diff options
| -rw-r--r-- | 23.c | 467 | ||||
| -rw-r--r-- | makefile | 1 |
2 files changed, 468 insertions, 0 deletions
@@ -0,0 +1,467 @@ + +#include <ctype.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + + +#define arrlen(x) (sizeof(x)/sizeof((x)[0])) + + +// Directions. Use characters corresponding to directions surrounding the 's' +// on a querty keyboard. Because why not? +#define DIR_N 'w' +#define DIR_S 'x' +#define DIR_W 'a' +#define DIR_E 'd' + +#define DIR_NW 'q' +#define DIR_NE 'e' +#define DIR_SW 'z' +#define DIR_SE 'c' + + +// Is this location an elf? +int +loc_elf(char ch) +{ + switch (ch) { + case '#': + case DIR_N: + case DIR_S: + case DIR_W: + case DIR_E: + return 1; + } + return 0; +} + + +// What direction does the elf at this location want to move? +int +loc_elf_dir(char ch) +{ + switch (ch) { + case DIR_N: + case DIR_S: + case DIR_W: + case DIR_E: + return ch; + case '#': + return 0; + } + return -1; + +} + + +// Is this location clear? +int +loc_clear(char ch) +{ + switch (ch) { + case '.': + case '\n': + return 1; + } + return 0; +} + + +// Is this location a proposed destination? +int +loc_proposed(char ch) +{ + return isdigit(ch); +} + + +// Get the offset of a position in a buffer, one move in a given direction +char * +posd(char * buf, int cols, int rows, int i, int j, int dir) +{ + int offset; + + switch (dir) { + case 0: offset = i + j * cols; break; + + case DIR_N: offset = i + (j - 1) * cols; break; + case DIR_S: offset = i + (j + 1) * cols; break; + case DIR_W: offset = (i - 1) + j * cols; break; + case DIR_E: offset = (i + 1) + j * cols; break; + + case DIR_NW: offset = (i - 1) + (j - 1) * cols; break; + case DIR_NE: offset = (i + 1) + (j - 1) * cols; break; + case DIR_SW: offset = (i - 1) + (j + 1) * cols; break; + case DIR_SE: offset = (i + 1) + (j + 1) * cols; break; + + default: + fprintf(stderr, "Unknown direction %d\n", dir); + return NULL; + } + + if (offset < 0 || offset > rows * cols) { + fprintf(stderr, "Invalid location at %d,%d", i, j); + switch (dir) { + case DIR_N: fprintf(stderr, "+N"); break; + case DIR_S: fprintf(stderr, "+S"); break; + case DIR_W: fprintf(stderr, "+W"); break; + case DIR_E: fprintf(stderr, "+E"); break; + case DIR_NW: fprintf(stderr, "+NW"); break; + case DIR_NE: fprintf(stderr, "+NE"); break; + case DIR_SW: fprintf(stderr, "+SW"); break; + case DIR_SE: fprintf(stderr, "+SE"); break; + } + fprintf(stderr, " in %dx%d\n", cols, rows); + return NULL; + } + + return buf + offset; +} + + +// Get the offset of a position in a buffer +char * +pos(char * buf, int cols, int rows, int i, int j) +{ + return posd(buf, cols, rows, i, j, 0); +} + + +// Get the bounding box for elves +int +bounding(int * xmin, int * xmax, int * ymin, int * ymax, + char const * buf, int cols, int rows) +{ + int i, j; + + *xmin = *xmax = *ymin = *ymax = -1; + + for (j = 0; j < rows; ++j) { + for (i = 0; i < cols; ++i) { + if (buf[i + j * cols] != '#') + continue; + + if (*xmin == -1) { + *xmin = i; + *xmax = i; + *ymin = j; + *ymax = j; + } + if (i < *xmin) + *xmin = i; + if (i > *xmax) + *xmax = i; + if (j < *ymin) + *ymin = j; + if (j > *ymax) + *ymax = j; + } + } + + if (*xmin == -1) + return -1; + + // use a semi-open range. + ++*xmax; + ++*ymax; + + return 0; +} + + +// Check if it's possible to move in a certain direction +int +trymove(char * buf, int cols, int rows, int round, int i, int j) +{ + static char const dirs[4] = { DIR_N, DIR_S, DIR_W, DIR_E }; + int d, dir; + + if (!loc_elf(*pos(buf, cols, rows, i, j))) + // ??? + return -1; + + if (!loc_elf(*posd(buf, cols, rows, i, j, DIR_N)) + && !loc_elf(*posd(buf, cols, rows, i, j, DIR_S)) + && !loc_elf(*posd(buf, cols, rows, i, j, DIR_W)) + && !loc_elf(*posd(buf, cols, rows, i, j, DIR_E)) + && !loc_elf(*posd(buf, cols, rows, i, j, DIR_NW)) + && !loc_elf(*posd(buf, cols, rows, i, j, DIR_NE)) + && !loc_elf(*posd(buf, cols, rows, i, j, DIR_SW)) + && !loc_elf(*posd(buf, cols, rows, i, j, DIR_SE))) + // No elves nearby, do not move. + return 0; + + for (d = 0, dir = 0; d < arrlen(dirs) && dir == 0; ++d) { + switch (dirs[(round + d) % 4]) { + case DIR_N: + if (!loc_elf(*posd(buf, cols, rows, i, j, DIR_N)) + && !loc_elf(*posd(buf, cols, rows, i, j, DIR_NW)) + && !loc_elf(*posd(buf, cols, rows, i, j, DIR_NE))) + dir = DIR_N; + break; + + case DIR_S: + if (!loc_elf(*posd(buf, cols, rows, i, j, DIR_S)) + && !loc_elf(*posd(buf, cols, rows, i, j, DIR_SW)) + && !loc_elf(*posd(buf, cols, rows, i, j, DIR_SE))) + dir = DIR_S; + break; + + case DIR_W: + if (!loc_elf(*posd(buf, cols, rows, i, j, DIR_W)) + && !loc_elf(*posd(buf, cols, rows, i, j, DIR_NW)) + && !loc_elf(*posd(buf, cols, rows, i, j, DIR_SW))) + dir = DIR_W; + break; + + case DIR_E: + if (!loc_elf(*posd(buf, cols, rows, i, j, DIR_E)) + && !loc_elf(*posd(buf, cols, rows, i, j, DIR_NE)) + && !loc_elf(*posd(buf, cols, rows, i, j, DIR_SE))) + dir = DIR_E; + break; + + default: + return -1; + } + } + + return dir; +} + + +#if 0 +void +grid_dump(char * buf, int cols, int rows) +{ + int i, j; + + for (j = 0; j < rows; ++j) { + for (i = 0; i < cols; ++i) { + int c = buf[i + cols * j]; + fputc(c == '\n' ? '.' : c, stderr); + } + fputc('\n', stderr); + } +} +#endif + + +int +main() +{ + char * buf = NULL, * pch; + int bufsiz = 0, buflen = 0; + int cols, rows, round; + int xmin, xmax, ymin, ymax, i, j; + int empty; + + // Read input + while (1) { + size_t n; + + if (bufsiz - buflen < BUFSIZ) { + void * p; + + bufsiz += BUFSIZ; + if ((p = realloc(buf, bufsiz)) == NULL) { + fprintf(stderr, "Bad realloc(%d)\n", bufsiz); + free(buf); + return -1; + } + buf = p; + } + + if ((n = fread(buf + buflen, 1, bufsiz - buflen, stdin)) == 0) + break; + buflen += n; + } + if ((pch = memchr(buf, '\n', buflen)) == NULL) { + fprintf(stderr, "No lines in input!\n"); + free(buf); + return -1; + } + + // Work out grid dimensions + cols = pch + 1 - buf; + rows = buflen / cols; + if (buflen % cols != 0) { + fprintf(stderr, "Input size %d is not a multiple of row length %d\n", + buflen, cols); + free(buf); + return -1; + } + + // Do rounds of movement simulation + for (round = 0; round < 10; ++round) { + char * psrc, * pdest; + int dir; + + // Get current bounding box. + if (bounding(&xmin, &xmax, &ymin, &ymax, buf, cols, rows) != 0) { + fprintf(stderr, "Can't find bounding box!\n"); + free(buf); + return -1; + } + + // Expand it to cover all possible movement + --xmin; + ++xmax; + --ymin; + ++ymax; + + // Expand it to cover the current grid (resizing only checked for growth) + if (xmin > 0) + xmin = 0; + if (xmax < cols) + xmax = cols; + if (ymin > 0) + ymin = 0; + if (ymax < rows) + ymax = rows; + + // Check grid is big enough to contain any proposed movement + if (xmin < 0 || xmax > cols + || ymin < 0 || ymax > rows) + { + int newcols, newrows; + void * p; + +#if 0 + fprintf(stderr, "Before\n"); + grid_dump(buf, cols, rows); +#endif + + newcols = xmax - xmin; + newrows = ymax - ymin; + bufsiz = newcols * newrows; + if ((p = realloc(buf, bufsiz)) == NULL) { + fprintf(stderr, "Bad realloc(%d)\n", bufsiz); + free(buf); + return -1; + } + buf = p; + + // Set bottom row(s) as empty. + memset(buf + rows * newcols, '.', (newrows - rows) * newcols); + // Move old rows into position, last first + for (j = rows - 1; j >= 0; --j) { + pdest = pos(buf, newcols, newrows, -xmin + cols, j + -ymin); + if (pdest + (newcols - (-xmin + cols)) - buf > newcols * newrows) { + fprintf(stderr, "Writing %d bytes to offset %d with buffer size %d\n", + newcols - cols, (int) (pdest - buf), newcols * newrows); + } + + memset(pos(buf, newcols, newrows, -xmin + cols, j + -ymin), '.', newcols - (-xmin + cols)); + memmove(pos(buf, newcols, newrows, -xmin, j + -ymin), + pos(buf, cols, rows, 0, j), + cols); + memset(pos(buf, newcols, newrows, 0, j + -ymin), '.', -xmin); + } + // Set top row(s) as empty. + memset(buf, '.', -ymin * newcols); + + // Set new rows, cols, and recalc bounding box. + cols = newcols; + rows = newrows; + + if (bounding(&xmin, &xmax, &ymin, &ymax, buf, cols, rows) != 0) { + fprintf(stderr, "Can't find bounding box!\n"); + free(buf); + return -1; + } + +#if 0 + fprintf(stderr, "After\n"); + grid_dump(buf, cols, rows); +#endif + } + + // Find proposed moves. + for (j = ymin; j < ymax; ++j) { + for (i = xmin; i < xmax; ++i) { + psrc = pos(buf, cols, rows, i, j); + if (!loc_elf(*psrc)) + continue; + if ((dir = trymove(buf, cols, rows, round, i, j)) <= 0) + continue; + + // Elf can potentially move. + // Set which direction they want to move in + *psrc = dir; + + // Count how many elves want to move to that position. + pdest = posd(buf, cols, rows, i, j, dir); + if (loc_clear(*pdest)) + *pdest = '1'; + else if (loc_proposed(*pdest)) + ++*pdest; + else + fprintf(stderr, "Unexpected destination at %d,%d\n", i, j); + } + } + + // Cancel moves which clash + for (j = ymin; j < ymax; ++j) { + for (i = xmin; i < xmax; ++i) { + psrc = pos(buf, cols, rows, i, j); + if (!loc_elf(*psrc)) + continue; + if ((dir = loc_elf_dir(*psrc)) <= 0) + continue; + + // Elf can potentially move. + // If more than one elf wants to move to dest, cancel movement. + pdest = posd(buf, cols, rows, i, j, dir); + if (*pdest != '1') + *psrc = '#'; + } + } + + // Finalise moves and clean up grid + for (j = ymin; j < ymax; ++j) { + for (i = xmin; i < xmax; ++i) { + psrc = pos(buf, cols, rows, i, j); + if ((dir = loc_elf_dir(*psrc)) > 0) { + // Finalise move. + pdest = posd(buf, cols, rows, i, j, dir); + *pdest = '#'; + *psrc = '.'; + } + else if (loc_proposed(*psrc)) { + // Clean up count of elves who wanted to move here. + *psrc = '.'; + } + } + } + +#if 0 + fprintf(stderr, "Round %d\n", round + 1); + grid_dump(buf, cols, rows); +#endif + } + + // Find the number of empty cells in the bounding box + empty = 0; + if (bounding(&xmin, &xmax, &ymin, &ymax, buf, cols, rows) != 0) { + fprintf(stderr, "Can't find bounding box!\n"); + free(buf); + return -1; + } + for (j = ymin; j < ymax; ++j) { + for (i = xmin; i < xmax; ++i) { + if (loc_clear(*pos(buf, cols, rows, i, j))) { + ++empty; + } + } + } + + printf("Number of empty spaces: %d\n", empty); + + // Tidy and exit + free(buf); + + return 0; +} + @@ -24,6 +24,7 @@ all: bin \ bin/20 \ bin/21 \ bin/22 \ + bin/23 \ bin: mkdir -p $@ |