Advent of Code 2023: The Reckoning of Elves

2023-12-01

Merry Christmas!

I am too tired to write this up now but I'll update this post later lol.

using C this year. maybe I will need to fall back to something else eventually but I think that's not very likely. at this point I haven't touched python pretty much since last year AoC, so I might be worse off if I did resort to it, especially as I inevitably rediscover everything that annoys me about it.

hardest day 1 to my memory, but it was a pretty fun one. I greatly prefer this to waiting all day in anticipation for a 5 minute problem.

pitiful part 2 time

-------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 1 00:28:05 9706 0 03:30:30 17373 0

unfortunately I had my call to `strstr`

something like
`if ((needle = strstr(prev, digits[i])))`

which meant if there are ever lines with more than one
occurrence of the same digit substring, I would only find
the first one. It took a while to notice how I was misusing
the function since I hadn't even identified that as the issue.
my original code for part 1 used `getchar()`

and solved it in
place, but that's not very practical for part 2 so i had to
quickly rewrite it.

#include#include #include #include #define unset 999 char buf[256]; char *digits[10] = { "invalid", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" }; void finddigits(int *f, int *fidx, int *l, int *lidx) { char *first = NULL, *last = NULL; char *needle, *prev = buf; *f = *l = unset; for (int i = 1; i <= 9; ++i) { prev = buf; while ((needle = strstr(prev, digits[i]))) { if (!last || needle > last) { prev = needle + strlen(digits[i]) - 1; last = needle; *l = i; *lidx = last - buf; } else { ++prev; } if (!first || needle < first) { first = needle; *f = i; *fidx = first - buf; } } } } int main() { int silver = 0, gold = 0; char *c; while ((c = fgets(buf, 256, stdin))) { int first = unset, last; int first2, last2, fidx, lidx; finddigits(&first2, &fidx, &last2, &lidx); while (*c != '\n') { if (isdigit(*c)) { if (first == unset) last = first = *c - '0'; if (first2 == unset || c - buf < fidx) { first2 = *c - '0'; fidx = c - buf; } if (last2 == unset || c - buf > lidx) { last2 = *c - '0'; lidx = c - buf; } break; } ++c; } while (*c != '\n') { if (isdigit(*c)) { last = *c - '0'; if (last2 == unset || c - buf > lidx) { last2 = *c - '0'; lidx = c - buf; } } ++c; } silver += first * 10 + last; gold += first2 * 10 + last2; } printf("%d\n", silver); printf("%d\n", gold); }

i still need to do proper write ups here, but i'm exhausted still so.. "TODO"

i was drunk for this one due to my own poor timing but eventually i got it through trial and error.
my primary mistake was not resetting the color counts after each *set* rather than each *game*
in part 1. part 2 was trivial afterwards.

--------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 2 01:30:39 14310 0 01:37:42 13510 0

and the code (logically unwashed, but cleaned some excessive debug printing)

#include#include #include #include int getn(int *n) { int c, r = 0; while (!isdigit(c = getchar()) && c != EOF && c != '\n'); if (c == EOF || c == '\n') return c; ungetc(c, stdin); while (isdigit(c = getchar())) r = r * 10 + c - '0'; *n = r; return c; } int main() { int i = 1, c = 0; int silver = 0, gold = 0; bool ok = true; while (c != EOF) { ok = true; while ((c = getchar()) != ':'); getchar(); int r = 0, g = 0, b = 0; int mr = 0, mg = 0, mb = 0; while (c != '\n') { int n; c = getn(&n); if (c == '\n' || c == EOF) break; int color = getchar(); if (color == 'r') r += n; else if (color == 'g') g += n; else if (color == 'b') b += n; mr = (r > mr) ? r : mr; mg = (g > mg) ? g : mg; mb = (b > mb) ? b : mb; while ((c = getchar()) != ';' && c != ',' && c != '\n'); if (c == ';' || c == '\n') { if (r > 12 || g > 13 || b > 14) ok = false; r = g = b = 0; } } gold += mr * mg * mb; if (ok) silver += i; if (i++ == 100) break; } printf("%d\n", silver); printf("%d\n", gold); }

This one really killed me today. Every day so far I haven't had nearly as much trouble working
out the puzzle as I have formulating simple control flow around the input and running into
pitfalls, such as today's array bounds checking. I don't feel like inspecting my code right now
to figure out exactly where it was failing, but I only solved part 1 after adding an extra column
to each row in the schematic and putting a `'.'`

character in its extra spot. This means no
digit string ever had was immediately adjacent to its row's boundaries.

I am not disappointed with the way I managed to turn my part 1 code into part 2 code or how long that took, but part 1 fucking me yet again due to stupid mistakes is not a good sign for the year so far.

