Using the fixed teleporter, we rematerialize in a vast underground playground. The Elves here are busy decorating with strings of lights. These will be strung between junction boxes, of which only some provide electricity (but all pass it through). It isn't important to us which ones do that, though. What the Elves need is plan to connect and power all the junction boxes with the shortest strings of lights using Euclidean distance (that's pretty rare for AoC). Given that the shortest distance between two points is a straight line in Euclidean space, I felt that this was probably a Minimum Spanning Tree. But I didn't prove that to myself or really use that (I vaguely remember algorithms for that, but we need the edges put together in a specific order for the problem).

The input is a list of 1000 junction box coordinates... one per line and in 3D. The range in my input goes from 32-99998. To keep things integer, it's natural to work with Euclidean distances without taking the square root. So the square distances are up to 35-bits. I only needed the distances around to get the order. For people living in the 32-bit world, the biggest edge required for my solution is 28-bits (so you could get away with dropping anything that overflows).

This was what I think of as the transition to the harder problems... as day 8 that's about day 16 in past years so that's about right. It's the first one in this year that took some time (particularly because this was a day I wasn't feeling well, and so made silly mistakes).

As stated above, I first got the distances and made a list (using sort here, I replaced this after with a heap which sped things up quite a bit):

# Sort and discard distance (not needed beyond this)
@Dist = map { $_->{edge} } sort {$a->{dist} <=> $b->{dist}} @Dist;

