20a.c

   1 #include <stdio.h>
   2
   3 #include <uthash.h>
   4
   5 struct point {int x; int y; int gen; };
   6 struct entry {
   7         struct point p;
   8         char c;
   9         UT_hash_handle hh;
  10 };
  11
  12 char *key = NULL;
  13
  14 void add_point(struct entry **board, int x, int y, int gen, char c)
  15 {
  16         struct entry *e = calloc(1, sizeof(struct entry));
  17         e->p = (struct point){.x=x, .y=y, .gen=gen};
  18         e->c = c;
  19         HASH_ADD(hh, *board, p, sizeof(struct point), e);
  20 }
  21
  22 char get_point(struct entry **board, int x, int y, int gen)
  23 {
  24         struct entry *e;
  25         struct point p;
  26         memset(&p, 0, sizeof(p));
  27         p.x = x;
  28         p.y = y;
  29         p.gen = gen;
  30         HASH_FIND(hh, *board, &p, sizeof(struct point), e);
  31         if (e == NULL) {
  32                 if (key[0] == '#')
  33                         return gen % 2 == 0 ? '.' : '#';
  34                 else
  35                         return '.';
  36         }
  37         return e->c;
  38 }
  39
  40 char evolve(struct entry **board, int px, int py, int gen)
  41 {
  42         int r = 0;
  43         for (int y = py-1; y<=py+1; y++)
  44                 for (int x = px-1; x<=px+1; x++)
  45                         r = r*2 + (get_point(board, x, y, gen) == '#' ? 1 : 0);
  46         return key[r];
  47 }
  48
  49 int main()
  50 {
  51         size_t len = 0;
  52         if (getline(&key, &len, stdin) == -1)
  53                 return -1;
  54         if (getchar() != '\n')
  55                 return 1;
  56
  57         struct entry *board = NULL;
  58         int x = 0, minx = 0, maxx = 0;
  59         int y = 0, miny = 0, maxy = 0;
  60
  61         int c;
  62         while ((c = getchar()) != EOF) {
  63                 if (c == '\n') {
  64                         if (x > maxx)
  65                                 maxx = x;
  66                         x = 0;
  67                         y++;
  68                 } else {
  69                         add_point(&board, x++, y, 0, c);
  70                 }
  71         }
  72         maxy = y;
  73
  74         int gen = 1;
  75         for (; gen <= 2; gen++) {
  76                 minx -= 3;
  77                 miny -= 3;
  78                 maxx += 3;
  79                 maxy += 3;
  80
  81                 for (y = miny; y<maxy; y++)
  82                         for (x = minx; x<maxx; x++)
  83                                 add_point(&board, x, y, gen,
  84                                         evolve(&board, x, y, gen-1));
  85         }
  86
  87         int r = 0;
  88         for (y = miny; y<maxy; y++)
  89                 for (x = minx; x<maxx; x++)
  90                         if (get_point(&board, x, y, gen-1) == '#')
  91                                 r++;
  92         printf("%d\n", r);
  93 }