I am revisiting my 2025 solutions, rewriting in elisp.

My original Python solution was horrible, so inspired by other solutions online, I did one using coordinate compression and pre-calculated "2D prefix sum".

The solution is rather long for an AOC solution (around 150 lines). I was therefore wondering if anyone has found a short general solution.

My elisp Solution

My original Part 2 solution for this day took 21 seconds and 725Mb to run, so it took quite a bit of wrestling to get it small enough for the Raspberry Pi Pico.

I tried a naive DFS search on key collection order and although that technically worked the proof-of-concept took nearly 80 minutes on my laptop, which would have been over 13 hours on the Pico even if I managed to claw back a 10x speed-up. I tried Iterative Deepening A*, but that didn't even finish after an hour on the laptop; there are just too many combinations that get very close to the optimal path length, and a lot of those come from taking the shortest path early on in the search tree.

I swapped back over to A* and used u/e_blake's heuristic to get the search space down as far as possible. The heuristic is to take the sum of the shortest paths from each robot's current position to the furthest key that they still need to collect. That works way better than my initial heuristic of totalling the shortest paths connected to all uncollected keys:

With each open set entry and each G entry taking 12 bytes (distance, robot locations, collected keys) that gets within spitting distance of the 200KiB target, but not quite optimally. With ~8k+ entries in the G set, we really should be looking at a ~16k element hash table to keep good performance (hash tables are ideally power of 2 on the Pico because % is an expensive operation) and that one hash table blows 192KiB of our 200KiB budget.

The distance/priority for both the open set and the G set can easily fit into 16 bits for this day. The collected keys are already pretty optimal, you need 26 bits so you're not wasting much with a 32 bit integer as a bitfield. The robot combinations need to be able to represent 4 entries at any one of 30 locations (26 keys + 4 starts), and since 30 choose 4 is 27,405 then that can in theory fit into 16 bits as well.

The trick to get over (under?) the line is to use a Combinatorial Number System to encode the robot locations into an int16_t. At a smaller 8 bytes per entry for both blocks of memory, we can finally afford a decent sized hash table, albeit at an additional cost of compressing and uncompressing the state data each time.

Final memory budget (at peak) ended up being ~188KiB:

-------------------------------------
LBA Stats
  [Blocks] Total: 9  Free: 1  Used: 6  Sentinel: 2
  [Bytes] Total: 204608  Free: 12672  Used: 191936
  [FreeChain] Free: 1
-------------------------------------
LBA Blocks
[...9FB8][ Sentinel]    0 blocks       0 bytes
[...9FD8][Allocated]  225 blocks    7200 bytes <-- Edges to adjacent keys
[...BC18][Allocated]  113 blocks    3616 bytes <-- Path length to all keys
[...CA58][Allocated]   20 blocks     640 bytes <-- Combinatorial cache
[...CCF8][Allocated]    8 blocks     256 bytes <-- Key locations
[...CE18][Allocated] 1536 blocks   49152 bytes <-- Priority queue (open set)
[...8E38][Allocated] 4096 blocks  131072 bytes <-- Hash map (g_score)
[...8E58][     Free]  396 blocks   12672 bytes
[...BFF8][ Sentinel]    0 blocks       0 bytes
-------------------------------------

Runtime is surprisingly still quite respectable: ~1.8ms on PC and ~340ms on the Pico @ 125MHz.

Thanks again to u/e_blake for sharing that heuristic!

[code]

I was a little worried about being able to squash this one down small enough for a microcontroller. My original solution for this one took ~64MiB and after swapping over to less wasteful data types it would still take >500KiB to store the back end of the transformed sequence, so it needed a re-think.

The approach I took for that first solution wasn't particularly unique, I think a lot of people did more or less the same. Since the second half of the phase transform has coefficients of the form:

1111
0111
0011
0001

It's possible to calculate the next phase with a running sum:

ABCD -> A + B + C + D = W -> A + X
0BCD ->     B + C + D = X -> B + Y
00CD ->         C + D = Y -> C + Z
000D ->             D = Z -> D

But doing it phase by phase, you still need the entire back end of the sequence (up to the signal offset) in memory. For my input that's over half a million elements.

Looking at the sequence of additions, it turns out it's possible to calculate the full history of one row based only on the history of the row below it.

The bottom row is trivially always going to come out the same value, since it only ever depends on the original sequence number and it always gets multiplied by 1, but it's a little easier to see the pattern if we number them anyway:

000D = D₁ -> 000D₁ = D₂ -> 000D₂ = D₃ ->...
=>
D, D₁, D₂, D₃, ...

The row above depends only on the current value and the bottom row:

00CD = C₁ -> 00C₁D₁ = C₂ -> 00C₂D₂ = C₃ -> ...
=>
C, C₁, C₂, C₃, ...

The next row is where it gets interesting:

0BCD = B₁ -> 0B₁C₁D₁ = B₂ -> 0B₂C₂D₂ = B₃ ->...
=>
B, B₁, B₂, B₃, ...

Notice that B₂ + C₂ + D = B + (C₂ + D) and that (C₂ + D) = C₃. Which means B₃ = B₂ + C₃.

If we can store the full history of one row across all phases so that we've got access to [C, C₁, C₂, C₃, ...] we can calculate the whole sequence for the row above: [B, B₁, B₂, B₃, ...]. Since we're doing 100 phases, that full history is only 100 elements.

There's some additional housekeeping, like repeating the signal without actually having that many repeats in memory, and putting the digits into a ring buffer so that we're only keeping the most recent 8 digits processes, but that's the core of it:

    vector<char> phaseHistory(100);
    for (int i = 0; i < signalToProcess; i++)
    {
        int s = baseSignal.Next();
        for (int phase = 0; phase < (int)phaseHistory.size(); phase++)
        {
            s += phaseHistory[phase];
            s = s % 10;
            phaseHistory[phase] = s;
        }
        digits[i & (digits.size() - 1)] = s;
    }

[Full code]

Memory: 650 bytes for the input, 100 bytes for the phase history and 8 bytes for the digits - well under the memory constraints I'm aiming for! The runtime on PC is a respectable but not great ~115ms. (It's easy to get that down to ~25ms by only reducing the phase history with % every 4 loops, but it obscures the logic)

I'm aware that u/askalski and u/maneatingape have got very sophisticated solutions that use magic maths, but I have no idea if those techniques can be used to speed up this approach further. I'd need a couple of weeks of background reading just to take a run at those!

Overall I'm happy just to cross this one off my list of nemeses.

I am learning (e)lisp for fun and ended up making a highly overcomplicated solution to the "Virtual machine" problem from 2024/17.

In AOC_17_2024_advanced_macro_version.el I define op-codes using lisp macros, leading to a very compact notation. I have furthermore implemented a Wozmon type monitor program to poke the VM (however, not very useful for solving the problem).

I think (e)lisp is very nice for AOC, what do you think?

This year I've been working through my existing solutions to squash everything down to microcontroller sizes. The two main restrictions are to minimise both the working memory and the callstack usage. I was pretty sloppy with memory on my original solution, bumping the maximum callstack memory up to 16Mb so that I could recurse one block at a time, so it needed a complete rethink.

