20b.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         int c;
   9         UT_hash_handle hh;
  10 };
  11
  12 int key[512] = {0};
  13
  14 void add_point(struct entry **board, int x, int y, int gen, int 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 struct entry *get_entry(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         return e;
  32 }
  33
  34 void del_point(struct entry **board, int x, int y, int gen)
  35 {
  36         struct entry *e = get_entry(board, x, y, gen);
  37         if (e != NULL)
  38                 HASH_DEL(*board, e);
  39 }
  40
  41 int get_point(struct entry **board, int x, int y, int gen)
  42 {
  43         struct entry *e = get_entry(board, x, y, gen);
  44         if (e == NULL)
  45                 return key[0] == 1 ? gen % 2 : 0;
  46         return e->c;
  47 }
  48
  49 char evolve(struct entry **board, int px, int py, int gen)
  50 {
  51         int r = 0;
  52         for (int y = py-1; y<=py+1; y++)
  53                 for (int x = px-1; x<=px+1; x++)
  54                         r = r*2 + get_point(board, x, y, gen);
  55         return key[r];
  56 }
  57
  58 int main()
  59 {
  60         int c;
  61         int i = 0;
  62         while ((c = getchar()) != '\n')
  63                 key[i++] = c == '#' ? 1 : 0;
  64         if (getchar() != '\n')
  65                 return 1;
  66
  67         struct entry *board = NULL;
  68         int x = 0, minx = 0, maxx = 0;
  69         int y = 0, miny = 0, maxy = 0;
  70
  71         while ((c = getchar()) != EOF) {
  72                 if (c == '\n') {
  73                         if (x > maxx)
  74                                 maxx = x;
  75                         x = 0;
  76                         y++;
  77                 } else {
  78                         add_point(&board, x++, y, 0, c == '#' ? 1 : 0);
  79                 }
  80         }
  81         maxy = y;
  82
  83         int r = 0;
  84         for (int gen = 1; gen <= 50; gen++) {
  85                 minx -= 3;
  86                 miny -= 3;
  87                 maxx += 3;
  88                 maxy += 3;
  89
  90                 //Calculate r immediately all the time, saves 25ms
  91                 r = 0;
  92                 for (y = miny; y<maxy; y++) {
  93                         for (x = minx; x<maxx; x++) {
  94                                 int nc = evolve(&board, x, y, gen-1);
  95                                 r += nc;
  96                                 add_point(&board, x, y, gen, nc);
  97                         }
  98                 }
  99                 //Delete old items (saves ±1second, 160k instead of 3.6 elems)
 100                 struct entry *e, *tmp;
 101                 HASH_ITER(hh, board, e, tmp) {
 102                         if (e->p.gen == gen-1)
 103                                 HASH_DEL(board, e);
 104                         else
 105                                 break;
 106                 }
 107         }
 108
 109         printf("%d\n", r);
 110 }