diff options
| -rw-r--r-- | 24.c | 242 |
1 files changed, 153 insertions, 89 deletions
@@ -1,6 +1,8 @@ #include <stdio.h> #include <stdlib.h> +#include <string.h> +#include <unistd.h> #define C_EMPTY 0x00 @@ -26,99 +28,41 @@ pos(unsigned char * buf, int cols, int rows, int i, int j) } -int -main() +void +clear_mask(unsigned char * buf, int cols, int rows, unsigned mask) { - 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; + int i, j; - default: - fprintf(stderr, "Unexpected input char %c\n", i); - return -1; + for (j = 0; j < rows; ++j) { + for (i = 0; i < cols; ++i) { + *pos(buf, cols, rows, i, j) &= ~mask; } } - 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; - } + +int +find_path(unsigned char * buf, int cols, int rows, + int start_col, int start_row, int exit_col, int exit_row) +{ + unsigned char * realnext, * next; + int i, j, round; // 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); + if ((next = realnext = calloc(rows, cols)) == NULL) { + fprintf(stderr, "Bad next alloc(%d)\n", cols * rows); return -1; } - for (i = 0; i < buflen; ++i) { - if (buf[i] == C_WALL) - next[i] = C_WALL; + for (j = 0; j < rows; ++j) { + for (i = 0; i < cols; ++i) { + if (*pos(buf, cols, rows, i, j) == C_WALL) + *pos(next, cols, rows, i, j) = C_WALL; + } } + // Place the start elf + *pos(buf, cols, rows, start_col, start_row) = C_ELF; + for (round = 0; (*pos(buf, cols, rows, exit_col, exit_row) & C_ELF) == 0; ++round) { int elves = 0; unsigned char * psrc, * pdest, * tmp; @@ -166,8 +110,7 @@ main() } if (elves == 0) { fprintf(stderr, "Warning, ran out of elves after %d rounds!\n", round); - free(next); - free(buf); + free(realnext); return -1; } @@ -186,18 +129,139 @@ main() 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; + clear_mask(next, rows, cols, C_ELF | C_BLZ); + } + + if (next != realnext) { + // Our `next` and `buf` variables are flipped. + // Copy `buf` into `next` so that the caller has an up-to-date + // copy of the map. + memcpy(next, buf, cols * rows); + } + + // Tidy and exit + free(realnext); + + return round; +} + + +int +main(int argc, char ** argv) +{ + unsigned char * buf = NULL; + int part = 1, bufsiz = 0, buflen = 0; + int cols = -1, rows = -1, start_col = -1, start_row = -1, exit_col = -1, exit_row = -1; + int i, round; + + // Parse options + while ((i = getopt(argc, argv, "p:")) != -1) { + switch (i) { + case 'p': + part = atoi(optarg); + break; + + default: + return -1; + } + } + + // 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 '.': + 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 start/exit positions + start_row = 0; + exit_row = rows - 1; + for (i = 0; i < cols; ++i) { + if (*pos(buf, cols, rows, i, start_row) == C_EMPTY) + start_col = 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; + } + + switch (part) { + case 1: + round = find_path(buf, cols, rows, start_col, start_row, exit_col, exit_row); + break; + + case 2: + round = find_path(buf, cols, rows, start_col, start_row, exit_col, exit_row); + clear_mask(buf, cols, rows, C_ELF); + round += find_path(buf, cols, rows, exit_col, exit_row, start_col, start_row); + clear_mask(buf, cols, rows, C_ELF); + round += find_path(buf, cols, rows, start_col, start_row, exit_col, exit_row); + break; + + default: + fprintf(stderr, "Unexpected part %d\n", part); + free(buf); + return -1; } printf("Found exit after %d rounds\n", round); // Tidy and exit - free(next); free(buf); return 0; |