The core of the reworked algorithm to eliminate recursion is to process the space a single line at a time working in one of two modes. We're either working down the space trickling water downwards into unoccupied spaces, or we're filling the space upwards with water. We swap from trickling to filling when we hit a new bottom, and we swap from filling back to trickling when we haven't added any new water in a line update.

Trickle Down

The trickle down state is the simplest; it's mostly looking for any unsupported water on the line above and creating falling water on the current line. If we see any falling water on the row above hitting a supporting surface on the current row, then we flag that falling water into a new state (which I've arbitrarily called 'foam') and switch over to the filling up mode:

    ..|...|...#~~~#...
--> ......#...#...#...

Goes to:

    ..|...+...#~~~#... <-- New foam '+' flips state
--> ..|...#...#|||#...

Filling up

Filling up is a more complex state which does the following 3 things in order, looking at the current row, the row below and the row above:

1. Spread out any foam across supporting surfaces, plus a 1 block overhang for edges
2. Replace any runs of foam which are constrained at both ends with a run of static water*
3. Create new blobs of foam where running water is now supported by static water

Whenever we get an update that doesn't modify the state of the water at all we swap back into trickle down mode.

For example:

    .....|.....
    .....|.....
    ..#..|..#..
--> ..#..+..#..
    ..#######..

Spread foam:

    .....|.....
    .....|.....
    ..#..|..#..
--> ..#+++++#..
    ..#######..

Replace water:

    .....|.....
    .....|.....
    ..#..|..#..
--> ..#~~~~~#..
    ..#######..

Create new foam:

    .....|.....
    .....|.....
    ..#..+..#..
--> ..#~~~~~#..
    ..#######..

Repeat until:

--> .....|..... No updates on this line
    .+++++++++.
    ..#~~~~~#..
    ..#~~~~~#..
    ..#######..

Swapping between sweeping down and sweeping up states means that we process the same line multiple times, but for my input that doesn't work out all that badly. It's ~4,400 line updates to fill in just under ~2,000 lines, so we're processing each line roughly twice on average.

Area Storage