--------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 3 02:00:41 11908 0 02:33:20 10667 0

Here's my almost unwashed code:

#include#include #include #include #define MAX 142 char schematic[MAX][MAX]; struct gear { int len; int ratio; }; struct gear gears[MAX][MAX]; void fill() { int c, y = 0, x = 0; while ((c = getchar()) != EOF) { if (x == 0) schematic[y][x++] = '.'; if (c == '\n') { ++y; schematic[y][x] = '.'; x = 0; continue; } schematic[y][x++] = c; } } bool issymbol(char c) { return c != '.' && ispunct(c); } void gear_add(struct gear *gear, int n) { if (gear->ratio == 0) gear->ratio = 1; gear->ratio *= n; gear->len += 1; } #define gear_check(g) if (s == '*') gear_add((g), atoi(&schematic[y][x])) int ispart(int x, int y) { int len = 0, s; while (x + len < MAX && isdigit(schematic[y][x+len])) ++len; if (x + len < MAX) { // check if character to direct right is a symbol if (issymbol((s = schematic[y][x+len]))) { gear_check(&gears[y][x+len]); return atoi(&schematic[y][x]); } // check if character to bottom right is a symbol if (y < MAX - 1) { if (issymbol((s = schematic[y+1][x+len]))) { gear_check(&gears[y+1][x+len]); return atoi(&schematic[y][x]); } } // check if character to top right is a symbol if (y > 0) { if (issymbol((s = schematic[y-1][x+len]))) { gear_check(&gears[y-1][x+len]); return atoi(&schematic[y][x]); } } } if (x > 0) { // check if character to direct left is a symbol if (issymbol((s = schematic[y][x-1]))) { gear_check(&gears[y][x-1]); return atoi(&schematic[y][x]); } // check if character to bottom left is a symbol if (y < MAX - 1) { if (issymbol((s = schematic[y+1][x-1]))) { gear_check(&gears[y+1][x-1]); return atoi(&schematic[y][x]); } } // check if character to top left is a symbol if (y > 0) { if (issymbol((s = schematic[y-1][x-1]))) { gear_check(&gears[y-1][x-1]); return atoi(&schematic[y][x]); } } } // check if any characters to direct top are a symbol if (y > 0) { for (int i = 0; i < len; ++i) { if (issymbol((s = schematic[y-1][x+i]))) { gear_check(&gears[y-1][x+i]); return atoi(&schematic[y][x]); } } } // check if any characters to direct bottom are a symbol if (y < MAX - 1) { for (int i = 0; i < len; ++i) { if (issymbol((s = schematic[y+1][x+i]))) { gear_check(&gears[y+1][x+i]); return atoi(&schematic[y][x]); } } } return 0; } char *getnums(int *x, int *y) { static int _x = 0, _y = 0; if (_y >= MAX) return NULL; while (!isdigit(schematic[_y][_x])) { if (++_x == MAX) { _x = 0; if (++_y == MAX) return NULL; } } *x = _x; *y = _y; while (_x < MAX && isdigit(schematic[_y][_x])) ++_x; if (_x >= MAX) { _x = 0; ++_y; } return &schematic[*y][*x]; } int main() { fill(); int silver = 0, gold = 0; int x = 0, y = 0; while (getnums(&x, &y)) silver += ispart(x, y); for (int y = 0; y < MAX; ++y) for (int x = 0; x < MAX; ++x) if (gears[y][x].len > 1) gold += gears[y][x].ratio; printf("%d\n", silver); printf("%d\n", gold); }

(Writing this two days late)

I fumbled this one hard, making it way harder for no reason except laziness.

--------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 4 00:20:54 7754 0 03:58:12 23594 0

Naively I thought this would be best solved with a stack, or at least that's the direction
I started heading in. However, instead of writing a proper stack implementation, I just
used a really big array with `head`

and `tail`

variables to track where I currently was
within the array. For part two, I wasn't realizing just how great the scale of the problem
was because for some reason when it hit the end of my array it just stopped. Eventually
I noticed when I increased the size of the array, it would similarly increase the result I
was getting in turn. For that lazy solution to work, the array would have needed to have
been huge.

I wasted so much time attempting that, once I moved on and went back to the drawing board it didn't take long to solve.

As always the biggest problem to work around with AoC is myself, not the puzzle.

