Commit: b97816259f1f1ac095b8c639c2028d4f5884c383
Parent: 6d3ce68bb28de716c3b5833b01326d51918d0479
Author: Randy Palamar
Date: Tue, 5 Dec 2023 06:38:02 -0700
day3 c solution
This day was pretty rough, mostly due to the fact that the
provided test data missed most edge cases. The one I provided
should work better. For me the main thing hanging me up was when
there was 'N\nN'. Everything else was straight forward.
I worked on the Haskell solution for most of the day but it was a
complete slog. I find that Haskell is really unfriendly to
debugging. There is no way to print some intermediate value in the
middle of a function. So far this has to be the biggest negative
for me w.r.t. Haskell. I got frustrated and implemented it in C in
a fraction of the time. With this solution in hand it shouldn't be
difficult to fix my Haskell version but it will come later.
Runtime for this C version is very fast <550us. I will see if the
Haskell version performs worse or not.
Diffstat:
| A | day3/day3.c | | | 308 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | day3/test | | | 10 | ++++++++++ |
2 files changed, 318 insertions(+), 0 deletions(-)
diff --git a/day3/day3.c b/day3/day3.c
@@ -0,0 +1,308 @@
+/* AOC 2023: Day 3 - Gear Ratios
+ *
+ * Suppose you have the following visual representation
+ * of some schematic:
+ *
+ * 467..114.3
+ * 35*.......
+ * ......633.
+ * ......#...
+ * 617*......
+ * .....+.58.
+ * ..592.....
+ * ......755.
+ * .....*....
+ * $664.598..
+ *
+ * Task 1: Find the sum of all numbers adjacent to a symbol (everything
+ * that is not a '.', '\n', or digit) including diagonally.
+ * Test Output: 4361
+ *
+ * Task 2: If exactly two numbers are next to a '*' they are a gear.
+ * Its ratio is the product of the two numbers. Find the sum of all
+ * gear ratios.
+ * Test Output: 467835
+ */
+#include <assert.h>
+#include <fcntl.h>
+#include <stdarg.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/mman.h>
+#include <unistd.h>
+
+typedef uint64_t u64;
+typedef uint32_t u32;
+
+typedef struct { void *data; u32 idx, cap; } Vector;
+typedef struct { u32 r, c; } Index;
+typedef struct { Index s, e; } Pair;
+
+typedef struct {
+ int chr;
+ char *data;
+ u32 dlen;
+ u32 pos;
+ Index idx;
+} Scanner;
+
+static u32 line_length;
+static Vector numpairs;
+static Vector syms;
+
+static void
+die(char *fmt, ...)
+{
+ va_list ap;
+ va_start(ap, fmt);
+ vfprintf(stderr, fmt, ap);
+ va_end(ap);
+ exit(1);
+}
+
+static void
+resize_vector(Vector *v, size_t elemsize)
+{
+ if (v->idx + 1 < v->cap)
+ return;
+
+ v->cap += 10000;
+ v->data = realloc(v->data, v->cap * elemsize);
+
+ if (!v->data)
+ die("realloc\n");
+}
+
+static void
+inc(Scanner *s)
+{
+ if (s->chr == '\n') {
+ assert(line_length == 0 || line_length == s->idx.c + 1);
+ line_length = s->idx.c + 1;
+ s->idx.r++;
+ s->idx.c = 0;
+ } else {
+ s->idx.c++;
+ }
+ s->chr = s->data[++s->pos];
+}
+
+static void
+dec(Scanner *s)
+{
+ if (s->pos > 0 && s->data[s->pos - 1] == '\n') {
+ s->idx.r--;
+ s->idx.c = line_length - 1;
+ } else {
+ s->idx.c--;
+ }
+ s->chr = s->data[--s->pos];
+}
+
+static void
+number(Scanner *s, Vector *v)
+{
+ resize_vector(v, sizeof(Pair));
+ Pair *p = &((Pair *)v->data)[v->idx++];
+ p->s = s->idx;
+ for (inc(s); s->pos < s->dlen; inc(s))
+ if (s->chr < '0' || s->chr > '9')
+ break;
+ dec(s);
+ p->e = s->idx;
+}
+
+static void
+sym(Scanner *s, Vector *v)
+{
+ resize_vector(v, sizeof(Index));
+ ((Index *)v->data)[v->idx++] = s->idx;
+}
+
+static void
+scan(Scanner *s)
+{
+ for (; s->pos < s->dlen; inc(s)) {
+ if (s->chr >= '0' && s->chr <= '9')
+ number(s, &numpairs);
+ else if (s->chr != '.' && s->chr != '\n')
+ sym(s, &syms);
+ }
+}
+
+static u64
+pair_to_num(Pair *n, char *data)
+{
+ assert(n->s.r == n->e.r);
+ u64 ret = 0;
+ u32 len = n->e.c - n->s.c;
+ u32 roff = n->s.r * line_length;
+ for (u32 i = 0; i <= len; i++) {
+ u32 idx = roff + n->s.c + i;
+ int t = data[idx] & 0xFF;
+ assert(t <= '9' && t >= '0');
+ t -= '0';
+ for (u32 j = len - i; j > 0; j--)
+ t *= 10;
+ ret += t;
+ }
+ return ret;
+}
+
+static void
+dump_syms(Vector *v)
+{
+ for (u64 i = 0; i < v->idx; i++) {
+ Index s = ((Index *)v->data)[i];
+ printf("(%u, %u)\n", s.r, s.c);
+ }
+}
+
+static void
+dump_pairs(Vector *v, char *data)
+{
+ for (u64 i = 0; i < v->idx; i++) {
+ Pair *p = &((Pair *)v->data)[i];
+ printf("(%u, %u), (%u, %u) -> %zu\n",
+ p->s.r, p->s.c, p->e.r, p->e.c, pair_to_num(p, data));
+ }
+}
+
+#define MAX(A, B) ((A) > (B) ? (A) : (B))
+#define MIN(A, B) ((A) < (B) ? (A) : (B))
+static int
+intersects(Pair *p, Index *i)
+{
+ int min = MAX(0, (p->s.c - 1));
+ int max = MIN(line_length, p->e.c + 1);
+ if (min < 0) min = 0;
+ if (min <= i->c && i->c <= max)
+ return 1;
+ return 0;
+}
+
+static int
+validate_pair(Pair *p, Vector *v)
+{
+ Index *si;
+ int r1 = p->s.r - 1, r2 = r1 + 1, r3 = r2 + 1;
+ int sr = r1 >= 0? r1 : r2;
+
+ u32 idx;
+ for (idx = 0; idx < v->idx; idx++) {
+ si = &((Index *)v->data)[idx];
+ if (si->r >= sr)
+ break;
+ }
+ for (; si->r <= r3 && idx < v->idx; idx++) {
+ si = &((Index *)v->data)[idx];
+ if (si->r <= r3 && intersects(p, si))
+ return 1;
+ }
+ return 0;
+}
+
+static u64
+sum_pairs(char *data, Vector *np, Vector *s)
+{
+ u64 ret = 0;
+ for (u32 i = 0; i < np->idx; i++) {
+ Pair *p = &((Pair *)np->data)[i];
+ if (validate_pair(p, s))
+ ret += pair_to_num(p, data);
+ }
+ return ret;
+}
+
+static void
+get_stars(Vector *st, Vector *sy, char *data)
+{
+ for (u32 i = 0; i < sy->idx; i++) {
+ Index si = ((Index *)sy->data)[i];
+ u32 roff = si.r * line_length;
+ int t = data[roff + si.c] & 0xFF;
+ if (t != '*')
+ continue;
+ resize_vector(st, sizeof(Index));
+ ((Index *)st->data)[st->idx++] = si;
+ }
+}
+
+static u64
+validate_gear(Index *s, Vector *np, char *data)
+{
+ u64 ret = 0;
+ u32 count = 0, idx;
+ Pair *p;
+
+ int r1 = s->r - 1, r2 = r1 + 1, r3 = r2 + 1;
+ int sr = r1 >= 0? r1 : r2;
+
+ /* skip invalid rows */
+ for (idx = 0; idx < np->idx; idx++) {
+ p = &((Pair *)np->data)[idx];
+ if (p->s.r >= sr)
+ break;
+ }
+
+ for (; idx < np->idx; idx++) {
+ p = &((Pair *)np->data)[idx];
+ if (p->s.r > r3)
+ break;
+ if (!intersects(p, s))
+ continue;
+ if (ret == 0)
+ ret += pair_to_num(p, data);
+ else
+ ret *= pair_to_num(p, data);
+ count++;
+ if (count > 2)
+ return 0;
+ }
+ if (count != 2)
+ return 0;
+ return ret;
+}
+
+static u64
+gear_ratio(char *data, Vector *np, Vector *s)
+{
+ Vector stars = {0};
+ u64 ret = 0;
+ get_stars(&stars, s, data);
+ for (u32 i = 0; i < stars.idx; i++) {
+ Index *si = &((Index *)stars.data)[i];
+ ret += validate_gear(si, np, data);
+ }
+ free(stars.data);
+ return ret;
+}
+
+int
+main(int argc, char *argv[])
+{
+ int fd;
+ Scanner s = {0};
+
+ if (argc < 2)
+ die("must specify a file\n");
+
+ if ((fd = open(argv[1], O_RDONLY)) < 0)
+ die("can't open file: %s\n", argv[1]);
+ s.dlen = lseek(fd, 0, SEEK_END);
+ s.data = mmap(NULL, s.dlen, PROT_READ, MAP_PRIVATE, fd, 0);
+ s.chr = s.data[0];
+ close(fd);
+
+ scan(&s);
+ u64 sum = sum_pairs(s.data, &numpairs, &syms);
+ u64 gr = gear_ratio(s.data, &numpairs, &syms);
+ printf("Task 1:\t%8zu\n", sum);
+ printf("Task 2:\t%8zu\n", gr);
+
+ /* be a good boy and unmap */
+ munmap(s.data, s.dlen);
+
+ return 0;
+}
diff --git a/day3/test b/day3/test
@@ -0,0 +1,10 @@
+467..114.3
+35*.......
+......633.
+......#...
+617*......
+.....+.58.
+..592.....
+......755.
+.....*....
+$664.598..