For my input the total working area is ~450 wide by ~2,000 tall. Even if we limit ourselves to the original 4 states (., #, |, ~) and pack every square into 2 bits, we would need ~220KiB to store the full space. That's more than the upper limit of ~200KiB I've set myself as a goal.

I instead use wrapped storage, allocating 64 real lines and aliasing every 64th line to the same line. The lines N+64, N+128, etc... map to the same storage as line N. This works because we never backtrack far enough in the filling state to need the older lines.

We rasterise the input lines into the space in chunks whenever we come to the bottom of the lines we've previously rasterised.

Since we're discarding old lines, we do need to keep tabs on how much water we've accumulated per line as we go. I do this in a relatively noddy way of keeping a ~2,000 element array of counts and updating a count per line whenever we've processed a line in the trickle down mode. It could be made more efficient if you tie the counting to the rasterisation process that discards old lines, but it was simpler this way and minimal extra memory.

Memory Used

For my input:

• ~2,300 lines of scanner input = ~18KiB
• 64 lines of ~450 bytes = ~28KiB
• ~2,000 lines of water counts = ~4KiB
• Total = ~50KiB

Small enough to run on a C64! Runtime on PC isn't terrible at ~5ms. I haven't run it on hardware yet, but if the usual x100 multiplier holds then it'll still be running under the 1s per puzzle target I try to hit.

The full gory details, minus some simple supporting libraries for parsing input, can be found here: [paste]

I'll admit that this one took the wind out of my sails for a few days. I'd been making decent progress with maybe one puzzle converted every spare evening or two, but even though I had the idea for the approach on this one pretty quickly, it took about a week to fully settle in my mind before I had enough motivation to take a run at it. Pretty pleased with where it ended up size-wise though; even if the code is a little ugly in places.

[*] I think I've just spotted a bug in my code while typing up the description, so there's an unhandled case where a box has an opening in the bottom. Doesn't affect the algorithm though.

One of the biggest performance surprises I've had so far squishing my solutions onto a Raspberry Pi Pico (RP2040) is day 25 for 2015. I knew the RNG was going to need 64-bit maths and that it would fall back to a software implementation, but I didn't predict just how slow that would be. The straightforward form of the solution takes a whopping ~27s to run through the ~17.8M multiply & modulo operations required!

Still, it's a good excuse as any to mess around with some maths and and some assembly.

64-bit multiply

The M0+ in the RP2040 doesn't have the UMULL instruction that produces a 64-bit result from two 32-bit values; you're stuck with MULS producing a 32-bit result. Grid method multiplication allows you to produce a full 64-bits across two 32-bit registers by splitting the input values into 16-bit pairs and doing the multiplication piecemeal:

[b:a] * [d:c] = [hi:lo]

Where:

• [b:a], [d:c] - 32-bit input values
• a, b, c, d - 16-bit halves of the input values
• [hi:lo] - 64-bit output in two 32-bit values

Then:

• [lo] = (a*c) + (c<<16) + (d<<16)
• [hi] = (b*d) + (c16) + (d16) + carry from lo

The carry is a pain to represent in C++. GCC provides __builtin_addc which is supposed to map to the correct ADCS instruction, but I didn't see it doing so in the generated code. I can only assume the structure of my code wasn't exactly right for GCC to perform the substitution.

It's much easier to control in the asm though.

64-bit modulo

This part took me a while to get my head around, but it turns out we've been quite lucky with the constants chosen for this puzzle.

The two basic rules of modular arithmetic we're interested in are:

• a1 * a2 === b1 * b2 (mod m)
• a1 + a2 === b1 + b2 (mod m)

Where:

• a1 === b1 (mod m)
• a2 === b2 (mod m)

Which allows us to do this:

• [hi:lo] % m === (2^32 * hi + lo) % m
• [hi:lo] % m === (2^32 * hi) % m + (lo % m)
• [hi:lo] % m === (2^32 % m) * (hi % m) + (lo % m)

2^32 % m is just the constant 4992:

• [hi:lo] % m === 4,992 * (hi % m) + (lo % m)

Each loop of the RNG is:

answer = (answer * 252,533) % 33,554,393

Which means the the largest intermediate value for the RNG is 33,554,392 * 252,533 = 8,473,591,274,936. The value in the upper 32-bits is therefore less than or equal to 8,473,591,274,936 / 2^32 ~= 1,972.

Since 4,992 * 1,972 = 9,844,244, and that's less than 33,554,393, it means that 4,992 * hi value is already modulo m.

• [hi:lo] % m === (4,992 * hi) + (lo % m)

We're adding two values that are both modulo m, so there's a chance that it will go over m, but it will always be less than 2 * m.

The net result is that we can do the 64-bit modulo with a single 32-bit multiply, a single 32-bit modulo operation and a single 32-bit subtraction if we're above 33,554,393.

Thankfully the Pico does have 32-bit integer divider hardware, so we can make use of that.

Putting the two reductions above into C++we get ~8.5s.

Hardware trickery

In order to push this even further I made the jump to asm. I couldn't seem to get enough control over the code generated from the C++ to really optimise the multiply, and the real party piece is to make use of the 8 cycles that the CPU has to wait for the divider hardware to generate a result.

By sheer coincidence the five instructions that weren't dependencies for the lo register just so happen to have a minimum cycle count of 8; meaning we get precisely zero wasted cycles waiting for the hardware div/mod to complete!

My final runtime for my input ends up being ~5s, which is about half a second faster than my intial guess at where I thought I might be able to get to. Quite pleased with that.

[Full solution]

I was going through year 2015 as an exercise in getting used to JS/Typescript and deno.

I came up with this solution while I was looking for something quicker than my initial brute-force one.

It's based on this bound which I figured out:

Let n = p_1 * p_2 * ... * p_m where p_1 <= p_2 <= ... <= p_m and prime. score(n) <= (1 + p_1) * (1 + p_2) * ... * (1 + p_m) = (a_1 p_1) * (a_2 * p_2) * ... * (a_m * p_m) where a_i = (p_i + 1) / p_i <= a_1^m p_1 * p_2 * ... * p_m = a_1^m n If n <= N then score (n) <= a_1 ^ (ceil(log_{p_1}(N)) N <= (p_1 + 1) ^(ceil(log_{p_1}(N))

I was pretty shocked when I saw how simple and quick the sieve methods were.

Anyway, I though I'd share I can't find a solution like it anywhere.

Part1

This concerns this puzzle: 2015-Day24.

After reading the discussion and review here: In Review I thought I would try my hand at a true brute-force solution, leveraging the expressiveness and speed of Smalltalk's collection libraries. Most of the solutions I've seen involve various clever tricks to avoid doing the work of checking through all the different combinations, or returning a solution without verifying that it is, in fact, the correct one.

The implementation I settled on completes part 1 in 70ms and part 2 in 6ms on my machine (Intel 270k+, 6000mhz DDR5). Smalltalk execution speed isn't as fast as a fully compiled language, but it's significantly faster than a purely interpreted language (like Python or Ruby). I'd be curious to see how this method would fare in something like Rust or Zig.

Here's the primary function doing all the work:

bestQE: compartments

| totalWeight |

totalWeight := packages sum.

1 to: (packages size // compartments) do: [ :comboCount |
    | potentialQuants |
    potentialQuants := OrderedCollection new.
    packages combinations: comboCount atATimeDo: [ :combo |
        | comboWeight |
        comboWeight := combo sum.
        (totalWeight - comboWeight) = (comboWeight * (compartments - 1))
            ifTrue: [
            | otherPackages |
            otherPackages := packages select: [ :x | (combo includes: x) not ].
            potentialQuants add: (otherPackages -> (combo inject: 1 into: [ :acc :x | acc * x]))]
         ].

    (potentialQuants sorted: [ :a :b | a value < b value ]) do: [ :potentialSolution |
        (self verifyRemainder: potentialSolution key splitInto: compartments - 1) ifTrue: [ ^ potentialSolution value ] ] ].

^ 'None found'

The only argument it takes is the number of compartments needing an even weight. It requires an instance variable "packages" which is an array containing the puzzle input as integers. Order is not important. Here's how it works:

1. Set an temporary variable totalWeight to hold the sum of all package weights.
2. Iterate from 1 to the number of packages divided by the number of compartments (no need to pass that size, since that would mean there is no solution). This is the number of packages that we will try to fit into the front compartment. Start with the fewest (just 1) and then add one more until we find a grouping that fits. The number of packages we're testing is passed forward as "comboCount".
3. For this quantity of packages to test, create an empty OrderedCollection (a growable Array) to hold any potential groupings that we find.
4. Take the group of all packages and stream them "comboCount" at a time through the next block of code, passing them as an Array called "combo". This is the part where the magic happens. We don't need to do any complicated looping or generate all the combinations we want to test in advance. The "packages" Array can stream all the combinations for us, one at a time.
5. Now we examine this particular "combo" Array. First, we store the sum of all its elements as the temporary variable comboWeight.
6. Is this combo a candidate? To check this, we look to see if, after subtracting the weight of this combo from the total weight of the packages, we are left with exactly the weight of the combo multiplied by (compartments - 1). That is, If we are dividing into 3 compartments, is the weight of THIS particular combo equal to a third of the total? If so, go to the next step. Otherwise, try the next combo.
7. If this combo passes the weight test, we create a temporary variable "otherPackages" pointing to an Array defined as all the packages that are NOT in our combo.
8. Then we add an association of the "otherPackages" and its QE score (by doing a quick multiplication fold on the combo Array) to our potential groupings Array we created in step 3. We might have several candidates at this combination size, and we need to find the smallest QE score of ones that properly fit.
9. After this process is repeated for the combo size we need to verify the set of potential answers, so we take the collection of candidates and sort them by ascending QE value. Basically, we don't want to evaluate ALL of them, just the smallest one that has other packages that can be verified to fit.
10. We then take that sorted collection of candidates, and verify each one using verifyRemainder, giving it the list of remaining packages and asking it whether it can be evenly split into (compartments - 1).
11. As soon as we find one that can be verified, that is the correct answer! We return the QE value of that candidate.
12. If none are found (which can also happen if the potentialQuants collection is empty), try combinations the next size larger. So, if no combinations of size 4 fit (or passed verification), try combinations of size 5.

Essentially - each time start with the smallest possible (smallest combo, then of those, the smallest QE). The first one that can be verified to fit is our answer;  return the QE.

Ok - now how about the verification? Again, I went with a brute-force approach:

verifyRemainder: list splitInto: piles

    | listWeight |

    piles = 1 ifTrue: [ ^ true ].

    listWeight := list sum.

    1 to: list size // piles do: [ :comboSize |
        list combinations: comboSize atATimeDo: [ :combo |
            | comboWeight |
            comboWeight := combo sum.
            (listWeight - comboWeight = (comboWeight * (piles - 1)) and: [
                self verifyRemainder: (list select: [ :x | (combo includes: x) not ])
                     splitInto: piles - 1 ]) ifTrue: [ ^ true ] ] ].

    ^ false

This has a lot in common with the bestQE function in the way it generates and checks groups of packages, but it is done recursively. It takes two arguments: the list of numbers to fit, and the number of piles to fit them into. Here's the outline:

1. Base case - if the number of piles asked for is only 1, then this was a successful split. Pass TRUE up the stack.
2. Otherwise, we still have work to do. Start by calculating the sum of the list we were given to split and store that value in listWeight.
3. Now we try the same method of generating larger and larger combinations that we used in the bestQE function.
4. We calculate the weight of each combination (storing in 'comboWeight'). The see if the comboWeight is exactly 1/piles of the listWeight. If so, it is a potential candidate for a successful split. In that case, recurse with a new list made up of packages that are NOT in the current list, and with one fewer pile. One thing to note here is the "and: []" construction. In Smalltalk, due to the way messages are evaluated by boolean objects, when and: is given a block as an argument (with the square brackets) that second condition is lazily evaluated. So, we don't recurse unless the current combo has the correct weight. If you're using a language that doesn't lazily evaluate AND, this will need an if/else condition.
5. If that particular grouping doesn't work, it tries the next. And if that comboSize has no successful groupings, it tries the next size up.
6. If no groupings successfully drop down into a pile of 1, then no split was successful, and the function returns "false".

In summary - We start checking combinations from the smallest possible size upward. We don't do ANY verification on them until we have a complete set for that combination size. We only verify them in ascending QE order. Verification uses the same computationally cheap "candidate filter" and reserves the harder stuff (collection allocation and building / recursion) once something passes the filter.

I realize that the input is meant to be "gentle" such that the smallest possible QE for a given combo size is the right answer, and no verification is needed. But that felt like an incomplete solution to me. Especially since, even with verification, the execution speed seems plenty fast (less than 100ms for both to complete).

One final note: These methods do assume that the input list has unique numbers. This is strongly implied by the problem statement, though it is not explicitly part of the puzzle. If the puzzle input could ever contain duplicated numbers, then the way that the "remaining packages" collection is created would have to be different. The core logic would remain the same.

One last thing - the discussion above that started me down this rabbit hole referenced Day17 and said that it was relatively similar to this day. For giggles: here is the Smalltalk solution to Day17:

One last thing - the discussion above that started me down this rabbit hole referenced Day17 and said that it was relatively similar to this day. For giggles: here is my solution to part 1 of Day17:

barrelCombinationsFor: needed

    | count |

    count := 0.

    1 to: barrels size do: [ :size | barrels combinations: size atATimeDo: [ :combo |
        (combo sum = needed) ifTrue: [ count := count + 1 ]
         ] ].

    ^ count

The thread was right. More than a passing similarity.

It took me a long while to figure out the details of what the puzzle was asking. Plus, I had a few false starts because I didn't really think it all the way through. I kept getting "Junctions" and "Connections" confused. I should go back and clean up this code, but frankly I'm kind of tired of looking at it right now ;-).

I did it in Rust, as I'm trying to learn the language.

use std::fs::File;
use std::io::{self, BufRead};
use std::path::Path;

use std::collections::HashSet;
use std::fmt;

//const FNAME: &str = "day8_sample.txt";
const FNAME: &str = "day8-input.txt";

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<File>>>
where
    P: AsRef<Path>,
{
    let file = File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

#[derive(PartialEq, Eq, Hash, PartialOrd, Ord, Clone, Copy)]
struct Point(i64, i64, i64);
impl fmt::Display for Point {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "({},{},{})", self.0, self.1, self.2)
    }
}