#define wsz 10 #define nsz 25 #define cards 205 int totals[cards]; int copies[cards]; int card() { int c, points = 0, total = 0; static int sack = 0; int winning[wsz] = { 0 }; while ((c = getchar()) != ':'); getchar(); for (int i = 0; i < wsz; ++i) { int a = getchar(); int b = getchar(); getchar(); int n = 0; if (a != ' ') n = (a - '0') * 10; n += b - '0'; winning[i] = n; } getchar(), getchar(); for (int i = 0; i < nsz; ++i) { int a = getchar(); int b = getchar(); getchar(); int n = 0; if (a != ' ') n = (a - '0') * 10; n += b - '0'; for (int j = 0; j < wsz; ++j) { if (winning[j] == n) { points = points ? points * 2 : points + 1; ++total; } } } totals[sack++] = total; return points; } void make_copy(int sack) { copies[sack] += 1; for (int i = sack + 1; i < cards && i <= sack + totals[sack]; ++i) make_copy(i); } int main() { int silver = 0, gold = 0; for (int i = 0; i < cards; ++i) silver += card(); for (int i = 0; i < cards; ++i) { make_copy(i); gold += copies[i]; } printf("%d\n", silver); printf("%d\n", gold); }

(Writing this a day late)

This one was daunting just to read. After you unwrap the whole thing, it's not actually
that difficult of a problem. However, I regrettably lost hours on a stupid mistake: I had an
intermediary variable of type `int`

that should have been `long`

. This is why the example
worked but not my own input; the example doesn't even approach needing a `long`

at all.

At least some of this time was spent taking a break or being distracted, but not as much as I'd like to be able to say.

--------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 5 03:34:25 19617 0 07:07:22 14161 0

I'll snip the code so the data (that I hardcoded lol) can be excluded but the whole file can be found on my github.

unsigned long to(unsigned long n, struct range *r) { unsigned long end = r->src + r->len - 1; if (r->src <= n && end >= n) { long l; if (r->src == n) l = r->dest; else if (r->src >= n) l = r->dest + (r->src - n); else l = n + -(r->src - r->dest); return l; } return -1; } #define sz(a, t) (sizeof((a)) / (sizeof(t))) #define find(seed, map) _find((seed), (map), sz(map, struct range)) unsigned long _find(unsigned long seed, struct range map[], long size) { long n; for (int i = 0; i < size; ++i) if ((n = to(seed, &map[i])) != -1) return n; return seed; } long getloc(long seed) { return find(find(find(find(find(find(find(seed, soil), fertilizer), water), light), temperature), humidity), location); } int main() { unsigned long silver = -1, gold = -1; for (long i = 0, n; i < sz(seeds, long); ++i) if ((n = getloc(seeds[i])) < silver) silver = n; printf("%ld\n", silver); for (long i = 0, n; i < sz(seeds, long); i += 2) { printf("%ld/%ld\n",i+1, sz(seeds, long)); for (long j = 0; j + seeds[i] <= seeds[i] + seeds[i + 1]; ++j) if ((n = getloc(seeds[i] + j)) < gold) { printf("\t%lu\n", n); gold = n; } } printf("%ld\n", gold); }

As you can see there are still parts of this that are absurdly bad. In particular, the
logic of `to()`

is way more complicated than it needs to be, but I was just breaking
down the logic as I could get it working in the moment without thinking about whether
it's a good design or not. I don't remember for sure, but the problem I was having
that I thought those pointless checks were "solving" was probably actually just the
integer type issue I mentioned above.

I'm not even remotely competent at math to recognize what the smart solutions for most problems are, but I have done a fair number of these puzzles at this point which often gives me the mere illusion of recognizing what to do.

In this case, I was trying to find patterns in the progress of the races to use to figure out
the fancy math / constant time solution to the problem, but nothing was working. Whenever
I ran the code I'd just get a hang as if this was another big `n`

brute force day. It took me
way longer than I wish to realize I had a stupid `for (int i = 0; i < time[r] - speed; ++i)`

range
accumulator loop instead of just doing `distance = speed * (t - speed)`

. Once I made that
change it finished quickly with the correct result.

--------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 6 00:17:56 6030 0 01:36:04 14326 0

There is certainly a trend in me making these problems significantly more difficult than they should be just by approaching them incorrectly (or at least poorly).

Luckily this was still more-or-less a gimme day, because I desperately need a good night's sleep.

uint64_t race(uint64_t speed, uint64_t t, uint64_t d) { uint64_t distance = speed * (t - speed); /* for (int i = 0; i < time[r] - speed; ++i) */ /* distance += speed; */ return distance > d; } int main() { uint64_t silver = 1, gold = 1; for (uint64_t r = 0; r < sizeof(time) / sizeof(uint64_t); ++r) { uint64_t total = 0; for (uint64_t i = 0; i <= time[r]; ++i) total += race(i, time[r], dist[r]); silver *= total; } uint64_t total = 0; for (uint64_t i = 0; i <= time2; ++i) total += race(i, time2, dist2); gold *= total; printf("%lu\n", silver); printf("%lu\n", gold); }