diff options
| -rw-r--r-- | 22.c | 239 | ||||
| -rw-r--r-- | makefile | 1 |
2 files changed, 240 insertions, 0 deletions
@@ -0,0 +1,239 @@ + +#define _GNU_SOURCE + +#include <ctype.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + + +// Proper modulo operator +#define modulo(n, m) ((((n) % (m)) + (m)) % (m)) + + +enum direction { + D_NORTH = 3, + D_EAST = 0, + D_SOUTH = 1, + D_WEST = 2, +}; + + +char const * +direction_name(enum direction dir) +{ + switch (dir) { + case D_NORTH: return "North"; + case D_EAST: return "East"; + case D_SOUTH: return "South"; + case D_WEST: return "West"; + } + return NULL; +} + + +enum direction +direction_turn(enum direction dir, char turn) +{ +#define direction_go(d, t) (1000 * (d) + (t)) + + switch (direction_go(dir, turn)) { + case direction_go(D_NORTH, 'R'): + case direction_go(D_SOUTH, 'L'): + return D_EAST; + + case direction_go(D_NORTH, 'L'): + case direction_go(D_SOUTH, 'R'): + return D_WEST; + + case direction_go(D_EAST, 'L'): + case direction_go(D_WEST, 'R'): + return D_NORTH; + + case direction_go(D_EAST, 'R'): + case direction_go(D_WEST, 'L'): + return D_SOUTH; + } + + fprintf(stderr, "Unexpected direction_turn(%d, %c)\n", dir, turn); + return D_NORTH; + +#undef direction_go +} + + +int +map_move(char * map, int cols, int rows, int pos, enum direction dir, int distance) +{ + int skip, wrap, base; + + switch (dir) { + case D_NORTH: + skip = -cols; + wrap = cols * rows; + break; + + case D_EAST: + skip = 1; + wrap = cols; + break; + + case D_SOUTH: + skip = cols; + wrap = cols * rows; + break; + + case D_WEST: + skip = -1; + wrap = cols; + break; + + default: + fprintf(stderr, "Unexpected direction %d\n", dir); + return -1; + } + + base = (pos / wrap) * wrap; + + while (distance > 0) { + int newpos = base + modulo(pos + skip, wrap); + + while (map[newpos] == ' ' || map[newpos] == '\n') + newpos = base + modulo(newpos + skip, wrap); + + switch (map[newpos]) { + case '.': + pos = newpos; + --distance; + break; + + case '#': + distance = 0; + break; + + default: + fprintf(stderr, "Unexpected map character %c\n", map[newpos]); + return -1; + } + } + + return pos; +} + + +int +main() +{ + char * buf = NULL, * beg, * end; + long bufsiz = 0, buflen = 0, maxline = 0, lines = 0; + long pos; + enum direction dir; + char distance[8], c; + int dlen = 0; + + + // Read map data + // Don't try and figure out lines yet, in case we get a line longer than + // our read buffer, which could make things awkward. + while (1) { + if (bufsiz - buflen < BUFSIZ / 2) { + void * p; + bufsiz += BUFSIZ; + if ((p = realloc(buf, bufsiz)) == NULL) { + fprintf(stderr, "Bad realloc(%ld)\n", bufsiz); + free(buf); + return -1; + } + buf = p; + } + + if (!fgets(buf + buflen, bufsiz - buflen, stdin)) + // End of file! + break; + + if (buflen > 0 && buf[buflen] == '\n' && buf[buflen - 1] == '\n') + // End of map input. + break; + + buflen += strlen(buf + buflen); + } + + // Work out max lines and longest line. + for (beg = buf, lines = 0; beg < buf + buflen; beg = end + 1, ++lines) { + end = memchr(beg, '\n', buf + buflen - beg); + if (end - beg > maxline) + maxline = end - beg; + } + if (maxline == 0 || lines == 0) { + fprintf(stderr, "Unexpected map size (%ld,%ld)\n", maxline, lines); + free(buf); + return -1; + } + ++maxline; // Also count the newline on the end of each line. + + // Resize the map data buffer to hold a full grid of data + if ((beg = realloc(buf, lines * maxline)) == NULL) { + fprintf(stderr, "Bad realloc(%ld)\n", bufsiz); + free(buf); + return -1; + } + buf = beg; + memset(buf + buflen, ' ', lines * maxline - buflen); + + // Move the map data so that it fits the grid properly + for (end = buf + buflen, pos = lines - 1; pos >= 0; end = beg, --pos) { + beg = memrchr(buf, '\n', (end - buf) - 1); + beg = beg ? beg + 1 : buf; + memmove(buf + pos * maxline, beg, (end - beg)); + memset(buf + (pos * maxline) + (end - beg) - 1, ' ', maxline - (end - beg) + 1); + buf[pos * maxline + maxline - 1] = '\n'; + } + + // Set initial position + pos = 0; + dir = D_EAST; + while (buf[pos] != '.') { + ++pos; + } + + // Read and follow the movement instructions. + while (pos >= 0 && (c = fgetc(stdin)) != EOF) { + if (isdigit(c)) { + distance[dlen++] = c; + } + else if (c == 'L' || c == 'R') { + distance[dlen] = '\0'; + + pos = map_move(buf, maxline, lines, pos, dir, atoi(distance)); + + dir = direction_turn(dir, c); + dlen = 0; + } + else if (c == '\n') { + // Cover last bit of distance, if any + distance[dlen] = '\0'; + pos = map_move(buf, maxline, lines, pos, dir, atoi(distance)); + break; + } + else { + fprintf(stderr, "Unexpected movement instruction (%c)\n", c); + free(buf); + return -1; + } + } + if (pos < 0) { + free(buf); + return -1; + } + + // Done. + printf("Password is %ld (%ld,%ld,%d)\n", + 1000 * (1 + pos / maxline) + 4 * (1 + pos % maxline) + dir, + (1 + pos % maxline), (1 + pos / maxline), dir); + + // Tidy and exit. + free(buf); + + return 0; +} + @@ -23,6 +23,7 @@ all: bin \ bin/19 \ bin/20 \ bin/21 \ + bin/22 \ bin: mkdir -p $@ |