2017/advent14.c

   1 #define _GNU_SOURCE 1
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 #include <unistd.h>
   6
   7 void hash (const char *in, char hash[16])
   8 {
   9   const int size = 256;
  10   unsigned char list[size];
  11   int i;
  12   for (i = 0; i < size; i++)
  13     list[i] = i;
  14   int skip = 0;
  15   int pos = 0;
  16   const char suffix[6] = { 17, 31, 73, 47, 23 };
  17   char *str = malloc(strlen(in) + 5 + 1);
  18   strcpy(stpcpy(str, in), suffix);
  19   for (int j = 0; j < 64; j++) {
  20     for (char *p = str; *p; p++) {
  21       int length = *p;
  22       for (i = 0; i < length / 2; i++) {
  23         int tmp = list[(i + pos) % size];
  24         list[(i + pos) % size] = list[(length - i - 1 + pos) % size];
  25         list[(length - i - 1 + pos) % size] = tmp;
  26       }
  27       pos += length + skip++;
  28     }
  29   }
  30   char *chunk = hash;
  31   for (i = 0; i < size; i++) {
  32     if (i % 16 == 0)
  33       *chunk = 0;
  34     *chunk ^= list[i];
  35     if (i % 16 == 15)
  36       chunk++;
  37   }
  38   free (str);
  39 }
  40
  41 int grid[128][128];
  42
  43 void visit (int n, int x, int y)
  44 {
  45   if (x < 0 || y < 0 || x > 127 || y > 127)
  46     return;
  47   if (grid[x][y] == 1) {
  48     grid[x][y] = n;
  49     visit (n, x + 1, y);
  50     visit (n, x - 1, y);
  51     visit (n, x, y + 1);
  52     visit (n, x, y - 1);
  53   }
  54 }
  55
  56 int main(int argc, char **argv)
  57 {
  58   if (argc != 2)
  59     return 1;
  60   char h[16];
  61   char *str;
  62   int len = asprintf(&str, "%s-127", argv[1]);
  63   char *p = str + len - 3;
  64   int count = 0;
  65   int i, j;
  66   for (i = 0; i < 128; i++) {
  67     sprintf(p, "%d", i);
  68     hash (str, h);
  69     if (getenv ("DEBUG")) {
  70       printf ("hash of %s was ", str);
  71       for (j = 0; j < sizeof h; j++)
  72         printf ("%02hhx", h[j]);
  73       putchar ('\n');
  74     }
  75     for (j = 0; j < sizeof h; j++)
  76       for (int k = 0; k < 8; k++)
  77         if ((1 << (7 - k)) & h[j])
  78           grid[i][j * 8 + k] = !!++count;
  79   }
  80   printf ("total of %d dirty blocks\n", count);
  81   int regions = 1;
  82   for (i = 0; i < 128; i++)
  83     for (j = 0; j < 128; j++)
  84       if (grid[i][j] == 1) {
  85         if (getenv ("DEBUG"))
  86           printf ("marking region %d at %d,%d\n", regions, i, j);
  87         visit (++regions, i, j);
  88       }
  89   printf ("total of %d regions\n", regions - 1);
  90   return 0;
  91 }