diff options
Diffstat (limited to '2024/06/puzzles.c')
| -rw-r--r-- | 2024/06/puzzles.c | 235 |
1 files changed, 235 insertions, 0 deletions
diff --git a/2024/06/puzzles.c b/2024/06/puzzles.c new file mode 100644 index 0000000..3e23933 --- /dev/null +++ b/2024/06/puzzles.c @@ -0,0 +1,235 @@ +#include <sys/stat.h> + +#include <err.h> +#include <errno.h> +#include <stdbool.h> +#include <stddef.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define new(a, T) ((T *)alloc(a, sizeof(T), _Alignof(T), 1)) +#define BETWEEN(lo, n, hi) ((lo) <= (n) && (n) <= (hi)) + +typedef struct { + ptrdiff_t x, y; +} vec2_t; + +typedef enum { + U, + R, + D, + L, +} dir_t; + +#if PART2 +typedef struct { + char *beg, *end; +} arena_t; + +typedef struct { + dir_t d; + vec2_t p; +} dpos_t; + +typedef struct gposset { + struct gposset *child[4]; + dpos_t key; +} gposset_t; +#endif + +static char *readinput(FILE *stream, vec2_t *start, vec2_t *size); +static vec2_t move(vec2_t pos, dir_t d); + +#if PART1 +static void simulate(char *buf, vec2_t pos, vec2_t size); +#else /* PART 2 */ +static size_t loopcnt(char *buf, vec2_t pos, vec2_t size); +static bool loops(char *buf, vec2_t pos, vec2_t size); +static uint64_t hash(dpos_t dp); +static bool ismember(gposset_t **m, dpos_t key, arena_t *perm); +static void *alloc(arena_t *a, ptrdiff_t size, ptrdiff_t align, + ptrdiff_t count); + +static char MEM[1024 * 1024]; /* 1 MiB */ +#endif + +int +main(void) +{ + FILE *fp = fopen("input", "r"); + if (fp == NULL) + err(EXIT_FAILURE, "fopen: input"); + + vec2_t pos, size; + char *buf = readinput(fp, &pos, &size); + +#if PART1 + size_t n = 0; + simulate(buf, pos, size); + for (const char *p = buf; *p != 0; p++) { + if (*p == 'X') + n++; + } +#else + size_t n = loopcnt(buf, pos, size); +#endif + printf("%zu\n", n); + + fclose(fp); + return EXIT_SUCCESS; +} + +char * +readinput(FILE *stream, vec2_t *start, vec2_t *size) +{ + struct stat sb; + if (fstat(fileno_unlocked(stream), &sb) == -1) + err(EXIT_FAILURE, "fstat: input"); + + char *buf = malloc(sb.st_size + 1); + if (buf == NULL) + err(EXIT_FAILURE, "malloc"); + buf[sb.st_size] = 0; + + if (fread_unlocked(buf, 1, sb.st_size, stream) != (size_t)sb.st_size) + err(EXIT_FAILURE, "fread: input"); + + start->x = start->y = 0; + for (const char *p = buf; *p != '^'; p++) { + if (*p == '\n') { + start->x = 0; + start->y++; + } else + start->x++; + } + + size->x = strchr(buf, '\n') - buf; + size->y = (sb.st_size + 1) / (size->x + 1); /* Last line lacks newline */ + + return buf; +} + +#if PART1 + +void +simulate(char *buf, vec2_t pos, vec2_t size) +{ +#define I(p) (p.y*(size.x + 1) + p.x) + dir_t d = U; + do { + buf[I(pos)] = 'X'; + vec2_t np = move(pos, d); + if (buf[I(np)] == '#') { + d = (d + 1) % 4; + pos = move(pos, d); + } else + pos = np; + } while (BETWEEN(0, pos.x, size.x - 1) + && BETWEEN(0, pos.y, size.y - 1)); +#undef I +} + +#else /* PART 2 */ + +size_t +loopcnt(char *buf, vec2_t pos, vec2_t size) +{ + size_t n = 0; + for (char *p = buf; *p != 0; p++) { + if (*p == '.') { + *p = '#'; + n += loops(buf, pos, size); + *p = '.'; + } + } + return n; +} + +bool +loops(char *buf, vec2_t pos, vec2_t size) +{ + dir_t d = U; + gposset_t *set = NULL; + arena_t perm = {MEM, MEM + sizeof(MEM)}; + + do { + if (ismember(&set, (dpos_t){d, pos}, &perm)) + return true; + int i; + for (i = 0; i < 4; i++) { + vec2_t np = move(pos, d); + if (buf[np.y*(size.x + 1) + np.x] != '#') { + pos = np; + break; + } + d = (d + 1) % 4; + } + if (i == 4) + return true; + } while (BETWEEN(0, pos.x, size.x - 1) + && BETWEEN(0, pos.y, size.y - 1)); + return false; +} + +void * +alloc(arena_t *a, ptrdiff_t size, ptrdiff_t align, ptrdiff_t count) +{ + ptrdiff_t padding = -(uintptr_t)a->beg & (align - 1); + ptrdiff_t available = a->end - a->beg - padding; + if (available < 0 || count > available/size) { + errno = ENOMEM; + err(EXIT_FAILURE, "%s", __func__); + } + void *p = a->beg + padding; + a->beg += padding + count*size; + return memset(p, 0, count * size); +} + +bool +ismember(gposset_t **m, dpos_t key, arena_t *perm) +{ + for (uint64_t h = hash(key); *m; h <<= 2) { + dpos_t l = key, r = (*m)->key; + if (l.d == r.d && l.p.x == r.p.x && l.p.y == r.p.y) + return true; + m = &(*m)->child[h >> 62]; + } + *m = new(perm, gposset_t); + (*m)->key = key; + return false; +} + +static uint64_t +_hash(uint64_t x) +{ + x = ((x >> 16) ^ x) * 0x45D9F3B; + x = ((x >> 16) ^ x) * 0x45D9F3B; + x = ((x >> 16) ^ x); + return x; +} + +uint64_t +hash(dpos_t dp) +{ + return _hash(dp.d) ^ _hash(dp.p.x) ^ _hash(dp.p.y); +} + +#endif + +vec2_t +move(vec2_t pos, dir_t d) +{ + static const vec2_t dirs[] = { + [U] = {0, -1}, + [D] = {0, +1}, + [L] = {-1, 0}, + [R] = {+1, 0}, + }; + vec2_t np = dirs[d]; + return (vec2_t){ + .x = pos.x + np.x, + .y = pos.y + np.y, + }; +}
\ No newline at end of file |