2018/day11.c

   1 #define _GNU_SOURCE 1
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 #include <stdarg.h>
   6 #include <stdbool.h>
   7 #include <assert.h>
   8
   9 void debug(const char *fmt, ...) {
  10   va_list ap;
  11   if (getenv("DEBUG")) {
  12     va_start(ap, fmt);
  13     vfprintf(stderr, fmt, ap);
  14     va_end(ap);
  15   }
  16 }
  17
  18 #define LIMIT 300
  19
  20 static struct point {
  21   int8_t value;
  22   int row[LIMIT];
  23 } grid[LIMIT][LIMIT];
  24 static struct best {
  25   int x;
  26   int y;
  27   int sum;
  28 } best[LIMIT];
  29
  30 static int8_t level(int x, int y, int s) {
  31   int id = x + 10;
  32   int p = (id * y + s) * id;
  33   return (p % 1000) / 100 - 5;
  34 }
  35
  36 static void rows(int x, int y) {
  37   grid[x][y].row[0] = grid[x][y].value;
  38   for (int i = 1; i < LIMIT - y; i++)
  39     grid[x][y].row[i] = grid[x][y].row[i - 1] + grid[x][y + i].value;
  40 }
  41
  42 static void find(int size) {
  43   int i, j;
  44   bool dup = false;
  45   best[size - 1].sum = -5 * size * size;
  46   for (j = 0; j < LIMIT - size + 1; j++) {
  47     int sum = 0;
  48     for (i = 0; i < size; i++)
  49       sum += grid[i][j].row[size - 1];
  50     for (i = 0; i < LIMIT - size + 1; i++) {
  51       if (i)
  52         sum += grid[i + size - 1][j].row[size - 1] -
  53           grid[i - 1][j].row[size - 1];
  54       if (sum > best[size - 1].sum) {
  55         best[size - 1].sum = sum;
  56         best[size - 1].x = i + 1;
  57         best[size - 1].y = j + 1;
  58         dup = false;
  59       } else if (sum == best[size - 1].sum)
  60         dup = true;
  61     }
  62   }
  63   if (dup)
  64     debug("ignoring duplicate best candidates for size %d\n", size);
  65 }
  66
  67 int main(int argc, char **argv) {
  68   int s = 1955;
  69   int i, j;
  70   int max = 0;
  71
  72   if (argc > 1)
  73     s = atoi(argv[1]);
  74   for (j = 0; j < LIMIT; j++)
  75     for (i = 0; i < LIMIT; i++)
  76       grid[i][j].value = level(i + 1, j + 1, s);
  77   for (j = 0; j < LIMIT; j++)
  78     for (i = 0; i < LIMIT; i++)
  79       rows(i, j);
  80   for (i = 0; i < LIMIT; i++) {
  81     debug("%d\n", i);
  82     find(i + 1);
  83     if (best[i].sum > best[max].sum)
  84       max = i;
  85     else if (best[i].sum == best[max].sum)
  86       debug("size %d has same best as %d\n", i, max);
  87   }
  88   printf("best at %d,%d,%d with %d\n", best[max].x, best[max].y, max + 1,
  89          best[max].sum);
  90   return 0;
  91 }