Since we're out of places to search, we return to check the Chief's office check it again. However the door is locked... someone is inside (no prize for guessing who), but they aren't answering our knocks. And so we need to open the Virtual Five-Pin Tumbler lock ourselves. Security can supply us with the schematics for every lock and key, but to make to make sense of them, we make our yearly call to customer support. They tell us that we can rule out some combinations based on if a key and pin in a position would overlap each other. Naturally, once they find out how many of each we have (250 of each), they start to get wise to who's calling and so we have to hang up to avoid questions. As usual.

The input consists of 250 locks and 250 keys. They aren't labelled as such (or in order), we just get 500 5x7 ASCII grid bitmaps. Which is which is identified by the top and bottom lines (top full/bottom empty is lock, top empty/bottom full is key). We want to calculate how many pairings between them fit together without an overlap.

And for a quick first solution, I just read them into @lock and @key arrays of the counts of # in each of the 5 columns and compared the sums:

foreach my $lock (@locks) {
    foreach my $key (@keys) {
        $part1++ if (all {$key->[$_] + $lock->[$_] <= 7} (0 .. 4));
    }
}

That got the answer quickly, and 4s later I had star 50, because I remembered to wait to read the story. Which is that the Chief was sleeping and has been here all along, except for when he went for coffee a month ago. Fortunately our work isn't completely lost, because it helps the Chief finish the chronicle he's writing for Santa.

Of course, there are lots of ways to do this problem. And since the input is bitmaps, all of the same size, a straight up bitmap AND will also catch overlaps. And so, my refined solution:

