#include #include #define GRID_SIZE 300 /* Dump a 2d array for debugging */ #define array_size(array) (sizeof array / sizeof array[0]) #define dump2d(array) { \ puts(#array":"); \ for (int row = 0; row < array_size(array); row++) { \ for (int col = 0; col < array_size(array[0]); col++) { \ printf("%5d", array[row][col]); \ } \ putchar('\n'); \ } \ } #define BAD_ARGS 1 int main(int argc, char *argv[]) { static int cells[GRID_SIZE][GRID_SIZE]; int grid_serial; struct { int power_level, bottom, right, size; } best = {INT_MIN}; if (argc < 2 || sscanf(argv[1], "%d", &grid_serial) != 1 ) { return BAD_ARGS; } /* Fill in cell power levels and check individual cells */ for (int row = 0; row < GRID_SIZE; row++) { int y = row + 1; for (int col = 0; col < GRID_SIZE; col++) { int x = col + 1; int rack_id = x + 10; int power_level = rack_id * y; power_level += grid_serial; power_level *= rack_id; power_level = power_level % 1000 / 100; power_level -= 5; cells[row][col] = power_level; if (power_level > best.power_level) { best.power_level = power_level; best.bottom = row; best.right = col; best.size = 1; } } } if (0) dump2d(cells) /* Replace the value in each cell with the sum of all values in * the rectangle from that cell to the top left corner, inclusive */ for (int right = 1; right < GRID_SIZE; right++) { cells[0][right] += cells[0][right-1]; } for (int bottom = 1; bottom < GRID_SIZE; bottom++) { int row_sum = 0; for (int right = 0; right < GRID_SIZE; right++) { row_sum += cells[bottom][right]; cells[bottom][right] = row_sum + cells[bottom-1][right]; } } if (0) dump2d(cells) /* Check all squares 2x2 and up */ /* Sums for squares of any size in the top left corner * of the grid can be read off directly */ for (int right = 1; right < GRID_SIZE; right++) { int bottom = right; int size = bottom + 1; int power_level = cells[bottom][right]; if (power_level > best.power_level) { best.power_level = power_level; best.bottom = bottom; best.right = right; best.size = size; } } /* Other squares along the top row of the grid * need the rectangle to their left subtracted out */ for (int bottom = 1; bottom < GRID_SIZE; bottom++) { int size = bottom + 1; for (int right = size; right < GRID_SIZE; right++) { int power_level = cells[bottom][right] - cells[bottom][right-size]; if (power_level > best.power_level) { best.power_level = power_level; best.bottom = bottom; best.right = right; best.size = size; } } } /* Other squares down the left side of the grid * need the rectangle above them subtracted out */ for (int bottom = 2; bottom < GRID_SIZE; bottom++) { for (int right = 1; right < bottom; right++) { int size = right + 1; int power_level = cells[bottom][right] - cells[bottom-size][right]; if (power_level > best.power_level) { best.power_level = power_level; best.bottom = bottom; best.right = right; best.size = size; } } } /* Squares everywhere else need both the rectangle to their * left and the rectangle above them subtracted out, then * the overlap of those two regions added back in */ for (int size = 2; size < GRID_SIZE; size++) { for (int bottom = size; bottom < GRID_SIZE; bottom++) { for (int right = size; right < GRID_SIZE; right++) { int power_level = cells[bottom][right] - cells[bottom][right-size] - cells[bottom-size][right] + cells[bottom-size][right-size]; if (power_level > best.power_level) { best.power_level = power_level; best.bottom = bottom; best.right = right; best.size = size; } } } } printf("%d,%d,%d (%d)\n", best.right - best.size + 2, best.bottom - best.size + 2, best.size, best.power_level ); return 0; }