diff options
Diffstat (limited to '24.c')
| -rw-r--r-- | 24.c | 205 |
1 files changed, 205 insertions, 0 deletions
@@ -0,0 +1,205 @@ + +#include <stdio.h> +#include <stdlib.h> + + +#define C_EMPTY 0x00 + +#define C_BLZ_N 0x01 +#define C_BLZ_E 0x02 +#define C_BLZ_S 0x04 +#define C_BLZ_W 0x08 + +#define C_BLZ (C_BLZ_N | C_BLZ_E | C_BLZ_S | C_BLZ_W) + +#define C_WALL 0x10 +#define C_ELF 0x20 + + +unsigned char * +pos(unsigned char * buf, int cols, int rows, int i, int j) +{ + i = ((i % cols) + cols) % cols; + j = ((j % rows) + rows) % rows; + + return buf + i + j * cols; +} + + +int +main() +{ + unsigned char * buf = NULL, * next = NULL; + int bufsiz = 0, buflen = 0; + int cols = -1, rows = -1, exit_col = -1, exit_row = -1; + int i, j, round; + + // Read input + while (1) { + 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 ((i = fgetc(stdin)) == EOF) + break; + switch (i) { + case '#': + buf[buflen++] = C_WALL; + break; + + case '.': + if (cols == -1) + buf[buflen++] = C_ELF; + else + buf[buflen++] = C_EMPTY; + break; + + case '^': + buf[buflen++] = C_BLZ_N; + break; + + case '>': + buf[buflen++] = C_BLZ_E; + break; + + case 'v': + buf[buflen++] = C_BLZ_S; + break; + + case '<': + buf[buflen++] = C_BLZ_W; + break; + + case '\n': + if (cols == -1) + cols = buflen; + break; + + default: + fprintf(stderr, "Unexpected input char %c\n", i); + return -1; + } + } + if (cols == -1 || buflen % cols != 0) { + fprintf(stderr, "Input size %d is not a multiple of row length %d\n", + buflen, cols); + free(buf); + return -1; + } + rows = buflen / cols; + + // Find the exit position + exit_row = rows - 1; + for (i = 0; i < cols; ++i) { + if (*pos(buf, cols, rows, i, exit_row) == C_EMPTY) + exit_col = i; + } + if (exit_col == -1) { + fprintf(stderr, "No exit position found!\n"); + free(buf); + return -1; + } + + // Create the "next" buffer, and place the walls in it. + if ((next = calloc(buflen, 1)) == NULL) { + fprintf(stderr, "Bad next alloc(%d)\n", buflen); + free(buf); + return -1; + } + for (i = 0; i < buflen; ++i) { + if (buf[i] == C_WALL) + next[i] = C_WALL; + } + + for (round = 0; (*pos(buf, cols, rows, exit_col, exit_row) & C_ELF) == 0; ++round) { + int elves = 0; + unsigned char * psrc, * pdest, * tmp; + + // Work out the possible positions of elves and blizzards in `next` + for (j = 0; j < rows; ++j) { + for (i = 0; i < cols; ++i) { + int o; + + psrc = pos(buf, cols, rows, i, j); + + if (*psrc & C_ELF) { + *pos(next, cols, rows, i, j) |= C_ELF; + if ((*(pdest = pos(next, cols, rows, i, j - 1)) & C_WALL) == 0) + *pdest |= C_ELF; + if ((*(pdest = pos(next, cols, rows, i + 1, j)) & C_WALL) == 0) + *pdest |= C_ELF; + if ((*(pdest = pos(next, cols, rows, i, j + 1)) & C_WALL) == 0) + *pdest |= C_ELF; + if ((*(pdest = pos(next, cols, rows, i - 1, j)) & C_WALL) == 0) + *pdest |= C_ELF; + ++elves; + } + if (*psrc & C_BLZ_N) { + for (o = 1; (*(pdest = pos(next, cols, rows, i, j - o)) & C_WALL) != 0; ++o) + ; + *pdest |= C_BLZ_N; + } + if (*psrc & C_BLZ_E) { + for (o = 1; (*(pdest = pos(next, cols, rows, i + o, j)) & C_WALL) != 0; ++o) + ; + *pdest |= C_BLZ_E; + } + if (*psrc & C_BLZ_S) { + for (o = 1; (*(pdest = pos(next, cols, rows, i, j + o)) & C_WALL) != 0; ++o) + ; + *pdest |= C_BLZ_S; + } + if (*psrc & C_BLZ_W) { + for (o = 1; (*(pdest = pos(next, cols, rows, i - o, j)) & C_WALL) != 0; ++o) + ; + *pdest |= C_BLZ_W; + } + } + } + if (elves == 0) { + fprintf(stderr, "Warning, ran out of elves after %d rounds!\n", round); + free(next); + free(buf); + return -1; + } + + // Whereever there is a blizzard and and elf together, remove the elf + for (j = 0; j < rows; ++j) { + for (i = 0; i < cols; ++i) { + if ((*(pdest = pos(next, cols, rows, i, j)) & C_ELF) != 0 + && (*pdest & C_BLZ) != 0) + { + *pdest &= ~C_ELF; + } + } + } + + // Swap next and buf, and clear `next` for next round + tmp = buf; + buf = next; + next = tmp; + for (j = 0; j < rows; ++j) { + for (i = 0; i < cols; ++i) { + if ((*(pdest = pos(next, cols, rows, i, j)) & C_WALL) == 0) + *pdest = C_EMPTY; + } + } + } + + printf("Found exit after %d rounds\n", round); + + // Tidy and exit + free(next); + free(buf); + + return 0; +} + |