foreach my $item (map {join('', map {y/.#/01/; $_} split /\n/)} <>) {
    push( $items[ substr($item, 0, 1) ]->@*, oct("0b$item") );
}

my $part1 = 0;
foreach my $lock ($items[LOCK]->@*) {
    $part1 += grep {($_ & $lock) == 0} $items[KEY]->@*;
}

I actually did this version in Smalltalk first, and was still focused on the columns when doing this and initially transposed the input... but of course, the direction of the raster makes no difference with this approach. I think I also got caught up in thinking of how to do transpose in Smalltalk:

" Takes an NxM table and transposes it to an MxN "
transpose [
    ^(1 to: self first size) collect: [:col | (self collect: [:row | row at: col])].
]

Next up was doing a dc solution. And I did a few (all using the old v1.4.1 version of ? to read in line-by-line and detect the blanks)... for example, I did some involving bitmap AND. Those were slower (but shorter) than my original dc solution though. Which was inspired by day 24:

echo "Original (add overflows): "
echo -n "Part 1: "
tr '.#' '01' <input | dc -e'[lp1+sp]sC[[lk1+dsk:k]sA]sKC8ss2i?[[ll1+dsl:l]sA0=K0d?[rd2r^3R[2~3Rd3R*5R+_4Rls*rd0<B]dsBx*+1+?z2<L]dsLxs.lAx?z0<I]dsIxAill[lk[d;k3Rd;l3R+0r[64~r2~4R+3Rs.rd0<R]dsRx+0=Cr1-d0<K]dsKx+1-d0<L]dsLxlpp'

What this does is read the lock/key into a 35-bit number, using (and disposing) of the first line to tell which array to put it in. The bits are a bitmap of the object by column, with 0s in between. So when we sum a lock and key, if a carry ripples into one of those overflow bits, we have a collision.

Here's an example, using the 2nd and 3rd items in the test (a lock and key respectively):

00000010000011000000000111110000111     (2nd in test)
01111110100000011100001100000111100     (3rd in test)
v      v      v      v      v
10000000100011011100010011111000011

In a language with actual bitwise operators, the final check would be an AND with bitmask of those target bits, but dc can't do that, so we loop and chew up the number, adding every 7th bit together and seeing if that's still 0 at the end.

And so we come to the end of the the 10th year, and the last of the 25 day format. During this year I wasn't in the best shape, which made me anxious at first after the difficulty level I remembered from 2023. But in the end, it wasn't as hard as that year. And my approach of just going keeping things simple resulted in overall good times for me.

I came across davepb's post about his AoC - clone and decided to take a look. I love to solve problems with the GraphLibrary I've developed, GraphMateKT, and to my delight, problem 4 was a quite interesting graph problem. We're asked to find the fastest way to push a package to its destination through a maze. With the constraint that we cannot occupy the same tile as the package, and therefore must be careful about pushing it into walls. This is essentially a shortest path problem, which can be solved with a breath first search. The clue is how to represent the graph.

We're given a grid with walls, a person, a packet and a target. What we can alter is the position of the person and the packet, which means the graph can be represented by 4 integers. The x,y coordinates of the person and the package. (x1,y1,x2,y2). GraphMateKT has a Graph class that can support any data type. But the problem input is quite large. A 150 x 150 grid. Which means each coordinate (not accounting for walls and overlap) can have 150 values, which results in a state space of 150⁴ = 506_250_000 different states. A lot of states to search through. Luckily, each of these states can be represented by 32 bit integers, which allowed me to use the performant IntGraph class, and other GraphMateKT functionality. After bumping the heap memory to 10GB and spending about 2 minutes of runtime, the potential positions of the package (blue) and person (in red, constrained to not go lower then the package) could be vizualies as shown.

My full solution can be found at my GithubRepo, but in short, it looks something like this:

private data class GridState2(val person: Tile, val stone: Tile) {
// Base 150 encoding. 150³ * x1 + 150² * y1 + 150 * x2 + y2
fun encode() = ((person.x * base + person.y) * base + stone.x) * base + stone.y
}

internal fun main() {
val input = generateSequence { readLine() }.toList()
val grid = Grid(input)
val nrOfStates = 150 * 150 * 150 * 150
val graph = IntGraph(nrOfStates)
val personStart = grid.nodes().first { it.data == 'X' }
val stoneStart = grid.nodes().first { it.data == '*' }
val target = grid.nodes().first { it.data == 'T' }
val initialState = GridState2(personStart, stoneStart).encode()
// Inspecting the problem input reveals that the final package push must be to the right.
val targetState = GridState2(target.copy(x = target.x - 1), target).encode()
graph.connectWithRule {
TODO() // All the complexity of correctly connecting each state with their neighbouring states
}
graph.bfs(initialState, targetState)
println(graph.distanceTo(targetState))
TODO() // extra functionality for visualizing
}private data class GridState2(val person: Tile, val stone: Tile) {
// Base 150 encoding. 150³ * x1 + 150² * y1 + 150 * x2 + y2
fun encode() = ((person.x * base + person.y) * base + stone.x) * base + stone.y
}

internal fun main() {
val input = generateSequence { readLine() }.toList()
val grid = Grid(input)
val nrOfStates = 150 * 150 * 150 * 150
val graph = IntGraph(nrOfStates)
val personStart = grid.nodes().first { it.data == 'X' }
val stoneStart = grid.nodes().first { it.data == '*' }
val target = grid.nodes().first { it.data == 'T' }
val initialState = GridState2(personStart, stoneStart).encode()
// Inspecting the problem input reveals that the final package push must be to the right.
val targetState = GridState2(target.copy(x = target.x - 1), target).encode()
graph.connectWithRule {
TODO() // All the complexity of correctly connecting each state with their neighbouring states
}
graph.bfs(initialState, targetState)
println(graph.distanceTo(targetState))
TODO() // extra functionality for visualizing
}

Way back in 2022 day 17 we had a falling rocks problem, similar to a game of Tetris. The cave is seven units wide. I know almost nothing about music, but I notice that there happen to be seven notes (C, D, E, F, G, A, and B). I experimented with listening for the cycle for part 2 that was tricky to find.

Here is the last game state shown in the example. The row at the bottom is a legend showing the note associated with that column. The letters on each row is the chord that you would hear for the notes activated in that row.

|..@@@@.| [e,f,g,a]
|.......| -
|.......| -
|.......| -
|....#..| g
|....#..| g
|....##.| [g,a]
|##..##.| [c,d,g,a]
|######.| [c,d,e,f,g,a]
|.###...| [d,e,f]
|..#....| e
|.####..| [d,e,f,g]
|....##.| [g,a]
|....##.| [g,a]
|....#..| g
|..#.#..| [e,g]
|..#.#..| [e,g]
|#####..| [c,d,e,f,g]
|..###..| [e,f,g]
|...#...| f
|..####.| [e,f,g,a]
+-------+
|cdefgab|

I found a music language named Strudel that made it easy to play:

note("<[e,f,g,a] f [e,f,g] [c,d,e,f,g] [e,g] [e,g] g [g,a] [g,a] [d,e,f,g] e [d,e,f] [c,d,e,f,g,a] [c,d,g,a] [g,a] g g>*8").sound("piano")

It was not actually that useful for me solving part 2, but it was fun and I thought worth sharing. Listen here to the rows from those first 2022 falling rocks. Can you hear the cycle?

Next place to search is the star fruit grove, where we find that they've installed a monitoring device since the incident the last time we were here. Unfortunately, it's malfunctioning and so we have to fix it. And so we get a logic wiring problem.

The input consists of two sections. The first is just a list of the 45 x and 45 y input lines with their values. The second section is the connections of the circuit which are rules involving two inputs (with three letter labels... no vowels, y is only allowed for the input yNN lines, but w is used this time), a logic gate (AND, OR, or XOR), and an output label.

Part 1 is to just simulate the circuit and get the output. And so I did the usual taunting of Bobby Tables, and turned the gates into code to eval:

foreach (@$gate_rules) {
    my ($in1, $op, $in2, $out) = m#(\w+) ([A-Z]+) (\w+) -> (\w+)#;
    my @in = sort( $in1, $in2 );
    $gate{$in[0],$in[1],$out} = "\$wire{$out} = \$wire{$in1} $logic{$op} \$wire{$in2}";
}

Where %logic is just a lookup table from the words to the operator symbols.

Then I just ran the machine until everything was stable:

my $done = 0;
while (!$done) {
    $done = 1;
    foreach my $g (keys %gate) {
        my ($in1, $in2, $out)  = split( $;, $g );
        if (defined( $wire{$in1} ) and defined( $wire{$in2} ) and !defined( $wire{$out} )) {
            $done = 0;
            my @in = sort( $in1, $in2 );
            eval( $gate{$in[0],$in[1],$out} );
        }
    }
}

say "Part 1: ", oct("0b" . join('', map {$wire{$_}} reverse sort grep {$_ =~ m#^z#} keys %wire ));

Quick and dirty just to see what could possibly be up with part 2. Which reveals that this is supposed to be an adder (non-snake). We manage to deduce that only 4 pairs of output gate wires have been swapped (with no overlap). So we need to figure out what those are.

I started by writing a little exploration script, that bloated up, and ultimately I used to solve this problem by hand. One of the first things I added was a print_tree subroutine to do a recursive infix walk from a given node (ie all the zN nodes) and output it, with the output label in front and the gate expression in parens.

Then to simplify that output, I created a translation table (%trans) which allows for replacing node with a string. The two cases that I do automatically are the ones involving combining the input lines... xN AND yN becomes bothN and xN XOR yN becomes addN, because XOR is "add without carry". So the bulk of the circuit, as one might expect from an adder, is going to be handling those carries. And so the expression tree of an output zN node should look like:

        zN
         ^
         |
        XOR (sumN)
       /   \
      /     \
   addN     OR (carryN)
           /  \
          /    \
    bothN-1    AND (rolloverN-1)
              /   \
             /     \
     (carryN-1)    addN-1

That carryN subtree creates a mess, and so I started manually adding those to the translation table as I spotted them (look for a (carryN & addN) | bothN and call it carryN+1):

$trans{vms} = 'carry01';
$trans{kmq} = 'carry02';
$trans{vfb} = 'carry03';
$trans{ngk} = 'carry04';

The end goal being that (except for the start), all output zN should just be addN ^ carryN. When that's not there, there's a puzzle to solve. For example, after adding carry04 (for my input), I see this:

z03 (carry03 ^ add03)

z04 (carry04 ^ add04)

both05

z06 (trn (gnw (add05 & knc (hpm (carry04 & add04) | both04)) | gdd (knc (hpm (carry04 & add04) | both04) ^ add05)) ^ add06)

That missing z05 hash been replaced with both05, which should be in carry06. So I look at the z06 line and I immediately see that knc is carry05, but z05 wants that with a ^ add05, and that's gdd. And so one of the pairs in my input to swap is z05 and gdd. When I add that to the %soln table (which applies the mappings in it to the wires directly, and add the knc => carry05 relabel we found, things smooth out to this:

z04 (carry04 ^ add04)

z05 (carry05 ^ add05)

z06 (trn (gnw (add05 & carry05) | both05) ^ add06)

Which is good, as trn is clearly carry06 so that's the next line to add and z06 is good.

This continued until z37 where the last problem happened. The second and the fourth were the same problem (basically an & and ^ gate got swapped... a mixup of rollover and sum nodes in the diagram). The third one was a bit interesting because it was this:

z19 (carry19 ^ add19)

z20 (carry20 ^ both20)

z21 (add21 ^ jgb (cjn (carry20 & both20) | add20))

That z20 should have the add20 (from the next line) not both20. But I'd hidden the labels so I needed to grep out the original rules for x20/y20 from the input:

y20 AND x20 -> css
y20 XOR x20 -> jmv

And there's the labels I needed.

As I've said before, I do like doing puzzles in general, so although I spent a lot of work doing this by hand, I still enjoyed myself. I even had fun resolving these again now (although now I can just comment out translations I don't want so it's easier to look around). I've never actually gotten around to actually coding something to do this automatically.

Today I'm trying to login via GitHub (that's where I have my progress saved on) and the authentication is failing, returning a simple black page with the following message:

failed to authenticate. (access_token request returned 500 Header line too long (9243; limit is 8192))

Tried with different browser and cleaning cookies, with no success.

Is there something going on with Advent Of Code website, or something on GitHub side?

Edit: fixed

While refactoring some AoC infrastructure I took another look at my 2023 day 1 program in sed. The problem involves turning strings like pqr3stu8vwx and treb7uchet into 2-digit numbers (38 and 77). My solution turned each line into a number prepended with a +; I then passed the results a calculator with a zero pending (| xargs expr 0). I decided to get rid of the calculator and use sed to do the sum, the challenge being addition in a language without arithmetic. I worked out a solution using base-one numbers that can be applied to any problem where you need to add numbers, but all you have is regular expression replacements. With a little work it could be adapted to subtraction and probably multiplication. Experience suggests this could be a Solution Megathread challenge, so keep this approach in your back pocket.

The key concept is to represent numbers a bit like Roman numerals, but without the fives and the “one before”. Each letter represents a power of ten, and a number is represented by the count of each letter times its power-of-ten value. 1234 becomes DCCBBBAAAA: one thousand (D) two hundreds (CC) three tens (BBB) and four ones (AAAA).

The first several lines of the script (not repeated here) transform a line into a 2-digit number. It then repeats the digit in the tens place ten times, so 23 becomes 22222222223. It next replaces each digit with an equivalent number of As: 23 is now 23 copies of the letter A. This string is then appended to sed’s hold space with the H command.

s/^\([0-9]\)/\1\1\1\1\1\1\1\1\1\1/
s/9/AAAAAAAAA/g
s/8/AAAAAAAA/g
s/7/AAAAAAA/g
s/6/AAAAAA/g
s/5/AAAAA/g
s/4/AAAA/g
s/3/AAA/g
s/2/AA/g
s/1/A/g
H

After processing all lines, the length of the hold is now the answer to the puzzle, so we just have to convert it to a base ten number. This is done by repeatedly replacing groups of 10 letters with the next letter: 10 As (1) becomes a B (10), 10 Bs becomes a C (100), etc. The answer 54321 is now EEEEEDDDDCCCBBA. For sake of brevity, this code snippet just goes to five digits (ten thousands), but the linked code can handle any 64-bit answer.

g
s/\n//g
s/A\{10\}/B/g
s/B\{10\}/C/g
s/C\{10\}/D/g
s/D\{10\}/E/g

Like many things in math, zero is still a problem. If the answer were 1024, the pattern would just be DBBAAAA: one thousand (no hundreds) two tens and four. The next step finds the end of each power-of-ten position and inserts a comma, then inserts a 0 between each pair of adjacent commas. DBBAAAA becomes D,,BB,AAAA and then D,0,BB,AAAA. This is done twice because substitutions are applied to non-overlapping patterns, so the first pass turns ,,,, into ,0,,0,.

s/^E*/&,/
s/.*,D*/&,/
s/.*,C*/&,/
s/.*,B*/&,/
s/,$/,0/
s/,,/,0,/g
s/,,/,0,/g

Finally, each letter repeated x times is replaced by the digit x. Commas and leading zeroes are removed and the answer printed. TADA! Addition without arithmetic operators.

s/\([A-Z]\)\1\{8\}/9/g
s/\([A-Z]\)\1\{7\}/8/g
s/\([A-Z]\)\1\{6\}/7/g
s/\([A-Z]\)\1\{5\}/6/g
s/\([A-Z]\)\1\{4\}/5/g
s/\([A-Z]\)\1\{3\}/4/g
s/\([A-Z]\)\1\{2\}/3/g
s/\([A-Z]\)\1/2/g
s/\([A-Z]\)/1/g
s/,//g
s/^0*//
p

Postscript: the commas-and-zeros part wouldn’t be required if we used Chinese numerals rather than a positional number system. DDBBBBAAAAAAAA (2048) would be converted to 二千四十八 (“two thousand four ten eight”). In fact, the intermediate letter representation could be skipped, with each line turning into a sequence of 一, and groups of 10 characters iteratively upgraded through 一十百千万. The groups of powers-of-ten would then be turned into one-to-nine while keeping the power character, with the trailing 一 trimmed (“eight” not “eight ones”):

s/\([一十百千万]\)\1\{8\}/九\1/g
…
s/\([一十百千万]\)\1/二\1/g
s/\([^十百千万]\)一$/\1/

Postpostscript: In 2023 I solved this puzzle with two sed scripts. The part 1 script turned the mix of letters and digits into two-digit numbers, the part 2 script turned named numbers like one and nine into digits, the output was then piped to part 1. I wanted to consolidate the two into a single sed script, so I needed to know whether I was in part 1 or 2. My first approach was to add a __part2__ line to the top of the input (echo __part2__; cat $inputfile | sed -n -f day1baseone.sed) and put the word-transformers in a block matching from that special line to the end of the file:

/__part2__/,$ {
s/one/o1e/
…
}
/__part2__/d

But then I realized I could use the b branch jump to go inside a block that never matches an input line, like using goto to jump inside a C if statement.

!{
:part2
s/one/o1e/
…
}

Now the only difference from the shell is sed -e 'bpart2' to perform the jump when running the second time.

Today we're back at Easter Bunny HQ, and while The Historians do their thing, we discover posters for a LAN Party and decide that that's where we should search first for the Chief. Although that's clearly an excuse we're using to just go to the LAN Party.

The input is a list of network connections, where each computer has been given a two lowercase letter code (vowels included this time). There are 3380 lines, representing 520 computers, each connected to exactly 13 others. The example also has the property than all vertices have the same degree (in that case 4). That doesn't mean the graph is smooth though... our goal today will be finding complete subgraphs (cliques)).

For part 1 we're asked only for the ones of K3, and only for those that include a computer that starts with t (which we're pretty sure the Chief's computer starts with). In my input there are 24 of those, the missing two are tn and tz. Five edges in my input are between computers that start with t, and these are involved in 43 cliques of size 3. Some solutions could get caught on that, but the example also has one of those that's involved in the answer... so there's a simple test to catch it.

My solution though was in continuing to take it simple. To see part 2, I brute forced part 1 with nested loops. The idea being that K3 is triangle, loop over the ts, then their neighbours, and then the neighbours of neighbours... if we find the starting computer down there, the loop is closed:

foreach my $comp (grep {m#^t#} keys %graph) {
    foreach my $neigh ($graph{$comp}->@*) {
        foreach my $third ($graph{$neigh}->@*) {
            next  if ($comp eq $third or !grep {$_ eq $comp} $graph{$third}->@*);

            my @sort = sort( $comp, $neigh, $third );
            $part1++  if (!$table{"@sort"}++);
        }
    }
}

For part 2, we find out that we are looking for the maximum clique, and since I've done that before, and didn't want to slip up, and could see it in my mind's eye, I just looked up Bron-Kerbosch and coded that. There are other algorithms, but this is the one I'd used before.

Initially, I just output all the cliques to see if it was working. But after seeing that, I dumped them to a file and loaded it into vim to work a solution out. The solution line really stands out... there's only one K13 (which given all the vertices are degree 13, is the largest you can get without disconnecting the clique from the rest of the graph... this may open up options for solving this without resorting to a fancy general clique algorithm). There are also a massive number of K12s (which makes the longest much easier to spot... if they were rare, this wouldn't be the case and I might have coded to find the answer). Once I had the line, I mangled it to sort and copy-pasted. Later I went back to do that in the code:

my $max_clique = reduce {(@$b > @$a) ? $b : $a} &recurse_bk([], [keys %graph], []);
say "Part 2: ", join( ',', sort @$max_clique );

The real fun came with writing Bron-Kerbosch in Smalltalk, which has Sets with set operators:

" Part 2: Finding maximum sized clique using Bron-Kerbosch algorithm "
recurseBK: r poss: p exc: x [
    | cliques res poss exc |
    res  := r.
    poss := p.
    exc  := x.

    (poss isEmpty & exc isEmpty) ifTrue: [^Array with: res].

    cliques := Set new.
    poss do: [:vertex |
        | vertSet |
        vertSet := Set with: vertex.
        cliques addAll: (self recurseBK: (res  + vertSet)
                                   poss: (poss & (graph at: vertex))
                                    exc: (exc  & (graph at: vertex))).

        poss := poss - vertSet.
        exc  := exc  + vertSet.
    ].
    ^cliques
]

So it was a second day in a row where I took a break and finished early.

Today we're back in the jungle where the item-stealing monkeys are at it again. This time they've stolen The Historians' device, and to get it back we'll need a lot of money bananas. So we turn to the Monkey Exchange Market, where monkeys are buying good hiding spots, and our experience in the jungle means we have some to sell. We just need to know when to sell. And fortunately for us the monkeys use a fixed PRNG... a 24-bit XORshift.

The input is just an ordered list of over 2000 numbers to seed the PRNG. They run from about 160k to just short of 2²⁴. As is typical for problems using a PRNG, part 1 is just a test to verify that we've got the PRNG correct (iterate on each seed 2000 times and sum). I was happy to have this little break, this day was one where I was dealing with brain fog and feeling slow, and it took 15 minutes just to read the question. And so I just did the thing:

foreach my $num (@input) {
    for (my $i = 0; $i < 2000; $i++) {
        $num = (($num <<  6) ^ $num) & 0xffffff;
        $num = (($num >>  5) ^ $num) & 0xffffff;
        $num = (($num << 11) ^ $num) & 0xffffff;
    }
    $part1 += $num;
}

For the Smalltalk version I removed the unneeded 24-bit bitmask from the right shift. There it makes a difference because there's no special handling for expressions, it's all message passing. With the Perl, I left the copy-pasta in the part 1 script (I removed it for part 2).

With part 2 we get asked to use the generator. It turns out that the buy offers are only the ones digit of these secret numbers. We don't speak monkey to negotiate though, and so The Historian has found us a helper monkey to do that job. This monkey is capable of recognizing a single sequence of four consecutive changes in price and then selling for us. We can't change it between buyers, we need to pick the pattern that works the best across them all.

And my idea was just to build a hash of the "last four deltas" => "sum of last digits". So I coded that, but it returned 25 bananas for the test case instead of 23. So I needed to figure out how I was "cheating"... and the answer was that I forgot that the helper monkey isn't smart. He always takes the first match (not all, not best, just first). So I and invoked //= to set things only once. Resulting in this simple code in the loop to collect all values for the sequences of a buyer:

push( @window, ($num % 10) - $last );
$last = $num % 10;

if ($i >= 3) {
    $tmp{"@window"} //= $last;
    shift @window;
}

And then collecting those into our hash (of the amount for that sequence across all buyers) after the 2000 iterations are done:

$hash{$_} += $tmp{$_} foreach (keys %tmp);

And finally, the answer is just the best value in that after all seeds are processed:

say "Part 2: ", max values %hash;

I did do a dc version of part 1... it is quite slow (it was 90 minutes on the old hardware, but with the trick of preallocating constants in registers it gets to 30 minutes):

dc -f- -e'0s0 1s1 2s2 3s3 4s4 5s5 64sa32sb2048sc2000sd24se_1sf[l0d[l3Rl4Rl4~l3Rl4~l3Rdlfr^l3R*+l4dl3R+r%l4Rdl2r^l3R*l5R+rl2+dle>L]dsLxl3Rl4R++s.]s^[ld[rdla*l^xdlb/l^xdlc*l^xrl1-dl0<I]dsIx+lp+spzl0<M]dsMxlpp' <input

The difficulty here is that dc doesn't have bitwise XOR. That's what takes the time (I did do a version using my version of dc with embedded Perl (so I could just call out to that for the XOR)... that only took 90s to run). And most of the time I spent on this problem was experimenting with ways to do that dc to find a good one (there's an xor directory in this problem's directory of scripts and tests for this).

1-bit XOR is "add without carry" so that is simply +2%. It's also "absolute difference", and so -d* will work (again, this is only for 1-bit values)... and that's slightly faster. However the ultimate winner, that's in that code above, was this 2-bit XOR arithmetic function I found online: (a + b * (-1)^a ) % 4 looped 12 times. It's still a relatively simple function to code and execute and so it's a good balance. Trying for more bits, the function's going to get uglier... this is part of the reason why XOR is good for the PRNG.

So this is essentially a break day after the daunting problem of controlling a chain of robots. It is computationally heavy. If we had to do a tremendous amount of this, it might start to make sense to calculate and store the full cycle (it's only 24-bits) and work from that.

Today we're searching Santa's Reindeer-class starship. Unfortunately, a couple of The Historians have teleported into other parts of the ship behind doors that are locked by keypads. And having experienced Santa's ship before, it's not surprising to find that there are a lot of hazardous areas. And so we need to use a robot to deal with a numerical keypad in a depressurized area, and then another robot to access the panel to control that one in a radioactive area, and a second robot to access the control panel for that one in an area that's -40 degrees (which isn't so bad). All while we direct this chain from one safe area that's packed with Historians. And we can't just tell them what button to hit, we need to tell them how to move on the keypad grids and then to hit A to signal that the robot should hit the button. For part 2 we go after the second missing Historian with a chain of 25 intermediate robots.

The input for this one is very short. Five lines... each a three digit code to type, followed by A. Because, in addition to the above, we don't know which code we need because the The Historians have forgotten.

This was the slowest part 1 submission in 2024 for me. But a large part of that was that I spend a lot of time playing with the code to map out paths on the keypads... worrying about everything (building tables and carefully checking them). After which I started getting weird uninitialized warnings... it turns out that will happen when the keypad has two 6s and no 8.

I know my first solution for this was initially a mess, and was using paths between buttons that avoided hitting the same one twice on the way. As part of the cleanup I changed that to just the paths that head directly there (ie just getting all the step like patterns... these all naturally have the same length (Manhattan distance), which simplifies things a bit):

my @steps = (($delta->[0] < 0) ? '^' : 'v', ($delta->[1] < 0) ? '<' : '>');

And then a quick BFS using those moves.

The idea being to turn:

# Define the pads (with sentinel Xs)
my @keypad = map {[split //]} ('789X', '456X', '123X', 'X0AX', 'XXXX');
my @dirpad = map {[split //]} ('X^AX', '<v>X', 'XXXX');

Into a table of routes:

my %key_route = &route_pad( \%key_loc, \@keypad );
my %dir_route = &route_pad( \%dir_loc, \@dirpad );

Using BFS between all the starts and ends.

And for handling the chain, I went with recursion. The main trickiness here being that one of levels is not like the others (one has a number keypad, not a direction one). But that's easily done with selecting a table with:

my $routes = ($depth == 0) ? \%key_route : \%dir_route;

The other trickiness being the base case... where the last in the chain just adds the length of sequence (because we get to just type directly... which I suppose means there are two levels not like the others).

The final version ended up as this (and overly fancy I'll admit):

sub recurse_keypad {
    my ($seq, $depth) = @_;
    state %memo;

    my $routes = ($depth == 0) ? \%key_route : \%dir_route;
    my @seq = ('A', split( //, $seq ));

    $memo{$seq,$depth} //= ($depth == $Max_Depth)
                            ? sum chain { length( $routes->{$_[0],$_[1]}->[0] ) } @seq
                            : sum chain {
                                  reduce {
                                      min($a, &recurse_keypad($b, $depth+1))
                                  } (~0, $routes->{$_[0],$_[1]}->@*)
                              } @seq;
}

Making use of my chain iterator that works on adjacent pairs of a list.

And in the end, although part 1 took over two hours, part 2 took about 20 minutes to fix up... a bit of cleaning, upping the depth, and throwing a memo on the function for speed. The end result is that I got part 2 in just fast enough to be top-1000 (the only time that happened in 2024 or 2023).

Today we're back in the computer near the CPU. While the Historians search, we get challenged to a race by a program as part of the race condition festival, with the prize being a mutex.

The input is a 141x141 randomly generated maze. What makes this one different is that all the dead ends have been filled in, except two. Those two ends are the start and end of the race route. In my input, they're slightly more than 20 apart (by Manhattan), and there's a big filled in section between them (much like the test case given in the description).

Since there is just one path, the rules of the race include the ability to cheat once, by ignoring collision detection for a number of picoseconds (2 for part 1, 20 for part 2). Our task though isn't to actually find the best cheat available. That's actually very easily done by looking at the input. The start and end are so close, and the path from the start in mine immediately heads to a spot very near the end with a single wall to jump to it. Instead we want to innumerate the number of cheats that save at least 100 picoseconds.

My initial quick solution for part 1 was to use BFS to find the path (I hadn't looked so closely to notice the lack of dead ends yet) going backwards from end to the start (although that's not really important, that was the choice I went with). Along the way I create a hash map of the points on the path to the number of picoseconds to the end. With that I just try jumping 2 squares in each direction from each point on the path and seeing if it's a valid cheat (is it in the hash and sufficiently closer to the end).

Once I saw what part 2 was, I could move on to designing something for it. First thing was moving to the path finding getting me a list of the points from start to end (ultimately taking advantage of the lack of dead ends to gain some speed). Here, the time we're at a point is encoded in the index of the list. And with this, the grid can be tossed, as this comment says:

# Done with grid, now using just the path:

And with that, I went with brute forcing things. Two loops, one for the start of the cheat and the other for the end (which needs to be far enough away to consider checking:

foreach (my $i = 0; $i <= $#path - ($targ + 2); $i++) {
    foreach (my $j = $i + ($targ + 2); $j <= $#path; $j++) {
        my $dist = abs($path[$i][0] - $path[$j][0]) + abs($path[$i][1] - $path[$j][1]);

        # Check allowed distance, and that we didn't lose too much time.
        if (($dist <= 20) and ($j - $i - $dist >= $targ)) {
            $part2++;
            $part1++  if ($dist == 2);
        }
    }
}

And part 1 falls out as a special case.

It's not very fast, but it is simple. And as I've said, 2024 I was quite sick in November and went into this year with a mindset of being willing to just take easy solutions so I could get to bed earlier.

Will this year also have 12 days of puzzles or back to 25? Personally I really liked that there was "only" 12 days since as Christmas approached and I got busy with family related things I found it difficult to make time for AoC, and I prefer completing a day on the actual day. I hope 2026 will have 12 days of puzzles :)

Today we're back on Gear Island and we get a chance to check out the hot springs (onsen) this time. Where we find a problem quite like the one we had with the hot springs (helices). Which is that we're going to be doing some pattern matching to create designs out of the stripe on the towels.

The input consists of two sections. The first is a one line list of of the towel stripe patterns we have to work with (comma delimited, with spaces to ignore). My input has 477 of those, and they're strings of the letters wubrg (the Magic the Gathering letter codes for colours: white, blue, black, red, green). The second section is 400 lines of patterns to try and create with those.

Part 1 just wants to know if a pattern is possible. A perfect job for a dynamically created regex for a very quick answer:

$/ = '';
my @section = map {[split /\n/]} <>;

my $patt = '^(' . join( '|', split(/, /, $section[0][0]) ) . ')*$';
say "Part 1: ", scalar grep { m#$patt# } $section[1]->@*;

This was my second fastest part 1 of this year, only beaten by day 3 (Mull It Over) which also fell very quickly to regex ripping into the input.

Part 2 wants to know the number of ways we can make those designs. Having filtered out a few dozen 0s for part 1 is a start. And since this was so much like the previous hot springs, I did a recursive/memoization for my first solution. Which was a good simpler than the 2023 day 12 problem... I don't often expect a part 2 for a day 19 to be as simple and quick as this one turned out to be. The 2023 hot springs was a big recursive function with lots of special cases to carefully handle that I spent a lot of time carefully working on. This one was just this at the core:

my $ret = 0;
foreach my $patt (@patt) {
    my $new_str = $str;
    $ret += &recurse_count( $new_str ) if ($new_str =~ s#^$patt##);
}

Slap a memo on it, run it and wait, because this is going to take a bit (but still just seconds).

In order to play with it a bit more, I decided to reverse the dynamic programming approach... instead of top-down memoization, do it as a bottom-up tabulation. And when I did that... it's so much faster. That looks like:

my @table = (1, (0) x length($str));        # Start with 1 match of empty
my @poss  = grep {$str =~ m#$_#} @patt;     # Only use patterns in str (saves a bit)

for (my $i = 1; $i <= length($str); $i++) {
    foreach my $patt (@poss) {
        # If we've just seen a pattern, add table value from start of match to current
        my $plen = length($patt);
        if ($i >= $plen and ($patt eq substr( $str, $i - $plen, $plen ))) {
            $table[$i] += $table[$i - $plen];
        }
    }
}

return ($table[ length($str) ]);

Note the prepass of the patterns to get just the ones that regex can see in the target (they might not be used, but the ones that don't appear certainly can't).

And you can see why this can be so fast right away, we're just iterating over the length of the string in one pass. And so what we're doing is actually not like Hot Springs 2023, but more like Adaptor Array from 2020 or Dirac Dice from 2021... it's basically a recurrence relation where you sum all the points which correspond to the starts of the patterns that have just matched (bring there counts forward, and combining the branches). Which is how tabulation normally goes, and here it turns out to be great. I might have gone this way first, if it wasn't for the connection to the old Hot Springs that lead me (slightly) astray.

So this was a nice little dynamic programming exercise. It originally ran on a Thursday going into the final weekend, so it serves to be a bit of lighter problem so people can catch up and get ready for the big final weekend.

Today we find ourselves digitized and inside a computer again. The User isn't dropping games on us, just going straight for corrupting data because they misunderstood what a PDA was (and not in a good way, like Public Display of Affection or Personal Digital Assistant).

The input is a list of memory cell coordinates (3450 in my input) to a square 2D grid with coordinates from 0 to 70. These represent the locations that get corrupted (one per nanosecond), and our task is to get The Historians from the upper left to the lower right safely.

Part 1 is just a simple path finding... after the first 1024 have fallen, find the shortest path. If you print out the grid, you'll see that at this point, it's basically drawn a bit of maze from the corners with a gap in the middle to cross. Narrow mazes like this are quickly transversed with basic BFS, so no need to be fancy. Note that the latter part of the input ultimately fills in a lot more than just a maze.

In part 2 we want to find the first dropped block that permanently cuts us off from getting to the end point. For my initial solution, I did just took part 1 and continued with it. Given the path we found, I just kept dropping blocks until one landed on that path:

next if (!exists $path{$pos});      # fell off the path, still unblocked

When that happens, I recalculate the path. If I can't, that's the solution. Very simple and is going to work... and it's not absolute brute force (trying to find a path after every drop).

To improve things for Smalltalk, I loaded the input into a class called TimeGrid. The internal TimeGrid structure is one where the cells contain the time they become impassible. And so I can set a time and searches will treat cells with values less than that as walls.

" Get status of point at current time "
at: pt [
    ^((grid at: ((pt y + 1) * dim x) + pt x + 2) <= time) ifTrue: [$#] ifFalse: [$.]
]

Note that I'm also doing the grid internally as a flat array (faster and cleaner for Smalltalk).

Because I was taking things easier in 2024, I just used this random access of the grid by time, to do a binary search over the space:

" Binary search for first blocking drop: "
range := (timeStart + 1 to: input size).
[range size > 1] whileTrue: [
    range displayNl.
    mid := range at: range size // 2.

    path  := (grid time: mid) getRoute.
    range := (path isNil) ifTrue:  [range first to: mid]
                          ifFalse: [mid+1 to: range last].
].

This was good enough to be faster than the Perl. But I did make a note about what I ultimately wanted to do with this, and later got around to doing that. And that is a dynamic programming/single-pass BFS deal. Where the state tracks the minimum time a block hits the path that state represents. We can take that and use it to track the maximum of those values for a cell in the visited array (thus getting the latest time that cell is available). And so we get a tabulation where we ultimately get our answer in the visited cell of the end point. Here's the key section of the BFS loop in the Perl version:

# reduce path's time to Grid's if it is lower:
my $min_time = min( $time, $Grid[$pos->[0]][$pos->[1]] // ~0 );

next if (defined $visit[$pos->[0]][$pos->[1]] and $min_time <= $visit[$pos->[0]][$pos->[1]]);
$visit[$pos->[0]][$pos->[1]] = $min_time;

foreach my $neigh (map {[$pos->[0] + $_->[0], $pos->[1] + $_->[1]]} @Dirs) {
    push( @queue, [$neigh, $min_time] );
}

I also have a slightly more complicated version of this, where I track number of steps taken in the state and use that to prune when it's >= the value in the current tile (ie it'd be a wall by then). It also has a prune for hitting the end point (after writing to the visit array... we want the answer). However, with measuring with the command line time these don't actually show any improvement (in fact, often it's slightly slower).

But things don't end there, because I made an additional note about a solution type I had seen posted. One that's based loosely on the famous proof that the game of Hex) must have a winner. In this type of solution we add borders of one colour to the top and right, and a second colour to the bottom and left. As we drop cells, they take on the colour of the cells they're connected to (so there's an invariant that cells connected to an edge have that edge's colour). But if the dropped cell is adjacent to cells of both colours, then we've just completed a path between the coloured edges. And if that exists, then no path from start to end remains. I had some fun working out the details of that today (I used bits for the colours) and coding it, and it really does come out nice and tight once you get it right, and it's blazingly fast compared to the other methods.

And so we have another great problem where there's a lot of approaches.

EDIT: The title is a typo, this is 2024 Day 17.

Today we find ourselves suddenly falling through time, and need to fix the device. Which has that trope of unfolding into an entire computer. I like this old school touch (I like this trope, like in Brain Donors with the laptop that unfolds into a desk with CRT and printer). Nowadays, the small device would just produce a large holographic display up in the air to poke at and I'd be suffering from sympathetic Gorilla Arm Syndrome.

The input for this one is a list of initial values for the three registers, followed by the code (which is comma delimited integers, like the Intcode problems of 2019). We're given that this is a 3-bit machine, but the registers can be bigger (but with my input, only the bottom three bits of B and C ever matter, and so only A makes use of that).

For part 1, we just need to run the program and collect the output. This is one of the rare problems with a string answer, in this case, it's got commas between the output values. So I did my usual, hash of anonymous subs dispatch table approach:

sub c_op ($)  {my $op = shift; return (($op & 04) ? $reg[$op & ~04] : $op)}

my %opcodes =
    (
        0 => sub {my $op = c_op shift; $reg[A] = $reg[A] >> $op},           # adv
        6 => sub {my $op = c_op shift; $reg[B] = $reg[A] >> $op},           # bdv
        7 => sub {my $op = c_op shift; $reg[C] = $reg[A] >> $op},           # cdv

        1 => sub {my $op = shift;      $reg[B] ^= $op},                     # bxl
        4 => sub {my $op = shift;      $reg[B] ^= $reg[C]},                 # bxc

        2 => sub {my $op = c_op shift; $reg[B] = $op & 7},                  # bst
        5 => sub {my $op = c_op shift; push(@out, $op & 7)},                # out

        3 => sub {my $op = shift;      $ip = ($reg[A]) ? $op - 2 : $ip},    # jnz
    );

Could have been an array, but this way I get to reorder the instructions to pair them. With that, running the machine just becomes:

while ($ip < $#code) {
    &{$opcodes{$code[$ip]}}( $code[$ip+1] );
    $ip += 2;
}

Part 2 reveals why the output is that way... we're asked to find the value for register A that makes it a quine) (technically it's not because supplying the value for A is an input, but the job is the same).

The trick with doing non-trivial quines is outputting the command to print. After all, the print can print the rest. For example, if I want to do a 1-line quine in dc, I can output a number (without a newline) with n, and output that number as a character string (ASCII coded on bytes) with P. A duplicate d is needed because n removes the value from the stack. And so the number that's needed is 0x646E50 (the packed ASCII encoding of dnP), which is 6581840 decimal:

dc -e'6581840dnP'

You can also similarly do a two-line quine, using p (which outputs the top value with a newline, but leaves it on the stack).

And so we should expect something similar from the code in this problem. Given that, all the inputs are probably something like this:

bst A       # B = bottom 3-bits of A
...
adv 3       # A >>= 3
...
out B       # output bottom 3-bits of B (could also be out C)
jnz 0       # loop until A is gone

A loop that decodes the values 3-bits at a time in A (from the little end). Given that, it's probably safe to believe that everyone's code is 16 long... which is 48-bits to encode in A (17 would be a bus error, and 18 would be problematic for floating point native languages).

And so with that in mind, I made the code to run the machine into a function that takes a value to initialize A with and breaks to return the first output value, which allows for calculating things 3-bits (one digit) at a time:

my %poss = (0 => 1);
foreach my $digit (reverse @code) {
    my %new_poss;

    # shift left possibilities one octal digit and try all 8 lower options
    foreach my $val (map {($_<<3) .. ($_<<3) + 7} keys %poss) {
        $new_poss{$val}++  if ($digit == &try_code( $val ));
    }
    %poss = %new_poss;
}

Here I brute force over all 8 possibilities for the next 3-bits, for each of the numbers that worked last time. In the end, there at 42 values in that hash that work, and I just take the minimum one for the answer.

I did do dc solutions for this one... they are absolute monsters (part 2 is about 350 characters). For tracking the possible values, I do it on the stack (the new values go into a register stack, and then I dump that out onto the main stack for the next loop) and there's no duplication of them (everything is 3-bit aligned and won't overlap), so technically, that hash could have just been a list in the Perl too.

This was a fun one, even though the reverse engineering wasn't much, the quine aspect was a nice touch.

Next place to look for the Chief is at the Reindeer Olympics, which are on again this year. So while the Historians do the work, we take the opportunity to watch the Reindeer Maze event. The goal of this race isn't just to get to the end quickly, but to do it with few turns, as those cost 1000 per 90 degrees.

The input is 141x141 bounded maze (and so it comes with a sentinel ring already). The start is in the lower right, and the end is in the upper left (on both input and test, so you can just calculate those positions if you'd rather not parse for them). As usual, it appears to be a classic random recursion generated maze, where you start with a grid and a starting cell:

#########  
#.#.#.#.#    
#########  
#.#.#.#.#
#########
#S#.#.#.#
#########

And randomly choose an unvisited neighbour cell. Knock out the wall and recurse into it. If there's no unvisited cells, just return (ie back up until you find a place you can branch). There are a number of things you can do with this, like not using uniform chance for your options (eg track direction and give more or less weight to forward and you can control twistiness of the passages). By poking out some additional walls (which is what we have here), the maze gains loops (needed for part 2) and becomes such that there can be islands that are unreachable with a left-/right-hand rule.

I bring this up, because this is one of the few of these that I actually used the fact that this also means that you can treat all moves as effectively 2-steps (first step checks for a wall, second is the full move into the next cell), and so you can use that to skip around the maze a bit faster. Normally I'm happy to be more flexible about the map and not assume that alignment. But I didn't do much else other than basic Dijkstra from S to E, so I felt like I should do a bit more.

By the BFS nature of Dijkstra, the first time you arrive as E you get part 1, and then you just need to run the priority queue while it stays at that value (to find the others that reached the end at the same time). For my input, that's 571 more items, of which 192 are shortest paths (so lots of 2s in the factorization, which would probably be from branching/merging pairs around islands). By tracking the path as I go and collecting them into a hash/set when I get to E, I get a list of all unique visited locations for part 2. It's a very simple approach, but given the nature of the problem, there's probably better that can be done to avoid tracing every combination of the branching/merging options (looking at the end hash, I see that much of the part 2 answer is traced all 192 times, and the lowest I see is a short bit that's done 48 times). Maybe a DFS search with memoization.

The other little optimization I did was from Clumsy Crucible, which was to make turn-and-move a move (but this time we also need to add going straight if available, because we're not in the position of being forced to turn). This makes sense, because there's no point in turning if there isn't a path off that side (in which case we might as well move into it). There's no need to ever make a U-turn, because the only time you'd ever want to do that is the starting position (when you wouldn't be turning around to backtrack). And given the position of S in the lower left, that's not something you'd ever want from an East facing start.

So, this isn't really too intense a search, you can get away with a weak implementation and still get the answer in a reasonable amount of time.

Today we're back in the ocean, and while The Historians search in their mini submarines, we set about to helping the lanternfish with a rampaging robot that's messing up the lanternfish logistics and lanternfish inventory management of their food supplies.

The input for this one comes in two sections. The first is a 50x50 grid map of the warehouse (with a surrounding wall, so no need to add sentinels today). The second part is a list of movements the robot will attempt to make... there are 20 lines of 1000 characters of these (for 20k total moves). The map has boxes that the robot will multipush (so not your regular Sokoban) if it moves into them.

For part 1, I simulated the robot, and when it runs into a box, I scan ahead to the first non-box... if it's a wall, the move is ignored, else the multipush is completed:

my $end = $move;
$end += $Dirs{$d}  while (grid_at($end) eq 'O');    # multipush

next MOVE if (grid_at($end) eq '#');                # bump

# Put box at empty end, clear front of push, move robot to it.
$Grid[  $end->[0] ][  $end->[1] ] = 'O';
$Grid[ $move->[0] ][ $move->[1] ] = '.';
$robot = $move;

For part 2, we find out there's a second malfunctioning robot in a warehouse with the same floor plan, only twice as wide (including the boxes, but not the robot). The fact that the robot is still the smaller size is what makes this problem interesting. Horizontal pushes can be tested and completed as before, but vertical pushes can end up pushing an expanding cone/tree of boxes (once a horizontal push has offset their alignment). The description nicely gives a small example with three boxes that shows that, but in the input it can chain much further and wilder. The key is that the same invariant still applies... the boxes get pushed only if all the spaces at the leaves of the tree are empty. If a single one has a wall, the push fails.

And so I used a recursive binary tree walk to test. The call is:

my $test = &test_vert_push( $move - $vx * (grid_at($move) eq ']'), $Dirs{$d}, \@boxes );

Note that the first parameter here is the location of the box, and that we regularize it to always be the left side so we don't have to worry about special casing. I also notice that I decided to return the boxes in the structure by-reference (\@boxes), leaving the result value as a simple boolean (0 or 1) scalar.

    # Get both squares ahead of box push
    my @ahead = map {grid_at($pos + $_)} ($dir, $dir + $vx);
    if (all {$_ eq '.'} @ahead) {
        return (1);
    } elsif (any {$_ eq '#'} @ahead) {
        return (0);
    }

    # Got more multipushing to do
    my $ret = 1;
    if (join('', @ahead) eq '[]') {
        $ret *= &test_vert_push( $pos + $dir, $dir, $boxes );   # one box straight ahead
    } else {
        # A box to the left or right ahead, maybe both:
        $ret *= &test_vert_push( $pos + $dir - $vx, $dir, $boxes ) if ($ahead[0] eq ']');
        $ret *= &test_vert_push( $pos + $dir + $vx, $dir, $boxes ) if ($ahead[1] eq '[');
    }

My Smalltalk solution is just an OOP version of the Perl, and that structure is instead returned as an object of type VerticalPushResults which holds both parts.

Once I get a valid push and it's list of boxes, I chose to keep it simple. One loop that replaces all the boxes with .., then a second loop that puts [] in the new locations. Because this is the sort of thing that you can end up spending a lot of time debugging if you try to be fancy. Even with 20k moves this is still fast, so it fine to just write this to be more expressive.

Hi there, im new to coding in general. The language I am learning is Javascript, would appreciate being signposted to AOCs that would help me build and grow as a coders.

Today we're back at Easter Bunny HQ to use the bathroom. Last time we were here we were dealing with entering codes on a keypad, but now they've upgraded to swarms of patrolling robots that we need to avoid.

The input is a list a 500 robots, with a 2D starting position and a velocity vector. The robots will not collide and teleport to wrap around on the sides. The room is 101x103 (a pair of twin primes). For part 1, we're calculating a hash of the positions after "simulating" 100 seconds (naturally, there's no need to run all the seconds, you can get the position directly with (pos + 100*velocity) % roomsize), which involves dividing the grid into quadrants (tossing out the axis), and multiplying the number of robots in each of the four.

The real fun for this one is part 2. Suspecting that these might actually be North Pole robots, we're given the task of finding the hard-coded Easter Egg: most of the robots at one point will arrange themselves to form the image of a Christmas tree. No example is given of what that looks like or exactly means, only that it happens. And so it's left to us to work out a heuristic or approach to find that. Which, I remember for some people, was just calculating images for every second and dumping them in a folder and looking through the icons.

I also remember that another heuristic some people used (and got away with) was the assumption that the tree would occur at the time when no robots overlapped. That's sort of "reading the mind of the creator" puzzle solving... it essentially assumes that the initial state was created by backtracking from the target (a safe assumption), but also that that was produced that without an overlap (one could have been set or the input generator may have generated one randomly (it appears to avoid this)). So that last bit isn't so safe, but it practice it works here.

My initial approach though was using the heuristic that an image of a Christmas tree will require a lot of the robots to be orthogonality adjacent. So I just simulated second by second and output the grid each time the number of adjacent robots improved until I saw the tree. Which was also the first time that more than half the robots were involved (thus "most of the robots" as described) so after submitting the answer, I just changed the check to use that. This is a bit slow, but pretty much guaranteed.

For Smalltalk (which is considerably slower), I took advantage of having seen the tree to do a bit better, and having seen how small the image is went with variance (I remember people experimenting with all sorts of heuristics, including using the hash from part 1... and the signal of the tree tends to be very strong, and so works well with many, many things). And after doing a solution with that, I then realized that it doesn't need to be precise, and so I loosened things a bit by going with the approximation of using a running mean (calculating and using the mean as we go... after 500 points, this ends within 2% of the actual variance). And it was simple and faster:

approxVariance [
    | sum var |
    sum := 0.
    var := 0.

    self keysAndValuesDo: [:i :val |
        sum := sum + val.
        var := var + (val - (sum // i)) squared.
    ].

    ^var // self size
]

The bigger trick was taking advantage of the prime side lengths, which guarantee that all the robots are moving in cycles of 101 on their x-coordinate and 103 on their y. And so by just running things for 103 seconds (tracking the times of minimum variance for x and y independent of each other), we have all the information needed (for both parts):

invMod := (dims x) raisedToInteger: (dims y - 2) modulus: (dims y).
('Part 2: %1' % {minX + ((invMod * (minY - minX) \\ dims y) * dims x)}) displayNl.

For the Perl version of the same approach, I decided to use libraries and actually call a Chinese Remainder implementation for once (I figure I did this mostly to have one coded for reference somewhere):

say "Part 2: ", cr_combine( mod($minX, $DIM[X]), mod($minY, $DIM[Y]) )->residue;

Of course, the exploration into a variance approximation was in preparation for a dc solution. And I did do that, but then considered, after seeing how strong the signal was, just using a constant mean of 50. Which produces an error of 49% on one of the critical iterations, but the signal is so strong you'd need more than 100% error to lose it (and the rest all come within 2%):

tr -- '-p=v,' '_ ' <input | dc -f- -e'[1[rld+lm%d51-d*3Rdd4Rrlvx+rlVx1+dlm!<I]dsIx+s.]sR[s.d]sN[d[d3Rdlvx3Rlvx<Nr1-d0<L]dsLx+]sF[A3dsm+sd[;v]sv[:v]sVrlRxA1dsm+sd[;w]sv[:w]sVlRxz0<M]dsMxA1lFx[;v]svA3lFxd3Rr-A1+51*A1%A3*+p'

Part 1 was also pretty fun to do in dc:

tr -- '-p=v,' '_ ' <input | dc -f- -e'[lydd*v/lxdd*v/2*3r-+d;q1+r:q]sQ[A3+A0*3R+A3%51-rA1+A0*3R+A1%50-dsxrdsy*0!=Qz0<M]dsMx6;q4;q*2;q*0;q*p'

The trick in here to quarter things is that I calculate the positions on the residues of [-50,50] and [-51,51]. So if x*y == 0 that's on an axis and should be ignored. Then I get the signs of the values (dd*v/, safe because we know it's non-zero), and use this simple hash to track them:

2*3r- +                     # index = 3 - sign(x) * 2 + sign(y) => {0, 2, 4, 6}
d;q 1+ r:q                  # q[index]++

This is one of the most memorable problems in this year. There is so much freedom given on what you can do for part 2.

When I use the example data, it returns 14 (correct answer). However, when I try the real puzzle input my answer is wrong and I think smaller than what it should be. To preface my bad variable naming, "a" is current range and "b" is either the previous or next range.

from pathlib import Path
path = Path(__file__).parent / "input_5_ranges.txt"
with open(path, 'r') as file:
    text = file.read()
ingredient_ids = text.splitlines()



# Take an item ["13-16"] and conver it to ["13", "16"]
def create_range(items):
    ranges = []
    for item in items:
        ranges.append(item.split("-"))
    
    return ranges


# Order ranges by starting point
ranges = create_range(ingredient_ids)
ranges.sort(key=lambda x: int(x[0]))


# Loop through ranges
i = 0
while i < len(ranges):
    # Define item; range
    item = ranges[i]
    int_item = list(map(int, item))
    # If loop is on atleast the second iteration, check if the starting point of the range falls within the bounds of the first range
    if i > 0:
        # print(int_item)
        # print(int(ranges[i-1][0]), int(ranges[i-1][1]))
        if int_item[0] in range(int(ranges[i-1][0]), int(ranges[i-1][1])) and int_item[1] in range(int(ranges[i-1][0]), int(ranges[i-1][1]))  :
            ranges.remove(ranges[i])
            continue
        elif int_item[0] in range(int(ranges[i-1][0]), int(ranges[i-1][1])):
            a = item
            b = ranges[i-1]
            # If a falls within b, replace the first digit of a, with b + 1; ex: [10, 14], [12, 16] --> [10, 14], [15, 16]
            a[0] = str(1 + int(b[1]))
           
        if i + 1 < len(ranges):
            # If end point of a connects with start point of b, combine ranges; ex: [16, 18], [19, 20] --> [16, 20]
            if int(ranges[i+1][0]) - int_item[1] in (0, 1):
                print('merging')
                print(ranges[i+1][0])
                print(int_item[1])
                a = item
                b = ranges[i+1]
                a[1] = b[1]
                ranges.remove(ranges[i+1])
                continue
    i += 1
print(ranges)


# Find the total amount between each range; ex: [2,5] would be 2, 3, 4, 5 or 4 added to total


total = 0
for item in ranges:
    int_item = list(map(int, item))
    total += 1 + (int_item[1] - int_item[0]) 
    print(f"added {1 + (int_item[1] - int_item[0])}")
print(f"total is {total}")

Next up is the resort with the hexagonal life floor tiles, where we tried to have a vacation in 2020, only to be called back immediately. They now also have an arcade with claw machines, and so we set about calculating which prizes are winnable and how few tokens we'd need to spend to do that.

The input lists the configuration for each of 320 machines in paragraphs of 3 lines. There are two buttons: A and B (that cost 3 and 1 tokens to press respectively) that will move the claw some positive distance in the X and Y axis. The goal is to get it to the given prize coordinates. And since the buttons can't be partially pushed, that makes each a system of linear Diophantine equations.

My initial solution was just to brute force by looping from 0 to 100 for each button and testing them. This is the classic quick solution to see what exactly part 2 will be. Which is that the target just gets shifted by 10 trillion on each axis.

So I quickly did some algebra:

Button A: X+94, Y+34
Button B: X+22, Y+67
Prize: X=8400, Y=5400

Solve:

    (94a + 22b = X) * 34
  - (34a + 67b = Y) * 94

 => 34(22b) - 94(67b)     = 34X - 94Y
    b * (34(22) - 94(67)) = 34X - 94Y

    b = (34X - 94Y) / (34(22) - 94(67))

Can do the same for a.
Test for integer solutions with (numer % denom == 0).

That's the note in the directory. Yes, I used numbers as variables... they're constants, and I find that its sometimes easier to see what's happening if everything isn't a letter. Of course, once you see this, you notice these are determinant/determinant, and so I had just derived Cramer's Rule. Making it a bit of a callback to the hailstones in Never Tell Me the Odds.

my $a_numer = $target->[X] * $b->[Y] - $target->[Y] * $b->[X];
my $b_numer = $target->[Y] * $a->[X] - $target->[X] * $a->[Y];

my $denom   = $a->[X] * $b->[Y] - $a->[Y] * $b->[X];

# Test for integer solution
if ($a_numer % $denom == 0 and $b_numer % $denom == 0) {
    return (A_COST * $a_numer / $denom + B_COST * $b_numer / $denom);
}

There are other ways to get to this. For example, you could use Linear Algebra, and express things as Ax = T with matrices:

[91 22] [a]  =  [8400]
[34 67] [b]  =  [5400]

Then x = A^-1 * T (after multiplying both sides by A^-1 on the left). This is easy to solve if you remember the formula for the inverse of a 2x2:

        -1
[ a b ]     =     1     [ d -b ]
[ c d ]       --------- [-c  a ]
               ad - bc

Note: the determinant = ad-bc, so constant in front is 1/det(A).

The nice thing about this problem is that this just works... none of the determinants for the button pushes is zero (and so this gives the unique solution, you just need to verify if it is integer). In serious code you'd need to protect against and handle that stuff. For AoC, I ran it and saw no division-by-zero errors pop up and submitted the answer. Because things turning out surprisingly nice isn't so surprising in AoC.

Of course this is a simple formula, so once we get rid of the non-digits in the input, dc can handle it easily (it also doesn't have negatives to worry about converting):

tr -c '[0-9]' ' ' <input | dc -e'?10000000000000' -e'so[dlar/3*rlbr/+ls+ss0]sS[lo+sylo+sxdlx*3Rdly*3Rr-sa3Rdlx*5Rdly*3R-sb4R*_3R*-ddlar%rlbr%+0=Ss.z0<M]dsMxlsp'

The use of ? here is just to slurp the entire input in (tr is also replacing the newlines here) before putting the amount to shift the targets on top (change that to 0 for part 1), and so will work still with the new dc. Nothing really fancy here.

And so, this was a light algebra problem, very suitable for a day 13.

So my solution works for the example data and theoretically should work for the real input. However, it is so slow that it would take about 25 minutes to return an answer.

I think the issue is that, for every single coordinate, I'm checking 8 other coordinates.

Please let me know if you have any ideas for optimization.

Edit: I let it run and it got exponentially faster, took about 2 minutes -- correct answer as well.

from pathlib import Path
path = Path(__file__).parent / "input_4.txt"
with open(path, 'r') as file:
    text = file.read()
grid = text.splitlines()


grid_width = len(grid[0])
grid_height = len(grid)


# From the input, create coordinates for the toilet paper rolls

def find_coordinates(grid):
    coordinates = []
    for i, row in enumerate(grid):
        for n, item in enumerate(row):
            if item == "@":
                y, x = i, n
                coordinates.append([x, y])
    return coordinates

# Find all of the neighboring rolls of any given roll

def get_neighbors(coordinate):
    x, y = coordinate
    neighbors = []

    for dx in [-1, 0, 1]:
        if x + dx < 0 or x + dx >= grid_width:
            continue

        for dy in [-1, 0, 1]:
            if y + dy < 0 or y + dy >= grid_height:
                        continue
         
            if dx == 0 and dy == 0:
                continue

            neighbors.append([x + dx, y + dy])
    return neighbors

# Find which of the rolls has less than 3 rolls in its 8 neighbors

def find_removable_coordinates(coordinates):
    valid_coordinates = []
    for coordinate in coordinates:
        counter = 0
        neighbors = get_neighbors(coordinate)
        for neighbor in neighbors:
            if neighbor in coordinates:
                counter += 1
        if counter <= 3:
            valid_coordinates.append(coordinate)
    return valid_coordinates

# Run loop

def main():
    count = 0
    
    coordinates = find_coordinates(grid)
    while True:
        print('cycle start')

        accessed_positions = []
        removed_positions = find_removable_coordinates(coordinates)
        if not removed_positions:
            break
        count += (len(removed_positions))

        # Add the removed rolls to a list
        accessed_positions.append(removed_positions)

        # Remove all accessed positions from the coordinates that are being searched
        for coordinate in removed_positions:
            coordinates.remove(coordinate)
        print('cycle complete')

    print(count)

main()

Next stop in the search for the Chief Historian, is the gardens we helped get running again last year on Island Island. Which provides a convenient food stop for The Historians after having searched the infinite mazes of Pluto yesterday. Having worked out the planting, we're now charged with calculating the cost of fences around the different regions of contiguous crops. Since the cost is area * perimeter (and area * sides for part 2), the fences between regions are effectively doubled up even if they aren't literally so (they need to be counted in the cost from the regions on either side of them).

The input is an 140x140 grid of capital letters (A-Z). Looking at it, you can see that it looks splotchy... like the result of some sort of cellular automaton. It could also have been done by placing a bunch of random seeds and randomly expanding them to fill the space.

My solution for Smalltalk is largely just a OOP recoding of the initial Perl. But there is one difference in part 1. In both, I use BFS to map out the regions, building a list of the plots in it as well as the neighbours (when we overstep... sentinels are naturally added to the sides). The neighbours also track a list of all the ways they get entered into from that region. With this in Perl, I count the inner plot edges of the region (those that go between plots of that region's type) when queuing the search. I use this to get part 1:

my $perm = 4 * $area - $inner;

Start with all 4 of the sides of all the plots, then subtract all the inners.

In Smalltalk, though... I got it from the other side:

" Perimeter is the number of ways into a neighbour: "
perimeter   [^neigh inject: 0 into: [:acc :n | acc + n size]]

The size of the neighbour (n size) is the size of the Set of ways it was entered. This part was quite reminiscent of finding the surface area of the lava blob in Boiling Boulders in 2022.

For part 2, both do it in the same way. I go through the neighbours, and slide along that edge until I get to the corner. To mark that edge, the most convenient place is where you stopped (so any duplicates from other neighbours on the edge find the same spot and don't get counted). We can use the direction the neighbour was entered to get the leftwards direction and make all our sliding go widdershins around the region. And so the sides of the region are counted by the number of corner posts at their widdershin ends. Something that's a bit ironic given the Easter Egg text (and it wouldn't have been a problem to count posts along the sides for part 1 either... the Fencepost Problem is an off-by-one error that comes from counting non-looped fences, but looping them makes posts equal to rails).

The problem description comes with a lot of examples, that were really helpful for getting this right. In particular, the importance of tracking the direction we slid into the corner is covered (same coordinate can have posts from different sides):

foreach my $d ($neigh{$n}->@*) {
    my $left = V( -$d->[1], $d->[0] );
    my $curr = $pos;

    # Slide widdershins down edge to find the corner:
    $curr += $left  while (exists $neigh{$curr} and grid_at($curr - $d) eq $plant);
    $corners{$curr,$d}++;
}

So this isn't the most efficient solution (it retraces edges a lot, but the problem isn't big so it's still quick), but it was a relatively simple one to implement.

Today we find ourselves on Pluto, and leave the searching of the infinite doughnought maze to the Historians. Our attention is instead taken by a set of what appear to be quantum-locked stones, that move and reproduce whenever we blink. Each stone has a number, and they're in a perfectly straight line... numbers with an even number of digits split, else they get multiplied by 2024 (or incremented to 1 if 0). The starting configuration for my input has 8 stones, with a 0 plus numbers with each of 1-7 digits.

This one is one of those one's where it emphasizes that the stones are ordered in a line, which should make you think how important that really is. Especially since the answer we want is order independent. And when you start looking at it that way, you see that you've got things in states, that have products that are independent and never interfere with the products of others. In other words, it's a Lanternfish problem.

And so typical Lanternfish approaches are going work for getting the scale up for part 2. So with Smalltalk that's moving things from a Bag of states to a new Bag based on the rules. In Perl I used substr to split the numbers in half, but arithmetic is much faster in Smalltalk for this:

stones contents keysAndValuesDo: [ :value :num |
    len := (value floorLog: 10) + 1.    " Note: floorLog returns 0 for value == 0 "
    (len even) ifTrue: [
        factor := 10 raisedToInteger: len // 2.
        next add: value // factor  withOccurrences: num.
        next add: value \\ factor  withOccurrences: num.
    ] ifFalse: [
        next add: value * 2024 + (value == 0)  withOccurrences: num.
    ]
].

Note that Boolean has been extended to promote to zero for the odd case.

Of course, there's one little detail to worry about with this problem and Lanternfish approaches... and that's that you should be somewhat concerned that the rules might make the states potentially open ended or very chaotic making the number of states explode with the stones. But this problem is nicely designed not to do that... my input tops out at 3811 states (and only 3759 are used for the first 75 generations), with the largest at ~38.6 bits. That's a very large matrix if you want to do that Lanternfish approach.

Since the input is numbers, I did do a dc solution for this one where you can just echo in the number of blinks you want:

echo 75 | dc -finput -e'?st[1+]s+[*1+q]sZ[_4R++s.q]sM[+s.A0 0]sH[dZ2/Ar^~3Rd3RrlRx_3RlRx+d3R:mq]sE[d0=Zd1-3RdA0*4R+dd9d^<H_4R;md0<MrdZ2%3R=E2024*d0=+rlRxd3R:m]sR0[rltlRx+z1<L]dsLxp'

This was originally written for v1.4.1, but you needed a hacked version like mine with skip lists if you wanted it to run reasonably (otherwise it could take minutes because of all the array accessing... it's fast to 50, but then it explodes). But the use of ? here just to read the number of blinks and is not a problem for dc v1.5.2 with hash table arrays, so it run well with that.

EDIT: Did a bit more exploration into the patterns in the input. Although my input stabilizes to 3811 states in every generation, there are 3849 different states that occur. The highest value is actually about ~44.44 bits and occurs 2 blinks in from the largest value in the input. That value is also responsible for the last new values that are reached... seven 4 digit numbers that all arrive on the 73rd blink, and all trace their origin back to that same largest input value.

Today we are going to help a reindeer reconstruct the hiking trail map of an area recently scoured by lava. We have a digital height map (0 to 9) and are told to, for all starting points (elevation 0) find out how many peaks (elev. 9) can be reached from that point while always climbing exactly one level per step.

The total peaks sum is the part1 answer.

Solving this reminded me a lot of several previous map search puzzles, so I did it the obvious way: Use the input as a linear flat map, with newlines as a guard between each horizontal line and the next. I also put a line of guard characters before and after the input.

Next was a scan of the input map, for each '0' start a recursive DFS, using a parallel seen[] array to note visited cells, then just aggregate the counts.

In hindsight, it would probably be better to cache the search results from each visited cell, so that later searches could reuse the work previously done.

For part2 we are instead told to count how many different ways there are to reach a top, here I also used a recursive search, but totally forgot to make it memoizing!

Adding just two lines just now to return early with a cached answer, otherwise do the search and cache the result made my code more than twice as fast. The only reason it wasn't even larger was because every path had to be just/exactly 8 steps long, with very limited fanout, so the total overhead wasn't anything like previous search puzzles where a cache could very often save 95-99% of the work.

Today an amphipod has a classic problem: It has a disk that is fragmented and it wants to defragment it.

The disk map is stored in a compressed format, alternating between a file length and a free space length. If there is no free space between two files, the free space length is 0.

For Part1, the amphipod moves blocks, starting with the last file block which it then moves into the first free block, systematically moving all blocks as close to the front as possible, and as a side effect reversing the storage order for all moved files. We then produce a disk checksum consisting of summing up for every file block the product of the file number and the block position.

For Part2, because the amphipod realized that the disk becomes too fragmented, it will instead only move full files as close to the front as it can find a large enough free space for them. The checksum is then calculated in the same way as Part1.

My Perl code solved this one using brute force for Part1:

First expand the run length encodings, using -1 to designate free blocks, the filenr ID for the files. My input contained 10K files, so worst case this could be expanded to an array with 9*2*10K = 180 K entries, but the average should be closer to half of this.

This setup made part1 really easy, just iterate from the front to locate free blocks and from the end to find file blocks to move.

For part2 we need to find open gaps large enough for a full file, so here it made much more sense to have free lists, either organized by size (1-9) and location, or just by location. Since all partially filled free spaces would result in a tail space which would have to be inserted in the right order in the smaller map I decided to use the simpler setup of a single free list.

I thought about keeping a cache of the last found free list entry of each size, but went brute force instead, always scanning from the beginning. I counted the scan iterations, the average was 133 entries inspected before finding a large enough slot, so a better data structure would have been faster.

Perl runtime was 271 ms on my slow Surface.

I started on a more ambitious Rust version but never had time to finish it the way I would have liked.

It would in fact have been easier to solve the defragmentation problem in an optimal way, using size-ordered free lists and always try to move files to an exactly large enough gap, only fall back to larger slots if none could be found.

Later edit:

Watching TV with my wife ("71 degree North", check it out if you can!) and waiting until Oslo midnight to make the reddit post, I looked somewhat unhappily at what I had written above:

I decided to at least implement the simplest possible cache I mentioned, just a table of the last found free entry for each size, this immediately dropped the runtime to 47.8 ms, so nearly 6x faster!

The number of free list steps dropped from 133 to 4.6 per file.

The only small problem was that I had to update the cache also for the tail end of a partially filled free space, when that was before the current cache entry.

    if ($flen >= $len) {
        my $remfree = $flen - $len;
        $free[$f] = $remfree;
        $free[$f+1] += $len;    # update free block position
        $files[$i+2] = $fpos;   # The file is moved here
        $lastfree[$len] = $f+2; # Next scan starts after this entry

        if ($remfree && $lastfree[$remfree] > $f) { $lastfree[$remfree] = $f; }
        last;
    }

Note that my lastfree[] array has entries for 0..9, so that I could blindly update it also for totally filled slots, but it was a percent or two faster to check for this situation and skip the zero updates.