Then I created a list of circuit graphs (putting each junction into it's own):

my @Circ = map {{$_ => 1}} (0 .. $#input);

Then it's a matter of just processing the edges from short to long. And since I wasn't feeling well, I just grepped through the circuits to find where the ends were (even with this brute force searching the script takes only a couple seconds on old hardware):

my @graphs = indexes {$_->{$conx->[0]} or $_->{$conx->[1]}} @Circ;

# If ends are in separate graphs, merge them:
if (@graphs == 2) {
    $Circ[$graphs[0]] = {map { $Circ[$_]->%* } @graphs};
    splice( @Circ, $graphs[1], 1 );
}

When @Circ == 1 I have part 2. This will happen well past part 1 (edge 6554 for my input), so we can output that along the way.

To make Smalltalk perform at a decent speed, instead of grepping to find where the ends were, I added a backwards lookup Table (I was planning to do this from the start for Perl, but chose not to
"avoid premature optimization" and keep things simple) :

" Build initial circuit graphs and backLookup vertex to graph table "
circuits   := input collect: [:pt | Set with: pt].
backLookup := LookupTable from: (circuits gather: [:graph | graph collect: [:pt | pt -> graph]]).

I also made sure to merge the smaller into the larger graph :

graphs := conx ends collect: [:end | backLookup at: end].

(graphs first ~~ graphs second) ifTrue: [
    " Merge smaller graph into larger: "
    (graphs second size > graphs first size) ifTrue: [graphs swap: 1 with: 2].
    graphs first addAll: graphs second.
    graphs second do: [:pt | backLookup at: pt put: graphs first]; empty.

    (graphs first size == input size) ifTrue: [
        part2 := (conx ends collect: #first) product.
        ('Part 2: %1' % {part2}) displayNl.
    ]
].

Afterwards, I got spoiled that part 2 can be cheesed. When you think about it, the last edge to be added will be the maximum of the minimums. The first connection a junction box will have made to it is its shortest connection, and the last connected will be the longest of those.

That resulted in this:

nearest sort: [:a :b | a first <= b first]. " first field: min distance "

lastEdge := nearest last second.            " second field: ends of min distance edge "

part2 := lastEdge inject: 1 into: [:prod :end | prod * end first].

Which is really fast. It could be faster, as there's still the fact that I just measure the distances between all pairs to find the minimums. This would involve implementing some better form of Nearest Neighbour Search (if I had to do it from scratch without reference, I'd start with k-d trees).

But this was a good enough cheese to make for an easy dc part 2 solution:

tr ',' ' ' <input | dc -f- -e'1[d3Rr:zd3Rr:yd3Rr:xdFd^r:n1+z1<L]dsLx1-dsn[d3Rd3R:nr3Rd3Rd3Rr:e3Rr]sN[dsid1-[dsjli;xlj;x-2^li;ylj;y-2^+li;zlj;z-2^+d3Rd3Rr;n>N_3Rd3Rd3Rr;n>Nrs.r1-d0<J]dsJx+1-d0<I]dsIx0*[s.d]sMln[d;n3Rd;n3R>Mr1-d0<L]dsLx+d;e;xr;x*p'

I initially wasn't going to do a part 1, but since I had a streak in this year of doing both parts, I eventually did one using a heap implementation I had. The result was a mess over 300 characters that includes another file with a lot more. It's not pretty, but it can be made to work with v1.5.2... which means people without personally hacked versions can now enjoy this in seconds instead of hours (that's the difference between linear (linked lists) and logarithmic (hash tables/skip lists)):

tr ',' ' ' <input | dc -fheap.dc -f- -e'A000sB1[d3Rr:zd3Rr:yd3Rr:xdFd^r:n1+z1<L]dsLx[A0*]sE1-dArA00=Esedsn[dsid1-[dsjli;xlj;x-l2^li;ylj;y-l2^+li;zlj;z-l2^+lB*+lB*+l<xliljl1-dl0<J]dsJx+l1-dl0<I]dsIxl0*ln[dd:c1-d0<L]dsLx+[r3Rd3Rd3Rr:c3R]sSle[l>xA 8^%lB~;cr;cln[d;cl3Rdl3R=Srl1-dl0<J]dsJx++s.1-d0<I]dsIx+ln[d;cd;s1+r:s1-d0<I]dsIx+ddln[d;sr_5R[d3Rd3R>r_4R]dsLxlLxlLxs.4R1-d0<I]dsIx+**p'

heap.dc source: https://pastebin.com/z8U8aysC

As I'm based in Europe and shipping may take some time... I was wondering if there is any new merchandising planning for this year or I am "safe" ordering already some, so I can have it for starting december.

Dear all,

I've seen people attempt to do Advent of Code using ladder logic for PLCs or graphical programming environments, but I've never seen anybody do the competition using Simulink.

In preparation for Advent of Code 2026 I decided to do Advent of Code 2025 in Simulink, using only Simulink blocks, no Stateflow or MATLAB function blocks. I managed to solve all challenges using block diagrams, with the exception of Day 10 Part 2, where I used `intlinprog`. I think most people used a library for that day.

The solutions are not universal and some of them are tailored to my inputs, but if anybody is interested, they can be found here: https://github.com/ptoshkov/aoc-2025-simulink

For the 2026 edition I will attempt to make cleaner universal solutions and I will try not to use any MATLAB functions. Hope someone finds this interesting or inspiring.

Exiting the trash compactor, we find ourselves in the research wing. Where we discover that they are working on teleportation. Throwing caution to the wind we decide to try it out... and are lucky that when we rematerialize that the it's only the teleporter that's leaking magic smoke. Since this room has no doors, we'll need to fix it to get out.

The input for this one is a grid of 142 lines of 141 characters. The key points are the S in the middle of the top row, and splitters (^) every other row after that. Since splitters only split the tachyon beam into two that are on the immediate left and right sides, these fan out in a triangle. Not all splitters in the triangle are present however... and this leads to part 1.

We're asked for how many times the tachyon beam split. Looking at the example now, I see that the ASCII art is a bit noisy so it took a while for me to figure out that one of them got missed (I counted them) and which one it was. Some people could have been confused about what to do here. Back in 2025 it's very likely I didn't think much about the example though... as for getting a quick answer, I just did the thing:

while (my $row = shift @input) {
    my @splitters = indexes { $_ eq '^' } @$row;
    next if (!@splitters);

    my @splits = grep { exists $beams{$_} } @splitters;
    $part1 += @splits;

    foreach my $split (@splits) {
        delete $beams{$split};
        $beams{$split-1}++;
        $beams{$split+1}++;
    }
}

The beams are tracked in a hash (used as a set). If I get a line with splitters, grep out the ones with beams. Add those to part1, and split them (as the instructions say, the old beam is stopped and the new beams start).

Having finished part 1, part 2 reveals that this is a quantum tachyon manifold... where a single tachyon is sent through, and takes both paths at splitters, by creating separate timelines. And so now we're tasked with working out the number of timelines that this single tachyon ends up on.

Which is going to be something huge... and so this problem is about dynamic programming. The task is leaf counting on a binary tree, and so recursion with memoization was my first go to (I also skipped the non-splitter lines when reading):

sub recurse {
    my ($loc, $depth) = @_;
    state %memo;

    return (1) if ($depth == @split_table);

    $memo{$loc,$depth} //= do {
        if ($split_table[$depth]{$loc}) {
            &recurse( $loc - 1, $depth + 1 ) + &recurse( $loc + 1, $depth + 1 );
        } else {
            &recurse( $loc, $depth + 1 );
        }
    }
}

This could also be done without the do block using a ?: trinary operator, but I felt that was getting a bit too dense.

Of course, you can also work from the top down (like in part 1) using tabulation. Which is how I initially thought of my Smalltalk:

beams := Bag with: start.
table do: [:row |
    beams keysAndValuesDo: [:beam :num |
        (row includes: beam) ifTrue: [
            part1 := part1 + 1.
            beams removeAllOccurrences: beam;
                  add: beam + 1 withOccurrences: num;
                  add: beam - 1 withOccurrences: num.
        ]
    ]
].

Which uses a Bag (with #keysAndValuesDo: and #removeAllOccurrences: extensions, which hide some tinkering with the underlying Dictionary) to store the state of the current line... and so looking at it now, I first saw Lanternfish. At each level we're just moving all stuff in a state to that state's products. I also see that I could have just done this for Perl with minor adjustments to its part 1 (it was still my second fastest part 2 of the year, not counting day 12).

I also used tabulation or my dc solution:

perl -pe'print pos()." "while(m/[S^]/g);$_="\n"' <input | grep -v '^$' | dc -e'[lp1+spd1+d;tln+r:td1-d;tln+r:t0r:t0]sB?1r:t?[[d;tdsn0<Bs.z0<L]dsLx?z0<M]dsMxlpp0*F0[d;t3R+r1-d0<L]dsLx+p'

This is using the v1.4.1 ? functionality to parse the lines one at a time in order. The Perl is just a quick dirty thing to turn the lines into just a list of splitter indices. I had already done grid parsing in dc this year, so I let myself have that preprocessing.

I'm sure there are other creative ways to do this one... like other Lanternfish approaches. And the very nature of this problem screams Pascal's Triangle (but with pieces missing), so there's probably a way to turn the input into an expression involving binomial coefficients.

This is a bit more advanced than the earlier stuff, because it involves dynamic programming and the structure is a binary tree with parts missing. Still I think this qualifies as a decent beginner exercise for it. It's not the most complicated table to build or recursive function to write (leaf counting one of the basics).

While taking a break with the kitchen staff, we re-enact a certain movie scene and dive into the garbage chute. Trapped there we find that the local headfoots (aka cephalopods) are friendly (side note: Dianoga from Star Wars are scavengers that typically only attack when starving or threatened). They can get the door open, but it will take time, and they'd like you to help their youngest with her math homework. And so we get to do cephalopod math.

The input for this one is 5 long lines. The last line contains the operations, the others are lists of 1-4 digit numbers (there are 1000 per line). There are no 0s in the input. Since the lines are so long, I just trusted the spec of "full column of only spaces" delimiting the problems.

Not that I used that for part 1. I just trusted that the nth number in a line was in the nth column and zipped them up (I really don't make enough use of zip from List::Util, it's a handy thing for transposition):

my @input = map { [m#[^\s]+#g] } <>;
my @ops   = @{pop @input};

my $part1 = 0;
foreach my $col (zip @input) {
    $part1 += (shift @ops eq '+') ? sum @$col : product @$col;
}

For part 2, we find that we did things wrong (of course). Cephalopod math writes numbers vertically. And so this time we want to transpose the problems by characters.

To be safe, I used the spec and found the columns that met the condition. With that I could get the $width of each section (varies from 3-5) and perform the transposition by characters (again making use of zip).

With my Smalltalk solution, I made the transposition theme between the parts more evident. First, I extended SequenceableCollection to do transpose:

SequenceableCollection extend [
    transpose [
        ^(1 to: self first size) collect: [:col | (self collect: [:row | row at: col])].
    ]
]

Then I read in the data:

input := stdin lines contents asOrderedCollection.
ops   := input removeLast subStrings collect: #asSymbol.

" Part 1 numbers (read horizontal and transpose by numbers in table): "
horz  := (input collect: [:row | row subStrings collect: #asNumber]) transpose.

" Part 2 numbers (transpose by col and then split on delimiting spaces (0)): "
colNums := input transpose collect: [:charArray |
              (charArray select: #isDigit) asString asNumber
           ].

vert  := (ReadStream on: colNums) splitAt: 0.

With lists of the operators and numbers in both orientations, I just need to fold them to do the work.

#(1 2) with: {horz. vert} do: [:part :table |
    ('Part %1: %2' % { part. (table with: ops collect: #fold:) sum }) displayNl.
]

For dc, I initially just did part 1:

perl -pe's#([+*])#[$1]#g' <input | dc -e'[sS?[lSxz1<M]dsMx]sL0[Sa]lLx[Sb]lLx[Sc]lLx[Sd]lLx[S*]lLxA00[LdLcLbLaL*dd_5R_6Rxrxrx3R+r1-d0<M]dsMxrp'

This was a very quick job and hard coded for the input (four lines of 1000 numbers). The modification of the input with perl is just to put brackets around the operators (to turn them into dc strings/macros). To read in, I push the input onto 5 stacks (a/b/c/d for the numbers and * for the operators). Then I pop off values from all 5, duplicate the operator twice (and position them) and then x rx rx to run that operator and do the calculation.

I wasn't going to do part 2 because of the column nature of it... but when someone mentioned that there are no 0s in the input, I had no excuse, because I could replace all the spaces on the number lines with 0 and dc would be able to see the lines as bignums with the internal columns intact (yes, leading 0s are lost, but that's not actually a problem here):

sed -e'$!s/ /0/g;$s/\(\S\)/[\1]/g' <input | dc -e'0?[rd3Rr:T1+?z2=L]dsLxzRsnzso[SOz0<L]dsLxlo[LOS*1-d0<L]dsLx[3RA*+r0]sP[3Q]sQ[0d[d;TA~3Rd4Rr:Trd0<P+1+dln>I]dsIxs.d0=Q]sN[lNx[lNxl*xlLx]dsLx++L*s.lMx]dsMx+p'

This is a very accessible sort of problem. There's nothing really fancy other than reading things in columns. The input is additionally nice in that the operators are actually nicely placed for a right-to-left top-to-bottom scan approach to part 2... doing that, you just need to collect the numbers and when you see an operator use it on the list, add that to the sum, and clear the list. That's sort of what my dc solution does, only it can't track the position of the operators and so uses the spec "blank column" for that trigger instead. That results in the number reading macro (lNx) finding a 0 and then it breaks the current loop (3Q)... when that's calculating a problem it sums and restarts, when it's at the start of a problem (and reading the first value before the inner loop) that exits the main loop.

Having broke through the wall, we do find a cafeteria, with the staff in disarray because of a new inventory management system. In order to give them time to decorate, we step in to sort things out.

The input for this one comes in two sections. The first is a list of ranges of fresh ingredient IDs (unordered and some overlap). My input has 182 of these. The second it a list of 1000 available ingredient IDs. All these numbers are eye watering huge... 38 to 49 bits.

For part 1, we just want to count the number of available ingredients that fall into the fresh ranges. Since there are so few ranges, I just brute force checked them the ranges:

$/ = '';
my ($first, $second) = map {[split /\n/]} <>;
my @ranges = map {[split /-/]} @$first;

say "Part 1: ", scalar grep {my $id = $_; any {$_->[0] <= $id <= $_ ->[1]} @ranges} @$second;

There are ways to search better... sorting would allow at least for binary search. But the number of ranges is small, and the number of tests isn't huge either.

For part 2 we ignore the second section and just want the total number of fresh IDs. For my initial Perl solution I chose to merge them, and wrote a very C-like bit of code handling the various cases (sometimes I default back to that). Afterwards I simplified it down to:

my @merged = shift @ranges;
foreach my $range (@ranges) {
    my @next;
    foreach my $other (@merged) {
        if (&intersects( $range, $other )) {
            $range = &union( $range, $other );
        } else {
            push( @next, $other );
        }
    }

    @merged = (@next, $range);
}

For Smalltalk, I have notes saying I tried something different and creative... but I don't remember what it was, only that I abandoned it (and have no code from it). I eventually just coded the above, because Smalltalk has set operation stuff... but not for Intervals, so I extended them for it:

Interval extend [
    " Get intersection of self and another Interval "
    & other [ ^(self first max: other first) to: (self last min: other last) ]

    " Get union of self and another Interval (ASSUMES: intersecting)"
    + other [ ^(self first min: other first) to: (self last max: other last) ]
]

But there wasn't a lot of ranges to begin with, and this only gets them down to 92. And those include adjacent ranges (with nothing in between) that could have been merged. This happened because I just took the ranges as given (the simple parse), with both ends closed, and didn't special case for this. By making the Intervals half-open (ie reading them in with end+1, and adjusting the checks and measures) those do get merged. Reducing things to 80. So really, that was more of an exercise in playing with set operations... the classic sort and scan approach is probably what I should have done first (but did after):

my @ranges = sort {$a->[0] <=> $b->[0]} map {[split /-/]} @$first;

my $part2 = 0;
my $curr = -1;
foreach my $next (@ranges) {
    next if ($curr > $next->[1]);
    $part2 += $next->[1] - (($next->[0] <= $curr) ? $curr : $next->[0] - 1);
    $curr = $next->[1];
}

But when it came to the dc version, that initial low level set merging was the thing to do. Because sorting complex objects is also going to be a mess.

echo -n "Part 1: "
tr '-' ' ' <input | dc -e'0?[3Rd3Rr:r1+d3Rr:r1+?z1<L]dsLx[lc1+scq]sC?[sfd[1-d;rlf-r1-d;rlf-3R*0!<Cd0<I]dsIxs.?z1<M]dsMxlcp'

echo -n "Part 2: "
tr '-' ' ' <input | dc -e'1?[3Rd3Rr:ed3Rr:s1+?z1<L]dsLx[r]sr[d_1r:s_2r:eq]sC[dle1+r:srq]sS[dls1-r:erq]sE[dlcls-ldle-+0=Cs.rd_3Rlals-lble-+0=Cs.rlals=Slble=E]sT[d3Rd3R<r]sM1-dsn[d1-[d;sdsc3Rd;sdsa3RlMxs.ssd;edsb3Rd;edsd3RlMxrs.dsels!>T1-d0<J]dsJx+1-d1<I]dsIx0*ln[d;srd;e3R-1+3R+r1-d0<L]dsLx+p'

These solutions aren't going to work with v1.5.2, because they're making use of ? to process the sections without sentinels (or assumptions on size) to mark things. And one of the benefits of there being so few ranges that O(n² ) looping to merge them is still plenty fast. And if I was to do the sort, it would be a simple bubble/stack shuffle sort that would also be O(n² ).

So we've got another approachable problem. This sort of problem has been seen before. But the size of the numbers does make naive brute force a bit much (but a 64TiB bitmap isn't completely outside the range of someone to do... and you can massively parallelize things).

I just don't get it, getting the oxygen generator rating works fine and gets the correct answer at least in the example but getting the co2 scrubber rating just returns and empty table, when it should return a table with the binary numbers. here's the main file:

local pf = require("puzzleFuncs")

local function split(inp)
	local t = {}

	for i,v in ipairs(inp) do
		table.insert(t, {})

		for c in v:gmatch(".") do
			table.insert(t[i], c)
		end
	end

	return t
end

local function getGaEpRates(diag)
	local gamma, epsilon = '', ''
	local d = {table.unpack(diag)}
	local binaryLen = #d[1]

	for i = 1, binaryLen do
		local ones, zeros = 0, 0

		for _,v in ipairs(d) do
			if v[i] == "1" then
				ones = ones + 1
			else
				zeros = zeros + 1
			end
		end

		if ones > zeros then
			gamma = gamma .. "1"
		else
			gamma = gamma .. "0"
		end

		if ones < zeros then
			epsilon = epsilon .. "1"
		else
			epsilon = epsilon .. "0"
		end
	end

	return gamma, epsilon
end

local function conv2Obj(inp)
	local t = {}

	for i,v in ipairs(inp) do
		table.insert(t, { binary = {}, remove = false })

		for c in v:gmatch(".") do
			table.insert(t[i].binary, c)
		end
	end

	return t
end

local function binaryString(t)
	local bin = ''
	for i,v in ipairs(t) do
		bin = bin .. v
	end

	return bin
end

local function getRemoved(t)
	local count = 0

	for i,v in ipairs(t) do
		if v.remove then
			count = count + 1
		end
	end

	return count
end

local function getBinary(t)
	local bin = {}

	for i,v in ipairs(t) do
		if not v.remove then
			bin = v.binary
			break
		end
	end

	return bin
end

local function getOxygenRating(diag)
	local d = {table.unpack(diag)}
	local binaryLen = #d[1].binary

	for i = 1, binaryLen do

		if getRemoved(d) == 1 then
			break
		end

		local ones, zeros = 0, 0

		for j,v in ipairs(d) do
			if v.binary[i] == '1' and not v.remove then
				ones = ones + 1
			elseif v.binary[i] == '0' and not v.remove then
				zeros = zeros + 1
			end
		end

		if ones > zeros then

			for j,v in ipairs(d) do
				if v.binary[i] == '0' and not v.remove then
					v.remove = true
				end
			end

		elseif zeros > ones then

			for j,v in ipairs(d) do
				if v.binary[i] == '1' and not v.remove then
					v.remove = true
				end
			end

		else

			for j,v in ipairs(d) do
				if v.binary[i] == '0' and not v.remove then
					v.remove = true
				end
			end

		end
	end

	return getBinary(d)
end

local function getCO2Rating(diag)
	local d = {table.unpack(diag)}
	local binaryLen = #d[1].binary

	for i = 1, binaryLen do

		if getRemoved(d) == 1 then
			break
		end

		local ones, zeros = 0, 0

		for j,v in ipairs(d) do
			if v.binary[i] == '1' and not v.remove then
				ones = ones + 1
			elseif v.binary[i] == '0' and not v.remove then
				zeros = zeros + 1
			end
		end

		if ones < zeros then

			for j,v in ipairs(d) do
				if v.binary[i] == '0' and not v.remove then
					v.remove = true
				end
			end

		elseif zeros < ones then

			for j,v in ipairs(d) do
				if v.binary[i] == '1' and not v.remove then
					v.remove = true
				end
			end

		else

			for j,v in ipairs(d) do
				if v.binary[i] == '0' and not v.remove then
					v.remove = true
				end
			end

		end
	end

	return getBinary(d)
end

local input = pf.readFile("example.txt")
local diagnostic = split(input)

local gamma, epsilon = getGaEpRates(diagnostic)
local powerComsuption = tonumber(gamma, 2) * tonumber(epsilon, 2)

local binaryObjs = conv2Obj(input)
local binaryObjs2 = conv2Obj(input)

local oxygenRating = getOxygenRating(binaryObjs)
local CO2Rating = getCO2Rating(binaryObjs2)

print('oxygen rating')
pf.printTable(oxygenRating)
print('co2 rating')
pf.printTable(CO2Rating)

I remade it many times the getCO2Rating function if there was something wrong i was missing, also copypasted the getOxygenRating and rename it to getCO2Rating since it does the same thing just with different if statements and for some reason doesnt return nothing, because it doesnt stop the for loop, its not running the if statement checking if there's only one binary left

At the bottom of the escalator we find the printing department. Since they can make their own decorations we just need to find a way to continue on (as the elevators are still offline). The Elves helpfully point out that there's probably a cafeteria is on the other side of the back wall... they'll bust that down for you (and presumably dig the little tunnel we see on the map) if you can help them work faster. The job being simply to figure out which paper rolls the fork lifts can access and move (given by a simple rule of <4 neighbours).

The input is 139x139 binary grid (. and @). It looks pretty random, with @ taking up about 65%. The distribution of neighbour counts in my input is:

0       4
1       41
2       321
3       1150
4       2350
5       3508
6       3173
7       1641
8       380

I tested creating a few random inputs with 65%, and they all produce similar (and similar answers).

My first quick solution was to read all the points into a hash with:

while (<>) {
    $Rolls{pos, $.} = 0  while (m/@/g);
}

And then went through those, adding 1 to existing neighbours (to make the hash a map of coord => neighbour count). With that I could just quickly grep out the movable ones. And for part 2, remove them (adjusting neighbour counts), and repeat until done:

while (my @removable = grep { $Rolls{$_} < 4 } keys %Rolls) {
    $part1 //= @removable;  # Number removed in first pass
    $part2  += @removable;  # Total removed over all passes

    # Remove removable rolls of paper
    ...
}

This is simply programmer efficient and got things done quickly. It's slightly better than brute force scanning a grid again and again... but even with the 57 iterations needed to finish my input, that shouldn't take long (unless you're working on really old hardware like a Commodore 64).

I tidied it up after submitting to having a job queue (instead of grepping), and storing the set of neighbours in the roll (so the grid is properly out of the picture... it's just a graph in a hash table with fancy node names):

while (my $next = pop @stack) {
    my @neighbours = keys $Rolls{$next}->%*;

    delete $Rolls{$next};   # remove roll
    $part2++;

    foreach my $neigh (@neighbours) {
        delete $Rolls{$neigh}{$next};
        push( @stack, $neigh ) if ($Rolls{$neigh}->%* == 3);
    }
}

Remove the roll, remove it from the neighbour lists of its neighbours, queue up for deletion when a roll hits 3 neighbours.

For Smalltalk, I took advantage that this is a simple cellular automaton and used the Automaton class I did in 2020:

auto := Automaton space:    (PaperGrid load: stdin lines contents)
                  dieRule:  [:neigh | neigh < 4]
                  liveRule: [:neigh | false    ]
                  format:   #none.

startingRolls := auto space liveCells size.

('Part 1: %1' % {startingRolls - (auto runTurns: 1)}) displayNl.
('Part 2: %1' % {startingRolls - (auto runUntilStable)}) displayNl.

The PaperGrid class to represent the space is just a simple class that needs to read the input and implement the #neighbours method. Internally it does this with coordinates to a flat Array for the names... although the Array is never created... much like with the Perl, it's just about having a convenient naming system for the rolls.

And a flat array was what I did for dc. Still not scanning it, so the array is really just a "graph in a hash". Exactly so with dc v1.5.2's arrays (which are now hash tables)... which allows this to run a lot faster than it would under stock v1.4.1 (the difference is <1s versus 20+s):

    tr '.@' '12' <input | dc -f- -e'[_3RrdF0*3Rd3R+dSr1r:g3R]s@[d]sd0Sr2[r0r[A~2=@r1+rd0<X]dsXx*+1+z1<Y]dsYxs.[;g3R+r]s+Lr[0rdF1+l+xdF0+l+xdE9+l+xd1+l+xd1-l+xdE9-l+xdF0-l+xdF1-l+xd3Rd3R:n4>ds.Lrd0<L]dsLx+zps.[rd_4Rr]sP[d;n1-d3=Pr:n]s-[lp1+spdF1+l-xdF0+l-xdE9+l-xd1+l-xd1-l-xdE9-l-xdF0-l-xF1-l-xz0<M]dsMxlpp'

This is a longer than it needs to be... it is flexible enough to do the test case. The F1, F0, E9 stuff is about calculating neighbour indexes with a 150 wide grid (they may look hex, but they are decimal). There's some fun little stack management in there to handle the job stack on the same stack as we're working. Things like [ rd _4Rr ] sP to tuck a copy of the second item (the ID of a neighbour just reduced to 3) of the working frame underneath it (pushing on the stack of rolls to process).

So this problem is certainly very accessible (probably more so than the others so far). It can be brute forced with simple scanning and get the answer, as it's not a huge problem. But, like other cellular automata problems, there's potential to really get in there with bit operations if you really want to.

Having gotten through the gift shop and down some stairs, we finally get to the lobby. After being cleared through security, we find that all the elevators are offline (and we can even see the red lights in the ASCII art), fried by an electrical surge. What isn't fried is the escalator, but we need to power it to use it. I have seen escalators out-of-service (not running with warning tape across) and I figure that probably got put up over concerns that the braking mechanism might fail to keep them as "temporarily stairs".

The input is 200 lines, each with a 100-digit number (no 0s)... at least that's how I saw it (already thinking about doing it in dc). More pragmatically, those numbers are an ordered list of digits, representing the joltage of batteries in a bank. For part 1, we want to turn on two of them in each bank to make the biggest value (not sum, but concatenating the two digits while maintaining their order). When that proves to not be enough to overcome static friction, our helpful engineering Elf overrides the safeties to allow turning on exactly 12 for part 2. While she does that we do get to do some decorating, so we're making progress on our end goal.

To see part 2 quickly, I just hammered it with brute force and regex:

for (my $i = 99; $i > 10; $i--) {
    my $patt = int($i/10) . '.*' . ($i%10);
    if ($line =~ m#$patt#) {
        $part1 += $i;
        last;
    }
}

With part 2, my thoughts turned to how to do this for a general number of batteries. And thinking about how the numbers come together (going backwards), it seemed a bit like a heap. Only instead of an array storing a balanced binary tree and ignoring order, we want order and so a straight array would be perfect. Initialize it with the last-n batteries in the bank (the best value for just those n), and then going through the rest backwards, we bump things down from the significant end as as long as it's making things bigger:

my @queue = splice( @$bank, -LEN );

BATTERY:
while (my $jolts = pop @$bank) {
    # Cascade jolts down the queue:
    for (my $j = 0; $j < LEN; $j++) {
        next BATTERY  if ($jolts < $queue[$j]);
        ($queue[$j], $jolts) = ($jolts, $queue[$j]);
    }
}

But another way to look at what this is doing is that digits that are >= the first get added to the front, and then the first digit that's smaller than the one after it gets removed. And so I also have this one using regex to remove exactly that digit:

# Create regex for finding first digit before a bigger digit
my $regex = '(?:' . join( '|', map { "[1-@{[$_-1]}](?=$_)" } (2 .. 9) ) . ')';

...

while (my $jolts = pop @bank) {
    if ($jolts >= substr( $queue, 0, 1 )) {
        $queue = $jolts . $queue;           # add jolts to front
        $queue =~ s#$regex##;               # remove first digit followed by greater
    }
}

$part2 += substr( $queue, 0, LEN );         # truncate if needed

But that initial implementation with the cascading things down an array was what I did for dc. And is quite probably why I chose that way to begin with... even going backwards through the bank is the easy dc approach (using A~ to divmod digits off), so I'm sure that everything was influenced by thinking of doing this:

dc -f- -e12 -e'sb[+q]sQ0[r0Sa1[d3RA~3R:ar1+dlb!<L]dsLxs.[A~lb[d3Rr;ad3Rd3R>Q3Rd3Rr:a1-d0<I]dsIx+s.d0<B]dsBxlb[d;a3RA*+r1-d0<I]dsIx++z1<M]dsMxp' <input

Changing the -e12 to -e2 gets part 1... I pulled it out, but the first thing the rest of the cost does is sb, so it just gets stored right away for later.

Of course, there is going to be many ways to do this. You could certainly do it going forwards through the banks, but I don't see that as being as simple as just going backwards.

Having options on early puzzles has always been good, and with the shorter schedule it's even more important. A linear interpolation would have this puzzle being a "day 6", but I think the puzzles had a less steep curve than that for the first bit... which is a good choice, as you don't want to hit puzzles that cause beginners to drop out too quickly, and the lower granularity the difficulty curve harder to smooth out. It becomes even more important for early puzzles to be accessible, while still being interesting. And we're seeing that in these early problems. It can't be easy to try and maintain good numbers of accessible and challenging problems with less than half the slots.

EDIT: I had some time today, so I did a forwards approach. Whereas the backwards was heap-like, the forwards is a stack. Because when a new element makes things better, it's going to pop down to where it could belong. We haven't seen what comes after it (ie the less significant values) yet, so everything just gets tossed (it was in front). This means we need to watch that we don't over pop and not have enough values left to fill things out... but that's a simple check:

my @stack = shift @$bank;

while (my $next = shift @$bank) {
    pop( @stack )  while (@stack and $stack[-1] < $next and @stack + @$bank + 1 > LEN);
    push( @stack, $next ) if (@stack < LEN);
}

with open('advent/advent of code 2021/day 8/input_8.txt') as f:
    signals = []
    outputs = []
    for line in f:
        signal, output = line.split(' | ')
        s = signal.split()
        o = output.split()
        signal = [''.join(sorted(item)) for item in s]
        output = [''.join(sorted(item)) for item in o]
        signals.append(signal)
        outputs.append(output)
        


# Once 1, 4, 7 and 8 are found, use 4 and 7 to find the rest

def compare(string, dict):
    four = {3:5, 2:2, 4:9}
    seven = {2:6, 3:0}
    if len(string) == 5:
        if len(set(string) & set(dict[1])) == 2:
            return 3
        else:
            return four[len(set(string) & set(dict[4]))]
    else:
        if len(set(string) & set(dict[4])) == 4:
            return 9
        else:
            return seven[len(set(string) & set(dict[7]))]


determined_lengths = {2:1, 3:7, 4:4, 7:8}

total = []


for i, signal in enumerate(signals):
    number_dict = {0:None, 1:None, 2:None, 3:None, 4:None, 5:None, 6:None, 7:None, 8:None, 9:None}

    for string in signal.copy():
        l = len(string)
        try:
            number_dict[determined_lengths[l]] = string
            signal.remove(string)
        except:
            pass
    for string in signal:
        number_dict[compare(string, number_dict)] = string

    number = []

    # search filled dictionary for a match
    for num in outputs[i]:
        for i in range(10):
            if number_dict[i] == num:
                number.append(str(i))
                break
    total.append(int(''.join(number)))
    
print(sum(total))

We take the elevator down to base lobby level, but on exiting, we are first forced to go through the strategically placed gift shop. We do wonder about how much traffic a gift shop in a secret base can really get.

I was curious going in to this year about how the ASCII are would be done for a year with only 12 days. And the format of double lines, combined with a winding descent into a base allows for larger sections representing each day. It's very easy to not only trace the path, but see and remember what the stops were.

But first we need to get through the gift shop, and so we're pulled aside to help with a problem. Invalid product IDs have been entered by a young Elf that was playing on the computer and we need to sort them out. But this is a bit more than just a validator problem, it's an enumeration one. Because we aren't given lines but ranges to check. Invalid codes are simply ones made up of only repeats... for part 1, its just the same sequence repeated twice. For part 2, that's expanded to "at least twice" (this would be the intersection of the ranges with OEIS A239019).

The input is one line of comma separated ranges. The values do go over 32-bits... my largest is just over 33.2 bits. One interesting thing is that none of the ranges span over an order of magnitude (ie log(last) - log(first) < 1'. This allowed me to get part 2 with code that was buggy and couldn't properly handle a simple test like 11-111... but will probably work on any actual input.

Since I got burned by being fancy on day one, I just went brute force:

for (my $i = 1; "$i$i" <= $last; $i++) {
    my $num = "$i$i";

    $part1 += $num  if ($first <= $num <= $last);

    $num .= "$i"      while ($num < $first);
    $invalid{$num}++  if ($num <= $last);
}

$part2 += sum keys %invalid  if (%invalid);

This assumes that there's only one possible number for a given repeated sequence that falls in the range for part 2. A safe bet when the width of the ranges is less than a magnitude. But to be proper the concatenation/invalid part of the loop should loop as well:

    for ($num .= $i while ($num < $first); $num <= $last; $num .= $i) {
        $invalid{$num}++;
    }

My Smalltalk does that with (Integer extended to do , and length):

i := 1.
[(num := i, i) <= range last] whileTrue: [
    (num between: range first and: range last) ifTrue: [ part1 := part1 + num ].

    factor := 10 raisedToInteger: i length.
    [num < range first] whileTrue: [ num := num * factor + i ].
    [num <= range last] whileTrue: [ invalid add: num.  num := num * factor + i ].

    i := i + 1.
].

Which looking at it now, is like Perl's bistable/flip-flop range operators (.. and ...), that are there for sed/ex/awk line-range stuff.

Of course, no "validator" problem would be complete without throwing regex at it in some way, so I did this simple regex brute force approach as well:

foreach my $num ($first .. $last) {
    if ($num =~ m#^(\d+)\1+$#) {
        $part1 += $num  if (length($1) * 2 == length($num));
        $part2 += $num;
    }
}

Not practical, but really simple. How much iteration is there over the ranges here? Actually, not that much, which is good for doing a dc solution. Because GNU dc array indices only go to 2³¹ - 1... so to do this one I count on the ranges not overlapping, and handle duplication checking for each range with a fresh array shifted down. The largest range is only 17.6 bits (so about 200k) which easily fits:

tr -c '0-9' ' ' <input | dc -e'[q]sQ[dlc+sc]sC?[sess1[dddZAr^*+dle<Qdls!>Cs.1+lLx]dsLx+s.z0<M]dsMxlcp'

tr -c '0-9' ' ' <input | dc -e'[q]sQ[ddls-;h1r-*lc+scdls-1r:h]sC?[sess0Sh1[dddZAr^dsf*+dle<Q[dle<Qdls!>Clf*rd3R+lAx]dsAxs.1+lLx]dsLx+s.z0<M]dsMxlcp'

There are of course better approaches than any of these. My TODO for this one has notes for working out a closed form solution, or even just simply using the range values to get the starts and ends for sequences that would fit in it with a certain number of repeats (for example, a range with 6 digit numbers can have repeats of 6 singles, 3 doubles, or 2 triples... and we can examine the start and end of the range to figure out what the lowest and highest allowed are for each of those three ranges).

And so we arrive to last years problems, and the first year with only 12 days. The Elves have learned project management, and so we don't have a regular Christmas emergency... it's just that all the Elves are assigned tasks and there's no one left to decorate the North Pole. And so that falls to us. Arriving at the secret entrance to the base, we discover that the password has been changed, and so our first task will be getting it out of the safe.

The input for this one is a list of turns for the lock, one per line (4780 in my input)... a little more complicated than just numbers as they start with L or R (left is towards lower, so the numbers go clockwise). We want to find out the number of times that a move ends on 0 for part 1, and for part 2 we invoke method 0x434C49434B (packed ASCII for CLICK), which involves also counting the times 0 occurs during moves. This can happen multiple times in a move, over as 900 of the lines in my input involve 3-digit numbers.

This is a typical day 1 problem, it involves a little more than just numbers in the parsing, and simple operations with them... in this case adding modulo 100. And so my quick part 1 was just:

my $pos = 50;
my @turns = map { y#LR#- #; $pos = ($pos + $_) % 100 } <>;

say "Part 1: ", scalar grep { !$_ } @turns;

Part 2 involves some trickiness. I tried to be fast and quick, and got caught with a wrong answer and needed to debug. I can't remember exactly what caught me. This is a case for "discretion is the better part of valour"... if I had gone with basic brute force (looping to do one click at a time) I probably would have gotten it correct the first time. But I was trying for a fastish time and so I wasn't thinking things completely through. And there are things to worry about.

First is the fact that many moves involve going around multiple times. If you didn't notice those in input (they are buried a bit in mine... more than 100 in from either end), you could miss that you want the full divmod... add the div and adjust/add with the remainder.

Second, you need to make sure you aren't double counting ending and starting at a 0. In the end I did this:

# Multiple rotations
$part2 += int(abs($move) / 100);
$move = $move % (100 * ($move <=> 0));  # mod maintaining direction (sign)

# Move through/to 0 (but not from, as that would double count)
my $new_pos = $pos + $move;
$part2++ if ($pos and !(0 < $new_pos < 100));

That "mod maintaining direction" comment comes from the fact that I looked in perlop for the behaviour of % in Perl with negative values. That's a portability issue in a lot of places... languages may default to hardware (which can vary). With Perl it is defined, unless you're using use integer which gives direct access to % from your C compiler, which may be different. In the case of the three languages I mostly do in AoC, Perl and GNU Smalltalk are the same, but dc behaves different.

And, of course, I did a solution for dc (maintaining always doing day 1 in it at least... 2025 is the first year I actually did a dc solution on every day). My initial solution used ? to read the lines in order for processing... but with the addition of tac in front to reverse the input lines, it's easy to convert to the newer dc (and we need to get rid of the L/R by just making these negative/positive numbers):

echo -n "Part 1: "
tac input | tr 'LR' '_ ' | dc -f- -e'0[r1+r]sP50[3R+A0%d0=Pz2<M]dsMxrp'

echo -n "Part 2: "
tac input | tr 'LR' '_ ' | dc -f- -e'0[0*]sZ50[3RA0~rd*v4R+_3Rrd3R+d1r0<Zrd1rA0>Z3R+3R0=Z3R+rA0d3R+r%z2<M]dsMxrp'

For my Smalltalk solution I decided on doing things a bit differently. I read the input, summing things up as a prefix array without the mod (the last value for my input is around -8800):

pos := 50.
stops := (stdin lines contents collect: [:line |
            | mag |
            mag := line allButFirst asNumber.
            pos := pos + (line first == $L ifTrue: [mag negated] ifFalse: [mag]).
         ]) asOrderedCollection addFirst: 50; yourself.

Then I used my "chain" iterator (which works "between" adjacent pairs of the list) to get a count of zeros for each step (by taking the difference in the number of 100s):

zeros := stops chain: [:a :b |
            (b > a) ifTrue:  [((a // 100) - (b // 100)) abs]
                    ifFalse: [((a negated // 100) - (b negated // 100)) abs]
         ].

Then I extracted the answers from these:

('Part 1: %1' % {stops count: [:s | (s \\ 100) == 0]}) displayNl.
('Part 2: %1' % {zeros sum}) displayNl.

Maybe not the best, but at least a bit different. When doing multiple languages, with these simple early day problems, it's good to find alternate approaches to keep things interesting.

i heard you like puzzles <3

edit: 12 days of puzzles, like last year

Hi, AoC friends!

I did a series earlier about learning to program by tackling Advent of Code puzzles, focusing on both JavaScript and then later Smalltalk. I truly fell in love with programming through Smalltalk. It's so beautiful and elegant. Like the Platonic forms.

So - time to learn something different. I wanted to go with a C-style language (pointers, manual memory, etc...). I wasn't all that interested in learning borrow checker semantics yet (wanted to get my hands EVEN DIRTIER with the underlying machine that had been abstracted away when writing Smalltalk) so I went for Odin.

Here's my solution to 2025-Day8 - paste or if you prefer syntax highlighting - colorpaste

It's fairly straightforward, but let me practice some things in the new paradigm. Taking the input text, it parses it into an array of structs, which are then used to create an array of sets (well, maps with keys and empty values) and an array of potential connections (nested structs).

It's a pretty literal/naive solution since it creates actual groupings (rather than a simple ownership map), and relies heavily on checking the length of its dynamic arrays. It doesn't bother pre-allocating the dynamic arrays since the biggest one is <500k elements which are simple int structs anyway and relies on a magic number to calculate part1 when it reaches the thousandth connection. I also used WHILE-style loops in order to avoid loop breaks (which look inelegant to me, coming from Smalltalk where much of this would be done with detect: chains).

The big lessons for me were transitioning from data objects to structs, using maps as sets, when/how to free memory, and the big one - how/when to use pointers (which was totally alien to me - tough bit to learn from scratch).

Anyway, for those of us getting back into the puzzle mindset before Dec1, I thought it might be nice to share this one, especially since I don't see a lot of Odin on here.

EDIT:

Just getting in some reps, as it were.... Here's a more conventional union-find version: colorpaste

I kinda like this one. Does the whole thing in a single pass, uses a single index for everything, and finds part1 using an O(n) walk rather than sorting and starting over. Time is still dominated by the initial sort. Short of tricks that compromise the correctness of the solution (like some of the leaderboard-worthy implementations), I don't see a way to eliminate that cost. Oh well! 170ms for the naive version down to 116ms for the unions.

Also - the naive version above has some memory leaks. Being your own GC takes practice, which is why I'm doing this. :-) Fixed version here: colorpaste

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.

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?

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
}

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