2017/advent3.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3
   4 #ifdef TRY1
   5 static int ringmax (int ring) {
   6   return (2 * ring - 1) * (2 * ring - 1);
   7 }
   8
   9 static int corner (int ring, int c) {
  10   return ringmax (ring) - ((ring - 1) * 2 * (4 - c));
  11 }
  12
  13 #if 0 // part 1
  14
  15 int main (int argc, char **argv) {
  16   if (argc != 2)
  17     return 1;
  18   int goal = atol(argv[1]);
  19   long ring = 1;
  20   while (ringmax (ring) < goal)
  21     ring++;
  22   printf ("ring = %ld\n", ring);
  23   int c = 0;
  24   while (corner (ring, ++c) < goal);
  25   printf ("between corners %d, %d\n", corner(ring, c - 1), corner(ring, c));
  26   int mid = (corner (ring, c - 1) + corner (ring, c)) / 2;
  27   printf ("distance = %ld\n", ring - 1 + abs (mid - goal));
  28   return 0;
  29 }
  30
  31 #else // part 2
  32
  33 static int ring_of (int cell) {
  34   int ring = 1;
  35   while (ringmax (ring) < cell)
  36     ring++;
  37   return ring;
  38 }
  39
  40 static int corner_of (int cell, int ring) {
  41   int c = 0;
  42   while (corner (ring, ++c) < cell);
  43   return c;
  44 }
  45
  46 static int e_of (int cell);
  47 static int n_of (int cell);
  48 static int w_of (int cell);
  49 static int s_of (int cell);
  50
  51 int e_of (int cell) {
  52   if (cell == 1)
  53     return 2;
  54   int ring = ring_of (cell);
  55   int c = corner_of (cell, ring);
  56   switch (c) {
  57   case 1:
  58     return cell + 8 * (ring - 1) + 1;
  59     break;
  60   case 2:
  61     return cell - 1;
  62   case 3:
  63     return cell == corner (ring, c) ? cell + 1 : cell - 8 * (ring - 1) + 3;
  64   case 4:
  65     return cell + 1;
  66   }
  67   abort ();
  68 }
  69
  70 int n_of (int cell) {
  71   if (cell == 1)
  72     return 4;
  73   int ring = ring_of (cell);
  74   int c = corner_of (cell, ring);
  75   switch (c) {
  76   case 1:
  77     return cell == corner (ring, c) ? e_of (cell) + 2 : cell + 1;
  78   case 2:
  79     return cell + 8 * (ring - 1) + 3;
  80   case 3:
  81     return cell - 1;
  82   case 4:
  83     return cell - 8 * (ring - 1) + 1;
  84   }
  85   abort ();
  86 }
  87
  88 int w_of (int cell) {
  89   if (cell == 1)
  90     return 6;
  91   int ring = ring_of (cell);
  92   int c = corner_of (cell, ring);
  93   switch (c) {
  94   case 1:
  95     return (cell == corner (ring, c) ? cell + 1 :
  96             cell == corner (ring, c - 1) + 1 ? cell - 1 :
  97             cell - 8 * (ring - 2) - 1);
  98   case 2:
  99     return cell == corner (ring, c) ? n_of (cell) + 2 : cell + 1;
 100   case 3:
 101     return cell + 8 * ring - 3;
 102   case 4:
 103     return cell - 1;
 104   }
 105   abort ();
 106 }
 107
 108 int s_of (int cell) {
 109   if (cell == 1)
 110     return 8;
 111   int ring = ring_of (cell);
 112   int c = corner_of (cell, ring);
 113   switch (c) {
 114   case 1:
 115     return cell == corner (ring, c - 1) + 1 ? corner (ring, 4) : cell - 1;
 116   case 2:
 117     return cell == corner (ring, c) ? cell + 1 : cell - 8 * (ring - 2) - 3;
 118   case 3:
 119     return cell == corner (ring, c) ? w_of (cell) + 2 : cell + 1;
 120   case 4:
 121     return cell + 8 * ring - 1;
 122   }
 123   abort ();
 124 }
 125
 126 static void locate (int goal) {
 127   printf ("\nprocessing %d\n", goal);
 128   int ring = ring_of (goal);
 129   printf ("ring = %d\n", ring);
 130   int c = corner_of (goal, ring);
 131   printf ("between corners %d, %d\n", corner(ring, c - 1), corner(ring, c));
 132   printf ("%4d %4d %4d\n", w_of (n_of(goal)), n_of(goal), e_of (n_of(goal)));
 133   printf ("%4d %4d %4d\n", w_of (goal), goal, e_of (goal));
 134   printf ("%4d %4d %4d\n", w_of (s_of(goal)), s_of(goal), e_of (s_of(goal)));
 135 }
 136
 137 static int *array;
 138 static int get(int cell, int neighbor) {
 139   if (neighbor < 1)
 140     abort();
 141   if (neighbor > cell)
 142     return 0;
 143   return array[neighbor];
 144 }
 145
 146 #define limit 100
 147 int main (int argc, char **argv) {
 148   if (argc != 2)
 149     return 1;
 150   int goal = atoi(argv[1]);
 151   int i;
 152   array = calloc(sizeof(int), limit + 1);
 153   array[1] = 1;
 154   for (i = 2; i <= limit; i++) {
 155     array[i] = get(i, e_of(i)) + get(i, e_of(n_of(i))) + get(i, n_of(i))
 156       + get(i, w_of(n_of(i))) + get(i, w_of(i)) + get(i, w_of(s_of(i)))
 157       + get(i, s_of(i)) + get(i, e_of(s_of(i)));
 158     if (array[i] > goal)
 159       break;
 160   }
 161   if (i > limit) {
 162     printf("limit is too small, recompile\n");
 163     return 2;
 164   }
 165   locate(i);
 166   printf("value = %d\n", array[i]);
 167   return 0;
 168 }
 169
 170 #endif
 171
 172
 173
 174 #else // try 2
 175
 176
 177
 178 typedef struct point {
 179   int x;
 180   int y;
 181   int value;
 182 } point;
 183 int main (int argc, char **argv) {
 184   if (argc != 2)
 185     return 1;
 186   int limit = atoi(argv[1]);
 187   point *grid = calloc(sizeof *grid, limit);
 188   if (!grid)
 189     return 2;
 190   enum direction { R, U, L, D } dir = R;
 191   grid[0].value = 1;
 192   for (int i = 1; i < limit; i++) {
 193     switch (dir) {
 194     case R:
 195       grid[i].x = grid[i - 1].x + 1;
 196       grid[i].y = grid[i - 1].y;
 197       if (grid[i].x == -grid[i].y + 1)
 198         dir = U;
 199       break;
 200     case U:
 201       grid[i].x = grid[i - 1].x;
 202       grid[i].y = grid[i - 1].y + 1;
 203       if (grid[i].x == grid[i].y)
 204         dir = L;
 205       break;
 206     case L:
 207       grid[i].x = grid[i - 1].x - 1;
 208       grid[i].y = grid[i - 1].y;
 209       if (grid[i].x == -grid[i].y)
 210         dir = D;
 211       break;
 212     case D:
 213       grid[i].x = grid[i - 1].x;
 214       grid[i].y = grid[i - 1].y - 1;
 215       if (grid[i].x == grid[i].y)
 216         dir = R;
 217       break;
 218     }
 219     for (int j = 0; j < i; j++)
 220       if (abs(grid[j].x - grid[i].x) <= 1 &&
 221           abs(grid[j].y - grid[i].y) <= 1)
 222         grid[i].value += grid[j].value;
 223 #if 1 // part 2
 224     if (grid[i].value > limit) {
 225       printf("%d = %d\n", i + 1, grid[i].value);
 226       return 0;
 227     }
 228 #endif
 229   }
 230   printf("%d,%d = %d\n", grid[limit - 1].x, grid[limit - 1].y,
 231          abs(grid[limit - 1].x) + abs(grid[limit - 1].y));
 232   return 0;
 233 }
 234 #endif