lilibyte

Advent of Code 2023: The Reckoning of Elves
2023-12-01
cyberspace, software

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.

2022

2021

Day 01 | Day 02 | Day 03 | Day 04 | Day 05 | Day 06


Day 01

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);
}

Day 02

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);
}

Day 03

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);
}


Day 04

(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);
}

Day 05

(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.


Day 06

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);
}