impl Point {
    fn distance(&self, p2: &Point) -> f64 {
        (((self.0 - p2.0).pow(2) + (self.1 - p2.1).pow(2) + (self.2 - p2.2).pow(2)) as f64)
            .sqrt()
            .abs()
    }
}

#[derive(PartialEq, Eq, Hash, PartialOrd, Ord, Clone, Copy)]
struct Pair(Point, Point);
impl fmt::Display for Pair {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "({},{})", self.0, self.1)
    }
}
impl Pair {
    fn contains(&self, point: &Point) -> bool {
        self.0 == *point || self.1 == *point
    }
}

fn make_circuits(junct: &Vec<Pair>) {
    let mut circuits: Vec<Vec<Pair>> = Vec::new();
    for &node in junct.iter() {
        let left = circuits
            .iter()
            .position(|c| None != c.iter().find(|&p| p.contains(&node.0)));
        let right = circuits
            .iter()
            .position(|c| None != c.iter().find(|&p| p.contains(&node.1)));
        match (left, right) {
            (None, None) => circuits.push([node].to_vec()),
            (Some(l), None) => circuits[l].push(node),
            (None, Some(r)) => circuits[r].push(node),
            (Some(l), Some(_)) if left == right => circuits[l].push(node),
            (Some(l), Some(r)) if left < right => {
                let (x, y) = circuits.split_at_mut(r);
                x[l].append(&mut y[0]);
                circuits.remove(r);
            }
            (Some(r), Some(l)) if left > right => {
                let (x, y) = circuits.split_at_mut(r);
                x[l].append(&mut y[0]);
                circuits.remove(r);
            }
            (Some(_), Some(_)) => {}
        }
    }

    let mut sizes: Vec<usize> = Vec::new();
    for c in circuits.iter() {
        let mut accumulator = HashSet::new();
        for n in c.iter() {
            accumulator.insert(n.0);
            accumulator.insert(n.1);
        }
        sizes.push(accumulator.len());
    }
    sizes.sort();
    sizes.reverse();
    let mut final_answer: usize = 1;
    for s in sizes.iter().take(3) {
        print!("{} ", s);
        final_answer *= s;
    }
    println!(" => {}", final_answer);
}

fn main() {
    if let Ok(lines) = read_lines(FNAME) {
        let mut junctions = Vec::new();
        let mut edges = Vec::new(); // consider a form of HasMap
        for line in lines.map_while(Result::ok) {
            let entry: Vec<i64> = line.split(',').map(|s| s.parse::<i64>().unwrap()).collect();
            let coord = Point(entry[0], entry[1], entry[2]);
            junctions.push(coord);
        }
        for (left_index, left_node) in junctions.iter().enumerate().skip(1) {
            for right_node in junctions.iter().take(left_index - 1) {
                edges.push((
                    Pair(left_node.clone(), right_node.clone()),
                    left_node.distance(right_node),
                ));
            }
        }
        edges.sort_by(|a, b| a.1.total_cmp(&b.1));
        let nodes: Vec<Pair> = edges.iter().take(1000).map(|p| p.0).collect();
        make_circuits(&nodes);
    }
}

Today we have a problem fit for the Santa mythos... Travelling Salesman (TSP). Route planning is important when you have a tight schedule. This starts a tradition of occasionally referencing a hard problem. NP-hard... worst case with TSP is superpolynomial. But since the input is part of the puzzle, it normally provides a way out so we don't have to face that.

