Add 2024 day 6 solutions

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