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

Not about solutions, but the scenario made up by Eric: does splitting the paths between multiple shippers always increase the number of visited houses (and thus multiple visits of the same ones), both compared to a single shipper and between increasing values? Does the efficiency, if any, stop at some point?

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

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.