I figure everyone got the same 8 names referencing various game places (under the principle that it'd be a shame for anyone to miss one). It's the distances that would be different in people's inputs. I suppose that makes this one of the easiest puzzles for people doing the Up-The-Ante of "write an input file generator".

And we're naturally given the complete (K_8) weighted graph... because Santa flies. And that's what makes this feasible... n is small. The thing with stuff like exponential growth is that everything is fine (often better than fine) until suddenly it's not. At this size, a brute force recursive DFS is still very fast. I could think about other approaches, but this was my first thought. And the fact is that the answer already pops out the instant I hit enter. Doing more is optional.

The code for the recursion is fairly simple for this. This could be a puzzle for someone who wants to try recursion for the first time. It is a common DFS search approach... a very standard pattern, that I've written many times for AoC. Return distance when you get to the end case, otherwise generate valid moves and recurse on those, take the min/max of them and return it. For a beginner, they'd probably want to use globals for the min/max stuff, which is fine. Get the recursing down search right first. Later on you can learn the "collecting up".

And although it is something I have written a lot, this puzzle still had interest for me.

One trick is that I added a ninth location (NorthPole) that was 0 distance from all the others (so it doesn't change anything). By starting at this node, I avoid worrying about the starting location. It also makes it more proper TSP... which involves a cycle, not a path. This is the standard, "I have to do special cases for ends? Can I step back somehow and remove them?" thinking (a classic example is using double pointers in C instead of single for walking structures). Spotting things like this made this puzzle feel a little more special.

And doing collection using minmax is nice to handle both at the same time (in doing this code review I got to clean that up, because now I allow myself to use List::AllUtils freely).

I also get to think about how I could do things a little more efficient. Like processing the list better than with grep. In a more intense problem, my old C-hack nature might come out with a bit-map and twiddling (bits - (bits & (bits - 1)) is cool) to handle the job. But it's not needed (list of at most 8 and shrinking), so simple and expressive is fine. This is one of the things that makes search problems interesting... there are always things to at least think about. Different ways to do things, and to keep in mind for later. And so I always like seeing them.

PS: Since I talked a lot about it, and the code is presentable, I'll put up a solution this time. I don't want to commit to doing that every day, nor do I want that to be the focus here. I thought about doing this as a separate solution post, but then the discussion would just get split or copied. So I'll make this the solution post. It's still early, the format of what this is can evolve (I've decided that it'd be handy to have puzzle names in the title).

https://pastebin.com/VNjML4F4

Source https://github.com/zack-bitcoin/adventofcode/blob/master/2022/day14/b.awk

When doing this one in C, I didn't want to deal with all the string stuff, so I found a mathematical solution that I really like.

Now, I'm learning Rust using AoC and decided to do the mathematical solution. I was told that I should post it here.

Edit: I realized that I got distracted and forgot to explain how it works.

The challenge is basically to find numbers that are a repeating pattern (there's more, less interesting (to me) details). This code tests a number to see if it is a repeating pattern. Here's a high-level description of the logic.

1. Use log10 (base 10 log) to determine how many digits are in the number aka its "scale".
2. Iteratively use modulo division to extract the last digits (1..scale/2) from the number.
3. Use multiplication and addition to repeat those digits
4. When the pattern is long enough, compare its value with the number.

Complete solution is here

fn check_entry(val: u64) -> bool {
    let scale: u32 = if val == 0 {
        1
    } else {
        (val as f32).log10() as u32 + 1
    };
    let mut decade = 1;
    for pat_scale in 1..=scale / 2 {
        decade *= 10;
        let mut pat = val % decade;
        if pat != 0 && scale % pat_scale == 0 {
            while pat < val {
                pat = pat * decade + pat % decade;
            }
            if pat == val {
                return true;
            }
        }
    }
    return false;
}

Over the course of the last two years, I have been plugging away at the Synacor Challenge. Today, I have finally collected and confirmed the final code!

Link to repository

Note that there is a "spoilers" directory that contains, predictably, spoilers to the puzzles.

Hi, AoC Reddit Friends!

I did a write-up for 2025 which was the first time I'd done AoC. Prior to December 2025 I had done no programming at all since back in the 1980's when I was a kid playing with a rudimentary BASIC interpreter.

Here's my write-up of the experience of using a LLM to teach programming (rather than having it write code).

https://www.reddit.com/r/adventofcode/comments/1ptagw8/aoc_2025_complete_first_real_programming/

I had heard stories about how unique the puzzles in AoC 2019 were, so I figured I would tackle it and see if I had gained some real programming skills or not.

 Spoilers Ahead for AoC 2019 

This time, my JS abilities were solid enough that I almost never had to use the LLM as a language reference, but occasionally I would run into a syntax error on something and have to ask for the syntax again ("Bro, I forget how to do a .reduce on an array. Remind me of the syntax?"). This would have been about the same as having a reference book on hand - basically a "faster internet search", saving me the trouble of looking through search results and posts and just asking for the syntax directly.

After I would solve the puzzle, I would then ask the LLM for improvements. A lot of the time the improvements were elements of the standard library that I just hadn't seen before. For example, I was making all the IntCode operators have uniform length this way:

const parseOperator = (instructions) => {
  let string = String(instructions);
  while (string.length < 5) {
    string = "0" + string;
  }
  return string;
};

The LLM introduced me to the .padStart method. So instead of calling the above function for each operation, I added this inside the IntCode VM/Interpreter:

 const operator = String(instructions[position]).padStart(5, "0");

Ahhhh, .padStart. Came in useful later. Add it to the toolbox. Other times the LLM would offer some efficiency suggestions, but I'm not sure they always would have made all that much difference. For example, in Day 24 I was using a map data structure to indicate areas where there were bugs with a key that was an X/Y/Z coordinate with a value of true/false. Works great, and allows me to also track empty spots - making it VERY easy to run the simulation since I can simply iterate over all known locations and let the map grow organically.

The LLM (Kimi K2.5-Thinking in this case) suggested storing ONLY locations where there are bugs in a set. That way set.has() gives me the boolean if there is a bug there. Simpler data. No need to store locations that are empty. But then the simulation logic is quite different. There is a memory improvement using a set, sure. But it's TINY over the course of such a small simulation (only 200 iterations). So - yes - cool idea to keep in mind for next time. I do tend to use sets primarily for memoization, so it's good to be reminded you can do other stuff with them. But it wasn't the kind of quantum leap from my experience with AoC 2025. Heck, with that one, my first question to the LLM after I got a working Day 1 Part 1 was, "What the heck is modulo???".

Other things that the LLMs would consistently complain about is my use of strings (specifically in my IntCode implementation). Yes, strings are slower than doing modular arithmetic to "peel away" the digits. But in Bun string manipulation is nearly free. To test this I benchmarked a crazy IntCode run that took about 30 minutes. Switching from strings (through the whole thing) to modulus operations saved about 2% of time over the entire run. It's non-zero improvement. But keeping strings throughout the entire implementation made it much easier to reason about the flow and adapt it to the needs of each puzzle. Every LLM I used for critique/improvements complained about my use of strings here. And if I was using another language/runtime I probably wouldn't have done it this way. Strings in other languages are much more computationally expensive, I get it. But they're so aggressively optimized in JS/Bun that I can throw them around basically however I want without worrying about it.

Ok - a few highlights:

Day 14 (Space Stoichiometry) was some sweet vindication. After wondering if my progression through AoC 2025 was due to AI assistance (some comments in this sub made me doubt myself), seeing this puzzle and writing up a quick implementation using dynamic programming and memoization - a mix of maps and sets - that allowed me to ignore the "leftover" parts of each recipe... it just felt like I finally knew what I was doing. I mentally braced myself for day 2, where the puzzle has to be solved in reverse with some truly huge numbers. But then I realized right away that I could brute-force the solution with a one-sided binary search... and DONE. Fastest part 2 I'd done so far. I have to admit that I was proud of myself. One trillion ore? It's nothing vs a binary search. Almost instant.

IntCode! - This was one of the most fun parts of the entire series. Making a tiny little VM and trying to adapt it to the puzzle was great. It reached the point around day 15 or so where it was fully generic. Each day after I simply reused the entire thing and wrote the program control logic around it. The big shift happened on Day 13. I had, up to that point, implemented IntCode as a pure function. It received the program and then an array of keystrokes. It would run the program, pushing all output to an array. Once the keystroke array queue was processed it returned the entire output array. When the control program wanted to send the next input, it would add it to the input array and send the whole thing through the IntCode VM again. Not efficient. But CLEAN. and CORRECT. It was slow, but extremely reliable.

Day 13 was the brick breaker simulation. Running the entire IntCode input sequence for every single joystick movement was simply too much to deal with. After a 30 minute (successful) run, I asked MiniMax 2.5 for some suggestions on how to save the state of the VM between input events. After a quick primer on generator functions and yielding values, I changed the input/output operators to pause the VM in between passing output and getting an input. Still used an array for output. Worked like a charm. After that the only thing that I bolted on was the ASCII translator. Fortunately, that's pretty easy to do in JS using the standard library.

For Day 25 I just played the adventure game. It was kinda fun to actually use the IntCode VM instead of have it perform instructions behind the scenes. I didn't have the heart to try to solve it algorithmically.

Several of these puzzles had wonderful "AH HAH!" moments. For example: Day 10 (Monitoring Station) seemed basically impossible to me, so I just sat on it for a few days. While I was eating wings at a local restaurant it suddenly occurred to me that this could be solved by a ratio. I quickly grabbed a napkin and asked for a pen from the server so I could write down the formula I wanted to try. It worked when I implemented it when I got home.

Some of the bad:

Day 10 Part 2 had some math that would have been EXTREMELY simple for someone who knows calculus. I'm just a regular guy trying to learn something new, so I had no idea what ArcTan even was. My daughter (who is taking Calculus II in college) explained it to me. After that it was fairly simple to write up, but this isn't the kind of thing that I could have reasoned out.

Day 16 Part 2 can only be computed fast enough because of an oddity in the test input. A generic solution would be MUCH slower and perhaps impossible to do on consumer hardware. This is the only puzzle that seemed "unfair" to me since it depends on noticing something about the input sequence. All the other puzzles don't rely (as far as I could tell) on some quirk of THAT input. That is, they all could be made to have "general" solutions. Just not this one.

Day 22 Part 2 relied on some very tricky math. Part 1 is trivial. It took me about a day to figure out that for Part 2 I only needed to track a single card backwards through the shuffles. Great! Implement reverse-cut. Easy. Implement reverse-deal-new-stack. Ultra simple. Deal with increment N???? This one had me stuck. Forever. I mean - it's easy to write a brute-force check for this. I checked it against the test deck size (10,007 cards) and it worked just fine. But with the totally insane size of the puzzle input, that just won't work at all. I finally broke down and asked the LLM for some math tutoring.

"If I have (A * B) % C = D and I know the values of B, C, and D, is there a normal/canonical way to get the value of A? I know that it has only one possible value because C is prime. What is this called and how do I do it?"

It tried to be helpful explaining inverse modulo stuff, but I couldn't understand it at all. Fermat has a theorem about it. Which works. I still don't get it. But in it goes to replace my O(n) version. Great - can compute a shuffle near-instantly. Then we get to the iteration part which, of course, has to be done logarithmically. And yes, I have no problem noticing that. But I don't know enough about logarithms. Or exponents. Or exponents combined with modular arithmetic (where they act differently, it seems). So.... yeah. Hit a math wall here. At least it wasn't a programming/logic wall. I just don't understand enough of the math. Neither did my daughter. This one looks pretty specialized. Oh well - I found a reference implementation to study, and just moved on. This one left a bad taste.

At least days 23 and 24 were so fun. I did have to ask for the normal way to get a bunch of generator functions in JS where I could interact with them by index for Day 23 (Category Six). Qwen 3.5 seemed confused by why I basically asked for an array. Did I not know what an array is? LOL. I was surprised by how simple that was. You can push generators into an array??? Like pointers???? Well, in that case.... Super fun puzzle to solve. I'm kinda proud of how quickly I threw this one together. IntCode implementation holding strong...

Day 24 (Planet of Discord) was just great. I wound up hardcoding a lot of stuff for Part 2 since it didn't involve different sized layers, so the LLMs complained that my version had too many magic numbers. Yeah, I know. I may get around to make it more general at some point. I'm just happy I was able to write out a performant solution without so much as asking to be reminded of the syntax. Realizing that my method required pre-seeding all adjacent squares on the initial map before passing it to the simulation... I figured it out myself, tested the theory, and implemented it cleanly! I know, this is all ordinary and whatever for most programmers.

But I'm new. And having a good time. About 10 weeks into my programming "journey".

So, what next? Well, I have so far really gravitated toward a functional programming style. I like functions with no side effects and immutable data. JS cries mechanical tears over my frequent use of structuredClone() to easily make sure no data passed as an argument gets messed with in any way. I like recursion - especially since Bun has proper TCO and I can do it million-deep without worrying about blowing the stack. JS has a fairly minimal standard library. So, for example, no LCM built in (needed for Day 12 Part 2). I had to write it myself - which was lots of fun:

const findLCM = (num1, num2) => {
  if (num1 === num2) return num1;
  const small = num1 < num2 ? num1 : num2;
  const large = num1 > num2 ? num1 : num2;
  const engine = (small, large, amount = 2, soFar = 1) => {
    if (amount > small) return soFar;
    if (large % small === 0) return soFar * small;
    if (small % amount === 0 && large % amount === 0) {
      const newSmall = small / amount;
      const newLarge = large / amount;
      const added = soFar * amount;
      return engine(newSmall, newLarge, amount, added);
    }
    return engine(small, large, amount + 1, soFar);
  };
  const GCD = engine(small, large);
  const LCM = (large / GCD) * small;
  return LCM;
};

I think I have to get comfortable with mutability. I need to be able to think of computation as something other than transformation of data. I also don't feel dependent on the LLM for holding my hand through basic concepts anymore. For that stage, JS was a great choice. I still think it's an amazing first language.

But it's time to learn the next thing. I'm going to do the next step of my programming journey in Smalltalk. :-)

Having completed 2024, 2025 years I complained to my friend, a huge AoC fan, how there are not too many problems calling for trees. He pointed me to 2020/day18 as an example of such a puzzle.

And I was in for a treat. While day 1 did not strictly require a parser, I suspected that day 2 would need one. So I built a recursive decent parser anyway.

And indeed, Day 2 built upon Day 1 by introducing additional requirements on operator priorities. Having a tokenizer/parser already made this trivial.

Do we have any other parser puzzles? I love-love-love my parsers and compilers!

In the spirit of our ongoing reviews of older puzzles, I took a look at my own Rust solution for this one, found that it was 4x slower then u/maneatingape's reference timing, so I looked for optimizations that I might have missed. Remembering his admonishment that the default HashMap is quite slow, I switched to rustc_hash::FxHashMap and then it was "only 3+x slower".

After running the reference benchmark on my own PC, I got 46 us, so effectively the same as the 47 on his Apple M4. This meant that there had to be some really huge difference in the code itself so I took a look at day08.rs , and lo and behold: They were effectively identical!

(At one point I replaced the generic regs.entry().or_insert() with an explicit test for the key, avoiding the entry key copy when not needed, that made a 1-2% difference.)

The only real difference was his use of a custom "FastMap" implementation, using the same FxHash, but further specialized, and that made all the difference in the world!

So Thank You maneatingape! From now on I'll borrow your hash.rs library!

(Also, thank you u/e_blake for the correct url!)

Today we need to hide our meddling in the system by overwriting some disks with fractal data. But the tricky bit is that we also need to provide a checksum for it.

First thing I do with magic numbers (like the space to fill here), is run them through factor. And that shows that both parts factor to and bunch of 2s and a 17. So the checksum will be 17 digits long. The personal input is a seed bit string. Mine is 17 digits long, and there's very good reasons to assume that everyone's is odd length (if not 17). Mine also has an odd number of set bits... there's a reason that might be consistent too, but that's not as key.

Not that the reason why having an odd number of digits was important to my initial solution anyways. Perl can easily reverse, translate, concatenate a string up to 40M in a blink. The big part is in calculating the checksum, and the rules are XNOR applied to adjacent pit pairs, and then pairs of pairs, and so on... until the entire section is done. Which is to say, it's like how I was calculating a parity bit for day 13, but we're getting the complement of it. It's fitting... parity bits were originally created for checksums.

And so, basically, initial solution comes down to this for each LENGTH / 17 section:

my $parity = 1;
for (my $i = $start; $i < $end; $i++) {
    $parity ^= substr( $str, $i, 1 );
}

Initiating parity to 1, gets us the complement. This is programmer efficient... no real thinking, and it runs in just over 6s on old hardware. So it's not a bad solution... especially if you just want to submit quick and have a script that's guaranteed to work for test and trying other things out.

First thing to target is the bottleneck, which is the parity loop... to see if we cut it down with something simple to start. And first thing I noticed is that the seed string and it's reversed compliment are inverses of each other. When they reflect, they turn into the other one. And so they alternate with pivot bits between them. But more than that, since they are complements of each other's bits, the total number of bits across a pair of them equals the length (ignoring the pivot for now). And so, there's a reason for the seed having odd length... each pair toggles parity, and so the total effect on parity depends on if the number of pairs in a section is even or odd. And so we can easily reduce our parity loop to about 1/18th the number of loops. You just need to do the initial few in a section to get to pivot, then all the pairs can be quickly done, then you need to do the pivot bits in between (the bulk, but only 1/18 of the string), and finish with the tail (the bit from the last aligned to the end). And so with that reduction, things run much faster (well under a second)... while still building the entire string to get all the single values we need.

Next experiment was done for my follow up initial Ruby solution (also done in C). Write a function to return the dragon curve value at an index, instead of creating it. As stated, the seed and the reverse compliment alternate in the output. So a table and an index % 36 (twice the seed length + 1 (cause we're including a pivot) of the first iteration can look up everything except the pivot points which occur at indices 17 mod 18. So we need to work out that pivot sequence, and it's just the regular dragon curve that begins with a seed of "0" (because the 0 added in the first iteration undergoes the rules and transforms to that).

So we need a way to calculate that. And what I did was notice that, since this a fractal, there's going to be the same alternating pattern of the "0" seed and it's reverse compliment ("1") on the even indices (0 mod 2). And when you remove those, you just get the pivots, which is the same "0" dragon curve you started with (self similarity in a fractal, who would have thought?). And that can be done endlessly. And the these sequences have a pattern, the first is indices 0 mod 2 (as noted), then 1 mod 4, 3 mod 8, 7 mod 16, etc. In binary, numbers in these sequences will share the the same length run of 1s in the low bits, then a 0, and then, since the sequence alternates, the next bit up is the value you want. Which is to say that if you have a number that's "10111101011X011", that's in the "mod 8" sequence, and the X is the value. So for pivots all we need is to get the bit above the least significant 0.

In C, I did that with:

return (!!(n & (~n & ~(~n - 1)) << 1));

This works because n & ~(n - 1) gives the least significant set bit. By taking ~n in there, we get the least significant 0. Then we shift it up 1 and us it as a mask against the original to select the bit we want. Then !! turns that from some power of 2 to just 0 or 1. (Side note: finding the last set bit also gives you all the 2s in factoring the number... which makes it convenient for calculating the length of the sections in this problem).

So with that in hand, putting it into the Perl solution instead of building the string... results in it taking 1 second longer. Who would have thought a string manipulation language might be really good at string manipulating? I could have probably bummed it down, but it didn't seem worthwhile... so I left the Perl solution with building the string and the Ruby/C solutions do it without.

BUT! The story doesn't end there. Because there's still those ~2M odd parity calculations tied to the pivot points. And in revisiting it now, wouldn't it be nice to cut those out? Like if we could directly calculate the parity of bits of the pivot sequence instead of just the sequence? If you have that, you can get the parity of the bits in a range by parity(end) ^ parity(previous end). So you only need to do that calculation once per section (ie 17 times). How to get that? I looked at it a little bit, but ultimately just calculated the first bunch and looked things up on OEIS (there's Olympics to watch right now, so I'll save looking for my own function/method later), and found https://oeis.org/A255070, which is the number of right turns (the 1s), and is related to things like the number of runs in the binary expansion. It also provides a way now to calculate it with hamming weight (aka bit count or popcount).

So we've gotten rid of all those pivot parity cases. But wait! There's more! Because at this point it occurred to me (while watching curling) that I'd been only zooming in on the fractal... what about zooming out? Because we just care about parity, the seed sections can be compressed to that bit. And here, the length of the input being odd comes into play again... since that makes the parity of seed combined with its complement odd, that means that they must have different parities... alternating and making the sequence a dragon curve. And if the seed has a parity bit of 0, then we've just wrote a function for the full data (we've got alternating 0/1s with the standard dragon curve in between them, meaning we've zoomed out to the same curve). Except... as I stated way up at the beginning, my seed has a parity bit of 1.

So, we have another little problem... we need to relate the parity function of the '0' curve with the curve starting from '1'. And as we've discovered, we know that they both have the same pivots and alternate the others (with opposite values there). So the original goes 0,a,1,b and the one we want goes 1,a,0,b... and that repeats every four. The only difference is that the one we want adds a parity bit on indices 0 mod 4, but the original delays until 2 mod 4 to add the same bit... but they're both the equal after every four (1+a+b). And so the change we need is to just add that early parity bit to results that are 0 or 1 mod 4.

But, what about even length seeds? They probably don't occur in inputs, but all my previous solutions could handle them. With even length, the seed blocks and their complement must have the same parity. So if the seed has 0 parity, we can just toss them all out and compress to the standard curve on the pivots. But if it's 1, then the blocks keep flipping parity... the combined result alternating 1/0. Which means the exact same adjustment we make for odd parity seeds works with both even and odd lengths! We only need to compress the index to ignore the seed blocks when things are even (zoom in).

And so we finally have all the pieces for my current solution.

https://pastebin.com/f06mZ1NQ

This was an excellent little math puzzle to play with. I really liked revisiting it. I did skip out on a bit and look up a result from OEIS, but I figure there's probably some recursive/dynamic way to calculate it too (because of the fractal self similarity... which just keeps coming up). It might not be as good, but I'm adding it as a TODO for later.

EDIT: I just realized that I should probably mention a portability issue for people that might want to transcode this. The calculated $index can be -1, and in Perl, -1 % 4 == 3, so this is fine. Not all languages behave that way (and might give a negative residue in that situation), so you might need to make that check positive with (index + 4) % 4.

Actually, two solutions side by side:

• The usual DP approach.
• Solve it as a system of linear equations, which I haven't seen anyone do.

​

import re
from sys import stdin


from scipy.sparse import csr_matrix, identity
from scipy.sparse.linalg import spsolve


matches = [0]


for line in stdin:
    line = line.strip()
    wins, have = line.split(": ")[1].split(" | ")
    wins = set(map(int, re.findall(r"\d+", wins)))
    have = set(map(int, re.findall(r"\d+", have)))
    matches.append(len(wins.intersection(have)))


N = len(matches) - 1


def dp():
    """Solve using tabular dynamic programming."""
    copies = [0] + [1] * N


    for i in range (1, N + 1):
        for j in range(i + 1, min(N + 1, i + matches[i] + 1)):
            copies[j] += copies[i]


    print(f"🂱 You get {sum(copies)} total scratchcards.")



def matrix():
    """Solve using matrix/system of linear equations."""
    w = [[0] * (N + 1) for _ in range(N + 1)]
    for j, k in enumerate(matches):
        for i in range(j + 1, j + 1 + k):
            w[i][j] = 1
    w = csr_matrix(w, dtype=int)


    i = identity(N + 1, format='csr', dtype=w.dtype)
    one = [0] + [1] * N
    copies = spsolve(i - w, one)


    print(f"🂱 You get {int(sum(copies))} total scratchcards.")  # type: ignore



dp()
matrix()

ETA: Actually 2022

This is the puzzle with data packets and comparisons. [1,1,3,1,1] etc

Link: https://github.com/LiseAndreasen/AdventOfCode/blob/master/2022/d13a.php

I am very happy with this solution. The code to create the small trees representing the packets turned out nice, and writing the compare function to work with usort was nice too.

Been doing AoC for a few years now and for some reason this day was giving me so much trouble. I think part 1 took me several weeks to get. Part 2 I came back to every so often to see if I could get it.

Initially I went with kind of a brute force design, trying to calculate every zero crossed left and right, and ever zero landed on, account for times when you start at zero, but everything I tried failed. I would consistently get the test input correct but fail on the full input.

I am a bit ashamed to admit it, but I turned to AI to talk through what was going on. Ultimately, I abandoned the suggestions I was getting and after a hint I saw in this sub, I went with the following:

public class Day01
{
    private readonly List<string> _input;
    public Day01()
    {
        _input = File.ReadAllLines(@"day01/input.txt").ToList();
    }
    private void partTwo()
    {
        int zeroCount = 0;
        int d = 100050;


        for(int i = 0; i<_input.Count; i++)
        {
            int turns = _input[i][0] == 'R'?int.Parse(_input[i].Substring(1)):-int.Parse(_input[i].Substring(1));


            if (turns < 0)
            {
                for(int j = d; j >= d+turns;j--)
                {
                    zeroCount += j%100 == 0 && j!=d? 1 : 0;
                }
                d += turns;
            }
            else
            {
                for(int j = d; j <= d + turns; j++)
                {
                    zeroCount += j%100 == 0 && j!=d? 1 : 0;
                }
                d+=turns;
            }
        }
        Console.WriteLine("Zero Count: " + zeroCount);
    }
}

I hope this helps someone else. The main idea was to start somewhere with a large amount giving me the ability to move along the number line using the amounts in the commands without actually going negative.

While not nearly as fast as folks can achieve using Python, here's a Google Sheet with 12 formulas that calculate the results and runtimes of both of the day's parts.

Advent of Code 2025

https://github.com/gitmartin/advent_of_code_2025/tree/main

This problem is somewhat related to the way regexps are implemented.

The first day required matching a set of rules forming a simple grammar. While I could do something smart based on the rule/input shape, I suspected that Day 2 would introduce some form of rule recursion so I went with a rather general approach: form a rule node tree and match input against it.

The second day introduced simple self-referencing rules. Having just written a node tree matcher, I just added a new kind of ref node making the tree into a graph, which I matched against. This recursive NFA regexp matcher ran in 0.5s.

Adding memoization on (rule_id, str_pos) made this run in 0.3s.

I played with converting the NFA to DFA (0.3s to 0.2s), implementing Thompson-style regexp VM (no perf advantages) and optimising the node graph (0.3 to 0.27s). Surpisingly, this gave no serious advantages at all but the code was getting a bit too hard hard to read.

So went with the original recursive NFA approach.

Tons of fun here. Anything else like it?

Revisiting old AoC challenges. I was looking around a bit and didn't see anyone solve it this way. All the solutions I saw are using one million integers to represent the grid. (But maybe I wasn't very thorough.) This solution uses rectangles represented by five integers each (left, top, right, bottom, and 'weight', which amounts to the brightness of a light), and computes rectangle intersections. Getting the coordinates of the spawned rectangles right is a bit gruelling.

Part 2 solution only. (Part 1 is almost the same.)

struct Rect: Equatable {
    var x1, y1, x2, y2, w: Int

    func weighted_area() -> Int {
        return (self.x2 - self.x1 + 1) * (self.y2 - self.y1 + 1) * self.w
    }
}


func parseLine(s: String) throws -> Rect {
    let m = s.matches(of: /(turn on|turn off|toggle) (\d+),(\d+) through (\d+),(\d+)/)[0].output
    var weight: Int
    switch m.1 {
    case "turn on":
        weight = 1
    case "turn off":
        weight = -1
    case "toggle":
        weight = 2
    default:
        fatalError("unreachable")
    }
    let x1 = Int(m.2)!
    let y1 = Int(m.3)!
    let x2 = Int(m.4)!
    let y2 = Int(m.5)!


    return Rect(x1: x1, y1: y1, x2: x2, y2: y2, w: weight)
}


func parseInput() -> [Rect] {
    var items: [Rect] = []
    while let line = readLine() {
        do {
            items.append(try parseLine(s: line))
        } catch {


        }
    }
    return items
}


func are_intersecting(p: Rect, a: Rect) -> Bool {
    return (a.x1 <= p.x2) && (a.x2 >= p.x1) && (a.y1 <= p.y2) && (a.y2 >= p.y1)
}


func apply_intersection(p: Rect, a: Rect, newPrecs: inout [Rect]) {
    let i = Rect(
        x1: max(p.x1, a.x1), y1: max(p.y1, a.y1), x2: min(p.x2, a.x2), y2: min(p.y2, a.y2),
        w: max(0, p.w + a.w))
    newPrecs.append(i)


    if a.x1 - 1 >= p.x1 {
        newPrecs.append(Rect(x1: p.x1, y1: p.y1, x2: a.x1 - 1, y2: p.y2, w: p.w))
    }


    if a.x2 + 1 <= p.x2 {
        newPrecs.append(Rect(x1: a.x2 + 1, y1: p.y1, x2: p.x2, y2: p.y2, w: p.w))
    }


    if a.y1 - 1 >= p.y1 {
        newPrecs.append(Rect(x1: i.x1, y1: p.y1, x2: i.x2, y2: a.y1 - 1, w: p.w))
    }


    if a.y2 + 1 <= p.y2 {
        newPrecs.append(Rect(x1: i.x1, y1: a.y2 + 1, x2: i.x2, y2: p.y2, w: p.w))
    }
}


@main
struct d06 {
    static func main() {
        let arecs: [Rect] = parseInput()
        var precs: [Rect] = [Rect(x1: 0, y1: 0, x2: 999, y2: 999, w: 0)]


        for arec in arecs {
            var newPrecs: [Rect] = []
            for prec in precs {
                if !are_intersecting(p: prec, a: arec) {
                    newPrecs.append(prec)
                    continue
                }
                apply_intersection(p: prec, a: arec, newPrecs: &newPrecs)
            }
            precs = newPrecs
        }


        print(precs.map({ $0.weighted_area() }).reduce(0, +))
    }
}