u/musifter

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

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

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

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

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

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

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

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

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

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

First stop in our search is the nuclear plant where we made medicine for Rudolph in 2015. While the Historians search for their Chief, we agree to help analyze some data for the engineers.

And so we get another problem that just deals with numbers. The input has 1000 lines, each is a report which is a list of 5-8 numbers in the [1,99] range. A safe report is one which is monotone increasing or decreasing, and adjacent levels differ in the range of 1 to 3. For part 2, we discover that they have a Problem Dampener, that tolerates a single bad level.

Since I wasn't feeling well, I just brute forced this. Took the diffs and:

$part1++ if (all { abs($_) <= 3 && ($diffs[0] * $_) > 0 } @diffs);

For part 2, if this fails, I try splicing out each number in turn until one works (on not). I remember thinking a little bit about trying to spot the problem on the go... and it went like: if I get to the third number and discover there's a problem, the first or second could still be the problem to remove. And with these short lists, 3 items is a huge portion of it. So simpler to just go with programmer efficiency and test them one at a time. If things were longer it'd make more sense to get into doing things smart.

One interesting thing to note with the solution above is the use of arithmetic logic. I was already thinking of how to do this in dc. And so the trick in there to tell if things are monotone increasing or decreasing... I multiply each diff with the first. If that's always positive, things are monotone (ie all diffs have the same sign as the first one).

A side effect of this type of arithmetic logic is needing to consider the 0 value. And here we see it used to handle a case that appears at first glance to be missing... the check that the difference is at least 1. A difference of 0 fails the second multiplication test, and so that check actually handles 1½ of the rules.

In any case, the dc ended up as:

dc -e'[0*]sZ[1+]sC0?z[2-dsn[3Rd4R-Sdr1-d0<I]dsIx*ld+sa0ln[rLddd*v3<Zla*0<Cr1-d0<I]dsIx+ln/+?zd1<M]dsMxrp' <input

The combining of the two rules is done by conditionally multiplying difference >3 by 0, making that 0 in the second part of the test cover both parts. Another little trick in this one was that it keeps a count of the number of steps that pass and then divides it by the number of steps... a simple way to check that they're equal and get a 1 or 0 to add to the total for the answer (as we're working with 0 precision). And, whereas yesterday, the use of ? wasn't really that important to tell things apart, here each line has a different number of numbers... and being able to read the input one line at a time is useful without having to add delimiters to the input (although 0 is conveniently available for that).

And so for a problem I basically brute forced, I did do some interesting stuff in my solutions.

For 2024, we're tasked by the Elvish Senior Historians with finding the Chief Historian in time for the sleigh launch. Which serves as the conceit for revisiting past locations to celebrate the 10th year. And so the ASCII art for this year is just a big number 10, with little bits of past years' art inside it.

The first task is working out the location IDs of where to search. And the Elves have produced two lists, and we get to compare them. And so we're back to just having plain numbers (5 digits) to work with on day 1... although in two columns with 1000 lines. The numbers in the first column are unique, the ones in second column are not (as needed for part 2). I didn't bother to make use of that, but you could.

I was really quite sick for the last half of November in 2024, and still wasn't feeling up to doing much... so I had extra low asperations for solutions right from the start in this year. Especially after 2023 had been a step up in difficulty (but I didn't find this year quite as hard... or maybe the problems were just more my style).

For my initial Perl solution, I just read the columns into two lists (and sorted those), while also making a histogram of the values in column 2. Then it was just:

say "Part 1: ", sum map { abs($_->[0] - $_->[1]) } zip \@list1, \@list2;
say "Part 2: ", sum map { $_ * ($counts{$_} // 0) } @list1;

For Smalltalk, I just threw the two columns into separate Bags, and then:

part1 := ((lists first sorted) with: (lists second sorted) collect: [:a :b | (a - b) abs]) sum.
part2 := (lists first collect: [:a | a * (lists second occurrencesOf: a)]) sum.

Dc added some issues, because it doesn't have a built in sort for part 1... so I needed to do one. And with the limited values and the nature of the problem, I went with a counting sort.

dc -e'[q]sQ?[d;b1+r:bd;a1+r:a?z0<I]dsIx[A 5^[dlGx[d0=QrdlPxr1-lJx]dsJx+1-d0<I]dsIx]sS0Sc[;a]sG[Sc]sPlSx[;b]sG[Sd]sPlSx0[Lcd0=QLd-d*v+lLx]dsLxrp' <input

The tricks here are that I first read the values into histogram arrays a and b (using ? to do things one line at a time, so the older dc is required). Then I have a double loop that counts down from 100000, and then pushes the index count-number of times onto a register stack. Since I need to do this for 2 columns, I parameterized the sort macro with macros to Get and Push from/to the correct places:

[;a]sG [Sc]sP lSx       # convert array a into sorted stack c
[;b]sG [Sd]sP lSx       # convert array b into sorted stack d

But I did do part 2 in dc first... because it was a lot simpler because it has no sort. But it also wants a histogram, and so it does occur to me that doing something like counting sort could be a good option for doing both parts at the same time.

dc -e'?[d;b1+r:bSa?z0<I]dsIx0La[d;b*+Laz1<L]dsLxp' <input 2>/dev/null

Note that it's piping to /dev/null an warning message for popping an empty register stack. Not adding a sentinel to the bottom of the register stack saves 4 strokes.

And so we've got a classic day 1 type problem... read numbers and do something simple with them. I will note that there is the unusual use of the word "distances" in part 1, where you would normally use "differences". So there is a bit of obscuring.

And so the expected shoe drops... the snow-making process has a problem, and it's forming hail that we need to break up. Conveniently the hailstones are being blown by magical winds, and so our physics is just linear. And so we have a problem that can be thought of as physics and/or linear algebra.

The input for this one is 300 hailstones. The consist of a 3D position and a 3D velocity vector. The positions in the input are eye watering numbers in the trillions to hundreds of trillions (the range for mine is ~42.6 bits to just short of 49). The numbers on the velocity side are on (-1000, 1000) (the largest magnitude in mine is 958)... with 0 excluded.

Part 1 wants us to ignore the Z axis, and considering the projection onto the XY-plane, find the number of intersections that occur within a bounding box, in the future (t > 0).

There's a number of ways to do this, and given expected arrival of the 3rd dimension, I went with Cramer's Rule and turning the hailstones into linear equations of ax + by = c (ie Ax = c as a matrix). To do that, I just considered y = mx + b. Where m is slope, which it rise-over-run which is vy/vx (with no fear of 0).

y = mx + b
y = (vy/vx) * x + b
vx * y = vy * x + c   (the intercept gets modified, and so I change the name to c).

-vy * x + vx * y = c  (c can be calculated from the input line values)

With that form, the intersection is just a determinant / determinant:

my $det = $b2 * $a1 - $b1 * $a2;

return (undef)  if ($det == 0);
return( [($b2 * $c1 - $b1 * $c2) / $det, ($c2 * $a1 - $c1 * $a2) / $det] );

So I just run through all the pairs (double nested triangle) and verify an intersection and that the time values are positive. I actually calculate them, but you could just worry about the sign if you want to avoid the division:

my $t1 = ($res->[X] - $stones[$i][X]) / $stones[$i][VX];
my $t2 = ($res->[X] - $stones[$j][X]) / $stones[$j][VX];

$part1++ if ($t1 > 0 and $t2 > 0);

For part 2, the 3rd dimension is in play, and we're tasked with finding a spot to stand and a velocity to throw a rock, so that it hits all the stones. Again, this isn't really a physics simulation, as the rock doesn't get effected by these collisions... it's just a line.

And my thoughts immediate on this go to that classic axiom of puzzling, that since this is a puzzle it is designed to have a solution. And that assumption can be used. Imagining I had two stones flying in front of me (and we've picked things aren't parallel and could cause problems), I could line up a shot that hits them both and the time between them would tell me how far back to stand. As they move, that line changes. But if I add a third rock to hit, that should fix the line (because puzzle). Two points make a line, three make the pattern. And so I should only need three points (but the others can be used to verify).

And so I started looking at equations. And this was my basic idea:

    X  <--S     Stone and the rock hit at X at time t.  The vector Vs - Vr, points
         /      back to the place the rock came from, and would travel from S to R
    ^   L       in the same time t.
    |
    R

I know some people visualized this in physics terms... imagine you're the rock and convert all the stone vectors into that frame of reference. It's really the same, I just came at it a bit different, because I was thinking algebra.

Next up was looking at getting a system to solve the variables. And there were more variables than I wanted to deal with, and so I cheesed it a bit. I called the rock vector (i,j,k) for a reason, and that was because I assumed that the velocity vector would be on the same scale as the stones (in fact, the largest magnitude on the rock for my solution is 286), and so I could brute for over i and j and make them constants... and k could be solved after. Here's the comment from the code:

# If we subtract the velocity vector of the rock (i,j,k) from each stone's
# velocity, at their time t (the time the stone is hit), they all add to the same point:
#
#     x1 + t1(vx1 - i) = x2 + t2(vx2 - i)
#
# Reworking that:
#
#     t1(vx1 - i) - t2(vx2 - i) = x2 - x1
#
# Which is a line of form ax + by = c, where the times are x and y... providing
# we make i a constant (which we're doing by brute forcing to try values for it).

And so, I used the function for line crossing from part 1, with X and Y coordinates of two stones, with brute forcing i and j (to consider them constants), to get potential times for impact on those stones. Then I check that that was a collision, and the times are positive and different and integers (because AoC answers... no need to bring in the possibility of rationals making integers until necessary).

With that, I then take the 1st stone and do the same with a 3rd. If I get a valid collision and the collision time for stone 1 is the same again (and leading to the same spot as the collision with stone 2 made it point to), I assume we've lined up our shot.

Next up is calculating k:

# Calculate k (the z part of the rock vector)
#
# t1(vz1 - k) - t2(vz2 - k) = z2 - z1
#
# k(t2 - t1) = z2 + t2(vz2) - (z1 + t1(vz1))
#
# k = (z2 + t2(vz2) - (z1 + t1(vz1))) / (t2 - t1)

Which is really just working out the obvious, it's the difference in the collision positions of two stones divided by their delta-time.

Then I just followed the the vector from the first stone back to the rock start:

my $x = $stones[0][X] + $time12->[0] * ($stones[0][VX] - $i);
my $y = $stones[0][Y] + $time12->[0] * ($stones[0][VY] - $j);
my $z = $stones[0][Z] + $time12->[0] * ($stones[0][VZ] - $k);

With (x,y,z) and (i,j,k) I can now validate all the stones if I want more confidence. But this worked and got my answer, so I didn't do more.

Like a lot of these last few days, I was happy with just having a solution that solved the problem at hand. I did spend a few hours thinking on this one, before ultimately just simplifying things to just get an answer (so I was getting tired). I can at least say that I did make good use out of the solution to part 1 for my part 2.

With the parts found, and the machines fixed, next up is the boot sequence. And so we have a circuit problem. Cables connecting modules, sending pulses between them, and a button to push to start it. Also a warning to never push the button again until after the pulses stop.

Reading the directions we find flip-flops, which are bits of memory, and conjunction modules, which are NAND gates (and functionally complete... which includes being an inverter (which the Easter Egg informs us was almost a separate thing, giving a little insight to development)). And so just knowing that, I can already see that this could be a very interesting and complicated machine. For the simulation there is a bunch of rules/clarifications on how to do this asynchronous machine. There isn't a state-wide clock and turns, so the pulses take turns in a queue (so they spread breadth first). And the pulses are describes as high and low, as that's how 1s and 0s are in hardware... a zero voltage is the ground state (binary logic is: high, low, ground, and don't-care... in yes/no question terms that's: yes, no, mu, and meh).

Part 1 wants us to just get the number of high and low pulses sent after the button has been hit 1000 times. So naturally, to see part 2 (which I suspected was going to involve cycles and hitting the button a lot), I just used a loop to do that, and counted them at the top of the queue loop:

# broadcaster is honourary flip-flop, always starts high
$Circ{broadcaster}{state} = 1;
my @queue = ([0, 'broadcaster', 'button']);

PULSE:
while (my $pulse = shift @queue) {
    my ($bit, $targ, $src) = @$pulse;

    $pulses[$bit]++;
    next PULSE  if (!defined $Circ{$targ}{type});   # output only nodes

    if ($Circ{$targ}{type} eq '&') {  # NAND
        $Circ{$targ}{$src} = $bit;

        my $state = int !(reduce {$a & $b} (1, map {$Circ{$targ}{$_} // 0} $Circ{$targ}{in}->@*));
        push( @queue, map { [$state, $_, $targ] } $Circ{$targ}{out}->@* );

    } else {  # flip-flop or 'b'roadcast
        next PULSE if ($bit);

        my $state = $Circ{$targ}{state} = int !($Circ{$targ}{state} // 0);
        push( @queue, map { [$state, $_, $targ] } $Circ{$targ}{out}->@* );
    }
}

Part 2, makes use of the output node: rx, which is the machine to send the sand down to Island Island. It turns on when it gets a low pulse. We want the lowest number of presses (suggesting cycles) to do that (with a warning to reset the machine).

As stated, this machine is potentially capable of a lot. And so that prompts me to reverse engineering and specializing the code. So looking at the actual input, there are 48 flip-flops (so the answer can be expected to be on that scale... and mine does require a 48-bit unsigned). So the brute force attempt I had started "just in case" wasn't going to complete very soon, and could be stopped. I messed around looking at patterns with the flip-flops a little bit, but then moved on to the NAND gates.

There are only 9 of them... one leads into rx (and thus is an inverter). Leading into it are 4 other NAND gate inverters, and the remaining 4 NANDS each lead into one of those (but are actual NAND gates, with multiple flip-flops in and out). So with that determined, I wanted to see when the four key inverters get triggered, and simulated that. And each does on a prime number of pushes (all four are primes about 4000). So I multiplied them and submitted for the answer, which was correct. Then I wrote the code to collect them and threw on an lcm for safety. Technically, I should properly confirm that the state is looping, but still haven't bothered. But as part of my input I do dump the memory state for fun:

say "Memory: ", map {$Circ{$_}{state}} sort grep {$Circ{$_}{type} eq '%'} keys %Circ;

If I was looking for efficiency, I probably would have arranged that first, and just stored the flip-flops as a 48-bit numbers and do bit twiddling for the pulses. And maybe I should do that for the Smalltalk version as it takes a few seconds to do 4000 pushes with the components in a Dictionary. But that code does use some actual OOP stuff though... it has a virtual Gate class for an interface that FlipFlop and NANDGate implement. And so the actually process loop sees everything the same.

This was a fun day. I guess at this point, this takes the place of an assembly VM problem, as those had been largely played out.

The mirrors were pointing at a parabolic reflector dish which is probably used to heat the lava. And which also has its mirrors in disarray. There's a system involving a platform and rolling rocks to align things by tilting, spinning, and deforming. We need to spin it to get the rocks to the edges of the platform, but want to make sure that the structure can bear the load.

And so we get a 100x100 grid with three values... in addition to empty (.) and solid block (#), we have rolling rocks (O). Part 1 just requires tilting it north and calculating the load after the rocks stop. And for my initial solution, I didn't actually bother moving the rocks... I just used a state machine in the direction of travel for each column. The idea is simple... count Os, and when you get to a #, add the difference of triangular numbers to the answer (and reset the counter). Because all the rocks in that section roll to the top (which is the direction of scoring increase), so the score of them is the big triangle of the top rock minus the triangle under that train of rocks:

for (my $y = $#Grid; $y >= 0; $y--) {
    if ($Grid[$y][$x] eq 'O') {
        $count++;
    } elsif ($Grid[$y][$x] eq '#') {
        my $h = @Grid - $y - 1;
        # difference of triangles: [h(h+1) - (h-c)(h-c+1)]/2
        $part1 += ($count * (2 * $h - $count + 1)) / 2;
        $count = 0;
    }
}

I was clearly thinking of doing this in dc (this solution is designed to be simple to implement), and did do part 1 later:

perl -pe's/(.)/$1 /g;y/.O#/012/' input | dc -e'?zdsn[d2r:a1-d0<I]dsIx+[[zd;a3*3R+r:az0<L]dsLx?z0<M]dsMx[lc1+sc]sC[rdlcd3R2*r-1+*2/ls+ss0scr]sSln[d;a0r[3~d1=C2=Sr1+rd0<H]dsHx*+1-d0<I]dsIxlsp'

My notes pointed out that I wasn't feeling well that day, so this was done quickly. That probably also explains the lack of a Smalltalk solution on this day.

Part 2 is the classic scale up... do a full spin cycle (all four directions in NWSE order) one billion times. My initial solution for this used the Vector class and did the above state machine. Clear Os when you count them, backfill when you hit a #.

And then we need cycle detection (standard find the loop, use that with some modular arithmetic to get the answer). And for a quick answer at first, I just used the load score function, and to be safe I looked for a duplicate cycle (not just the first repeat, but two repeats of equal size... 2 points is a line, 3 is pattern). And I did double check that the numbers were also the same in the two ranges for added safety (not actually needed for my input). Then I used dc to do the calculation for the index and copy-pasted from the script output to submit. I later wrote the code to do the calculation, and also did a perfectly safe version (that's actually just as fast), using a massive hash key of the positions of all the rolling rocks (so no question that the first repeat is a cycle). As I wasn't feeling well, this one got left in that state.

Coming back to it, I saw it ran in over 20s. And figured that was mostly Vector overhead (it was worth for quick coding at the time). And sure enough, it's an order of magnitude faster without it. Playing with it further, I decided to reverse the state machine... run it the direction opposite the motion. The only reason I did it the other way was the convenience for part 1 and dc. The backwards state machine is about 9% faster... it doesn't have that backfilling loop. Instead, if works like this:

for (my $j = 0; $j <= $Size; $j++) {
    my $tile = $Grid[ $x[0] ][ $x[1] ];
    if ($tile == 1) {
        $pos[$mdim] += $mdelta;
        $Grid[ $x[0] ][ $x[1] ] = 0;
        $Grid[ $pos[0] ][ $pos[1] ] = 1;
    } elsif ($tile == 2) {
        @pos = @x;
    }

    $x[$mdim] += $mdelta;
}

When we get to a # we set pos to it to know where to roll rocks to. Then when we find rocks, we increment that and move the rock. For a tiny extra boost, I also switched to an (axis, delta) pairing for the vectors instead (x,y). There's still more that I could have done, especially with scoring and hashing. But this is good enough for now... how often does this load need to be calculated?

Heading towards the "Hot Springs", we arrive at an observatory. And the Elf there will show us the way, after we help with his analysis.

And so we get what appears to be a 2D grid problem. My input is a 140x140 grid of mostly empty space (.), with 450 galaxies (#). We want the sum of distances (Manhattan) between all the pairs. But as is the case with astronomy... you look at stuff at billions of light years away, but that's was where and what it was like billions of years ago. It's now much further away due to expansion. And so we need to work that out. And the rules given are that any empty row or column becomes twice as big.

And I guessed that part 2 would be making things bigger in some way. So to see what that was, I just brute forced part 1 to begin with. I was experimenting with the Math::Vector::Real module for handing points and vectors at this time, and it has some overhead, but if the task isn't too bad (and this one isn't), it can make up for it in simplicity of coding and legibility. One nice thing is that the constructor is short and simple: V(...). Another thing is that it has built in distance functions (and this was an opportunity to use one). The one problem I have with it is the print string... I'd rather have it plain and using $;.

So it was very easy to just do the thing... shift the coordinates, and double-triangle loop the pairs:

my $dist = 0;
foreach my $i (0 .. $#shifted-1) {
    foreach my $j ($i+1 .. $#shifted) {
        $dist += $shifted[$i]->manhattan_dist( $shifted[$j] );
    }
}

And since part 2 only made the gaps bigger, I had another really fast turnaround by just changing the scale factor for:

$g += V($yshift, $xshift) * $scale;

At which point the script ran equally fast to part 1 (there's no additional work), which was an immediate answer. I suppose after the pipes and interpolation on the weekend, this is a break Monday. Because it really didn't force things to be better. What did that for me was deciding to do a dc version (and I did Perl and Smalltalk versions from that). I do have a bigger test case (280x280 with 5000 galaxies) that someone posted at the time to help prompt people to do that as well. That one makes my brute force take a minute and a half.

But for me, I was thinking while doing the brute force, and it was not lost on me (while thinking of tricks that might be needed for part 2 scale-ups) that Manhattan distance makes the x and y parts independent. Which is the point I decided to definitely do a dc solution... because with that realization, the problem turns from 2D to 1D. Basically, the grid can be collapsed to lists of row sums and column sums, and then discarded. And short lists of numbers to chew on, that's something for dc.

The other thing I thought about was that getting the sum of absolute differences of all pairs is a typical programming test problem. And it's largely the same sort of math I was working with on day 9 as well. The trick here is that a little algebra can collapse things into multiplication and make things a single loop.

For example, consider the list 2 3 5 8, and we want the sum of the absolute differences of the pairs. As a table:

    2     3     5     8
2   X   (3-2) (5-2) (8-2)   2 is subtracted 3 times             = (0-3) * 2
3   X     X   (5-3) (8-3)   3 is subtracted 2 times and added 1 = (1-2) * 3
5   X     X     X   (8-5)   5 is subtracted 1 time  and added 2 = (2-1) * 5
8   X     X     X     X     8 is added 3 times                  = (3-0) * 8

So there's a pattern in coefficients: -3 to 3 by 2 (where those 3s are the #numbers - 1).

Of course the problem is a little more that that here... as we have a multiple of the numbers at each step (number of galaxies in that row or column). But it's not that hard to work out the adjustment to do that as well. The end result (as an extension to Array) in my Smalltalk solution is:

diffSum_expand: scale [
    | col seen sum number |

    number := self sum.
    col := seen := sum := 0.
    self do: [ :count |
        col  := col + ((count = 0) ifTrue: [scale] ifFalse: [1]).
        sum  := sum + ((2 * seen + count - number) * count * col).
        seen := seen + count.
    ].
    ^sum
]

And the dc (which still isn't fully golfed):

perl -pe's/(.)/$1 /g;y/.#/01/' <input | dc -e2 -e'ss?1[0[3Rd3R+rz2-d_3R;c+r:cz2<X]dsXxdlg+sgrd_3R:r1+?zRz1<Y]dsYx[ls*]sE[0sc0sa0r[dlAxd1r0=Elc+scddla2*+lg-*lc*rla+sa3R+r1-d0<L]dsLx+]sD1-[;r]sAdlDx[;c]sArlDx+p'

Change the -e2 to -e1000000 for part 2 (or whatever scale you want).

So this was another really fun day.

As the sandstorm clears we find the maps lead to an oasis. There's a hang glider here to get up to the next island, but we'll need the sun to rise to create an updraft first. And so we decide to spend our time studying the oasis. Collecting data, we want to do some interpolation, and so we get to work with finite differences and discrete Taylor series.

My time for part 1 was just under an hour. Part of that was a late start and a bug where I took the opportunity to get ice cream (I remember this... the bug really was nothing, I just wanted some of the ice cream I had bought the day before as a debugging snack for later days). And a chunk of time was spent just making sure I could still work out a polynomial interpolation like this by hand (the third line in the test is f(x) = 1/3 x^(3) - x^(2) + 11/3 x + 10).

But then I realized that I hadn't even seen part 2 yet, and quickly coded up a part 1... it was a good opportunity to use the chain operator I had built in past years again:

do {
    $i++;
    $table[$i] = [chain {$_[1] - $_[0]} $table[$i-1]->@*];
} until (all {$_ == 0} $table[$i]->@*);

$part1 += sum map {$_->[-1]} @table;

Then I saw part 2, and had one of the quickest turn arounds of the year with this diff:

18c18
<     my @table = ($list);
---
>     my @table = ([reverse @$list]);

I did do a combined version after that using this for part 2 (after the part 1 line):

$part2 += reduce {$b - $a} reverse map {$_->[0]} @table;

For Smalltalk, I used the alternating sum trick to do that difference reduction:

[row conform: [:n | n = 0]] whileFalse: [
    " Part 1 is sum of lasts, part 2 is alternating sum of firsts "
    part1 := part1 + row last.
    part2 := part2 + (mult * row first).
    mult  := mult negated.

    row := row chain: [:a :b | b - a].
].

A key benefit of this approach being that it just keeps only one working copy of the row instead of the whole table, and calculates the answer in parts as it goes. This is useful because, with the input being all numbers, I wanted to do a dc solution. It does have negative numbers in the input though, so I needed to convert the unary - to _.

tr '-' '_' <input | dc -e'0?[zsn[z:az1<L]dsLxln[dd;ad5R+_4Rr[1-d;ad4Rr-3Rd_3R:ad0<J]dsJx*+1-d1<I]dsIx*?z1<M]dsMxp'

tr '-' '_' <input | dc -e'0?[zsn[zlnr-:az1<L]dsLxln2-[dd;ad5R+_4Rr[1-d;ad4Rr-3Rd_3R:ad0<J]dsJx*+1-d1<I]dsIx*?z1<M]dsMxp'

Like all the other dc this year, it's embracing ?. Which is very handy here for separating the lines... because 0 and -1 are in the input, and numbers go up to 8 digits in magnitude (making choice of a delimiter to insert inconvenient... ? avoids that).

And so we have what's really quite a nice and simple problem with finite differences and sequences. There really was no need to get into Newton polynomial interpolation and discrete Taylor series, but you could if you really wanted the full answer.

Today we get lost in an sandstorm and need to use "maps". There's also the possibility our maps were made for ghosts. And so we get a graph transversal type problem.

The input is in two sections. A line at the top of R and L directions (in order, and repeat as long as needed), followed by a list of nodes. The connections of the nodes are a pair, left and right. My input has just under 800 nodes, and the length of the directions is 293 (a prime number).

This puzzle was my quickest "start to part 2" solution of the year. I really didn't do anything fancy. In fact, for part 2, I didn't even code it until later the next day. I know this because I still don't have a Smalltalk solution in the directory (but did do a quick dc for part 1)... which was curious enough, that I looked up in the Megathread to see if I commented on why. And the answer was, it was nice a day so I took the opportunity to get out and do stuff.

As for what I did, I loaded the graph as a hash of hashes:

foreach ($section[1]->@*) {
    my ($label, $left, $right) = m#(\w+)#g;
    $graph{$label} = {L => $left, R => $right};
}

The second layer keys on L and R so I can just use the input string directions directly to move:

while ($loc ne 'ZZZ') {
    $loc = $graph{$loc}{ $dirs[$steps % scalar(@dirs)] };
    $steps++;
}

For part 2, I modified the script to verify that things were nicely looping for the ghosts. Testing for each of the 6 starts, I "discovered the horrible secrets of desert ghosts". Namely that the cycle lengths are all numbers with two prime factors: a two digit one and 293 (the length of the direction string). So I just fed the 7 primes to dc to multiply them (to get the lcm) and pasted the result. Later I wrote a script to do that work automatically.

The dc solution for part 1 was a quick job. I think part of the reason I decided to do this one was because of 2021 day 12, where I did a graph transversal problem to maintain a streak of dc solutions. This is a simpler graph to do and an easier walk:

    perl -pe's/[^A-Z\n]//g;s/(.)/ord($1)." "/eg' <input | dc -e'?zdsn[1-d3Rr:dz1<L]dsLx[0r[r256*3R+r1-d0<I]dsIx+]sN??[6lNx_4R3lNx:h?z1<L]dsLx[r]sr16i414141[rdln%;d3R;h10 6^~3R4C=rs.r1+rd5A5A5A!=M]dsMxrp'

So this was apparently a day off for me. Checking weather history, the temperature got to 10C early and stayed there until after midnight. Given some of the early problems, I was probably thinking that this was a good day to get a lot of stuff done before the actual harder days arrived.

After a 5-minute airship ride (which is 2 minutes longer than The Airship Blackjack track from FFVI), we get dropped off on the edge of Desert Island. Where an Elf on a camel asks us if we've brought the parts to fix the machines to move the rocks and filter the sand. And so we're tasked with finding out why those have stopped, and since the journey will take a few days, we get another game. This time it's a poker variant.

First thing I did when seeing that was check the ordering of hands for any straights/run-based hands. And there are none to worry about. The ordering is entirely based on sets, and bigger is better. Ties broken by rank of the cards... but in the order listed.

The input is a list of 1000 hands, with a bid amount. Hands will win an amount equal to this bid times their ranking in the list. We just need to work out the rankings. And for part 2, Jacks become Jokers and wild. And of particular note... JJJJJ is a hand in the input (but not in the test). It is, in fact, the only hand with five of one card naturally in my input (and so the highest ranked hand for part 1). But part 2 has 27 five-of-kinds and it's the lowest ranked of those because it has no naturals.

And what I did was treat the hands as hexadecimal numbers with:

$hand =~ y#AKQJT#EDCBA#;

Then I built a signature to sort on for hand ranking by counting the size of the sets and sorting them. So a full house would be 3200000000000. So I just sort primarily on that, and then on the hexified hand value:

@hands = sort {$a->[1] <=> $b->[1] or hex($a->[0]) <=> hex($b->[0])} @hands;

For part 2, it was a very quick turnaround. I made Js into 0s (to lower them below 2s):

$hand =~ y#AKQJT#EDC0A#;

And then sorted the counts without the Js, adding them to the biggest group:

my @str = sort {$cards{$b} <=> $cards{$a}} (2 .. 9, 'A' .. 'E');
$cards{$str[0]} += $cards{0};

One thing to note about this is that with Perl, I had the twelve 0s so there was something to add the J count to for the JJJJJ case. My Smalltalk solution did things differently, and I needed to add a 0 so that case had something to add to. So that line does catch some solutions.

But part of the reason I considered hexadecimal, was because of dc... because it can handle uppercase hex digits. So if the input was in hex, I'd be fine. The catch is... it involves a sort. And so I finally decided to write one, and I went with an exchange sort shuttling between the main stack and a register stack. Because for a stack based language, that is the obvious and simple thing to do:

[rq] sQ
Ll Ll                       # next (ASSUME: at least 2 hands to sort)
[
    [
        d3R d3R             # next top -> next top top next
        !>Q                 # if top >= next, rotate next on top and quit J loop

        Sl                  # push top back on input stack
        z 1<J               # quit if out next left on stack
    ] dsJx                  # next rest

    Ll d 0<S
] dsSx

Next problem is the dealing with the grouping signature. With Perl and Smalltalk it's easy to just sort the counts, but even with the sort function that's not something I wanted to do twice. So I turned things around... I go through all the cards, and add 10^count of each. Thus a full house becomes 16^3 + 16^2 + 11 * 16^0 , and two pair is 2 * 16^2 + 1 * 16^1 + 10 * 16^0 . Basically, a hexadecimal number where the digits are the counts of the counts.

The other main trick is what I sort... and that's the grouping, the hand, and the bid (to keep it attached to the data) stuck together in one big number: groupings * 16^8 + hand * 16^3 + bid.

perl -pe'y#TJQKA#ABCDE#;$_=sprintf("%s \U%x\n",split)' <input | dc -e'16i0Sl?[rd0Sc[10~d;c1+r:cd0<C]dsCxE[d;c10r^3R+r1-d1<I]dsIx*10 5^*+1000*+Sl?z0<L]dsLx[rq]sQLlLl[[d3Rd3R!>QSlz1<J]dsJxLld0<S]dsSx1[d4R1000%*3R+r1+z2<M]dsMxrp'

perl -pe'y#TJQKA#A1CDE#;$_=sprintf("%s \U%x\n",split)' <input | dc -e'16i[rq]sQ[rd1=Qdscrdss]sM0Sl?[rd2Sc0ss[10~d;c1+dls<Mr:cd0<C]dsCxlcd;c1;c+r:cE[d;c10r^3R+r1-d1<I]dsIx*10 5^*+1000*+Sl?z0<L]dsLxLlLl[[d3Rd3R!>QSlz1<J]dsJxLld0<S]dsSx1[d4R1000%*3R+r1+z2<M]dsMxrp'

Part 2 is longer for the handling of Jokers, but if you change the translation from 1 to B, it will do part 1. The use of 1 instead of 0 is because we don't want to lose leading 0s, and 1 is also < 2, which is the only requirement to make Jokers count the least.

This was a fun day.

The ferry brings us to the location of a large pile of sand, that's most notable by its absence. Fortunately, we see a poster for boat races that will get us a trip to Desert Island, where that sand must come from.

The boat races involve a time and a distance to beat. The input only has 4 of them, but the data is in columns to make up some complexity for the fact that there's an unusually low number of cases. Which gets even lower for part 2 when the numbers get concatenated (due to misreading the kerning).

I remember doing the math for the discrete physics, and submitting part 1 and then part 2, only to discover afterwards that my solution actually failed the test case for part 1. I'm not sure if that's because I did a (now lost) brute force script for part 1, or because I just quickly eyeballed the case results and missed the mistake. This is another one where the test covers more than the input.

The physics for this one is pretty basic. You have t seconds, you get to hold and charge for x, and then the boat moves at speed x for t - x seconds. And that needs to be greater than a distance d. So,

|--|------|      dist(x) = x * (t - x) = xt - x^2 > d
0  x      t

So we get critical points at:

x = t ± sqrt( t^2 - 4d ) -------------------- 2

And the answer we want is the number of integers between the two roots. So for my initial solution, I took the floor of the upper, ceiling of the lower, and calculated the size of the range:

my $upper = floor(($t + sqrt( $t*$t - 4*$d )) / 2);
my $lower = ceil (($t - sqrt( $t*$t - 4*$d )) / 2);

return ($upper - $lower + 1);

Observant people will notice the bug (that I've previously mentioned) is there in this. If the discriminant is a perfect square, the roots are on integers and you will include them... but we don't want to tie. And so the third test of (time = 30, distance = 200) will return 11, when it should return 9. To fix that, I added $d++ before this, to bump the requirement to the next possible value. None of the values in my input test this though. So it was a bug I did not notice until after, when by chance, I tried the test case again.

Of course, that was the simple approach, because getting the answer directly from the roots is a bit more complicated. I can't recall if I thought of trying that first, but I did look at it after and work out the adjustment. Basically, for that, if we take the roots to be x0 and x1 (with x1 > x0):

x1 - x0 = (t+sqrt(discrim)) / 2 - (t-sqrt(discrim)) / 2
        = t/2 - t/2 + sqrt(discrim)/2 - -sqrt(discrim)/2
        = sqrt(discrim)

But we need the number of integers in that size of range, but the range center depends on if the time is even or odd:

|   |   |   |   |   |   |     Integers (t is even) (5)
  |   |   |   |   |   |       Integers (t is odd)  (6)
 |----------|----------|
x0         t/2         x1

And additionally, if we truncate the difference to an integer, it depends if that ends up even or odd as to whether we're including or excluding one. And so the factor to adjust ends up being an XNOR.

my $len = int(sqrt( $t*$t - 4*($d+1) ));
return ($len + ($t + $len + 1) % 2);

Coded this way with arithmetic, because this was about getting a tight dc solution:

tr -dc '[0-9\n]' <input | dc -f- -e'1+4*rdd*4R-vd3R+1+2%+p'

To get this to do part 1, took a bit to handle the column reading:

tr -dc '[0-9 \n]' <input | dc -f- -e'[1+4*rdd*3R-vd3R+1+2%+]sCz2/[d3Rr:n1-d0<L]dsLx1+[z1-;n3RrlCx*z1<L]dsLxp'

So it was another "good dog" day. The most memorable thing about these days for me though, was that it emphasized that I really needed to always check the tests to make sure those weren't being broken and it made me expand the framework beyond being bare bones. This is the year where I added sections so that all available tests get tested all the time (without relying on eyeballing and memory)... as well as a special script for "line tests", for making tests that test individual cases. Stuff I had thought about adding before, but now considered important.

Today we get the island with the gardener, who confirms the obvious... that Island Island is the water source. The problem is that it needs sand to filter the water, and the source of that has stopped (welcome to the Grand Material Continuum). There's a ferry leaving soon in that direction, but in the meantime we're asked to help with the food production by working out planting locations.

And so the input is multiple sections. The first is a list of seeds (which will be treated as ranges in part 2), followed by a series of mapping tables. The tables are given in the order. The mappings in them are not. Mappings are given by three numbers, the start of the destination, the start of the source, and the length of the range to map. Not all source ranges are listed, and those that aren't are assumed to be identity mappings. In my input, all the tables have a range that goes to 2^32 , except soil-to-fertilizer. The mappings in the test don't go out that far... the maximum there appears to be 100 (which only 2 have explicit mappings for).

And that difference was really the whole of today's problem for me. This is the part 2 that took the second longest amount of time for me in this year, and it was almost entirely in debugging the test case (and working it out by hand... probably with a bunch of time procrastinating and grumbling). Because the missing ranges at the tails... they matter in the test, but the one in the input doesn't matter at all. Same with the internal implicit identity mappings... if I remove all handling of these from my solution, the test blows up and returns nothing... but the input just smoothly gives the right answer. And so the test case for this one is a much better test of the solution than the input (that's happened before, but this time was an extreme case of it). In fact, with my Smalltalk solution... the test even caught an off-by-one in it that my actual input fails to. The fact that I discovered that, after hours of getting the things perfectly correct, that I could gut my code into something completely wrong and still pass the input left a bit of a bad taste. I can't help feeling that either the input should have been better, or the problem and test adjusted to match that simplicity.

Maybe I should have just brute forced it... sure it's 2 billion points and going to take a while, but I could have gone to bed early.

But I didn't, and ultimately even the correct solution isn't that complicated... I just had some bugs and it wasn't stuff I really cared for to begin with. Part 1 was quickly done because you need to process single points... which can only ever involve one of the ranges, and then you're on to the next table. And so for Smalltalk I could just this to the bottom to catch the identity maps:

typeMap addLast: (Mapping new: '0 0 4294967296').

Mapping just being an subclass of Interval that adds a destination field.

For part 2 though, ranges can cross many ranges, and you don't want them to stumble on an additional different mapping. And so I just processed the mapping tables to fill in the blanks and complete them. Finding gaps in 32-bit tables is not a new thing in AoC. After which I can take intersections of the ranges against those to get the subranges to map for the next step. Process all the ranges through all the tables and then find the minimum.

This is not one of my favourite AoC problems. It's not actually bad though... it's just feels like it could have been made better. Some input might actually have tested and required working code, unlike mine. Sure, getting the answer is all that's technically required, but I do like when that "proof of work" is more of a proof that things work.

The gondola arrives at Island Island... and island with islands, so there's plenty of water, but apparently no immediate water source. An Elf at the station directs us to ask the gardener about it, who's on another island. They'll let us borrow a boat to get there, if we help them figure out their winnings on a big stack of scratchcards.

And so the input is a big list of cards (mine has 220). The number of each card (1-220) is part of the input, but again, they're sorted and so you can ignore that if you want. The card is divided into two sections with a |... the winning numbers and the numbers to compare against them. These numbers are from 1-99 (the absence of 0 is useful again). The number of numbers in each section are regular... 10 winning, 25 have. That can be used, but the test case has different sizes (5 and 8), so I just ignored that. These are proper cards... there isn't a card with two of the same winning number or two of the same "having" number. All the better for throwing things into two hashes/sets/bit arrays.

Part 1 is just a simple counting of winning numbers, but you score them with the power of 2 of that. So you can bitshift, but 1 << 0 is 1, but 2^(-1) is 0.5, which truncates to 0 as an integer (and so you can avoid a special case). This was especially useful for my dc solution for this:

sed -e's/|/0/;s/[^0-9 ]//g' <input | dc -e'0?[0Sh[1r:hd0<L]dsLx[r;h+z3<L]dsLxrs.1-2r^+?z1<M]dsMxp'

The input is mostly numbers, and I convert the | to the unused 0, which can then be used as the accumulator for counting wins. This is using ? to separate the lines by reading them one at a time, and so is a v1.4.1 solution.

Part 2, complicates things by having cards win copies of the next n cards. And just from the description, there's an immediate feel that this is describing a dynamic programming tabulation (there's an order to the cards, where previous ones are used to calculate the later). Of course, you can also do the same work with a recursive memoized function. And I did solutions both ways. My Smalltalk tabulation (you can also use a Bag for this):

cards := Array new: cardWins size withAll: 1.
cards keysAndValuesDo: [ :card :num |
    (card + 1 to: card + (cardWins at: card)) do: [:i | cards at: i inc: num].
].

So there is a bit of advance concepts for day 4 behind this one. But the problem is linear and small. You can easily brute for the number of wins on card with loops... and removing the memoization in part 2 still results in a things only taking a couple seconds. And I think that helped this one be considered a "good dog" compared to it's neighbours.

The Elf leads us to a gondola to get us up to the next sky island. But naturally, it's not working and we need to fix it. First by identifying the parts, and the by working out the gear "ratios".

That last bit was the other way I mentioned to my friend that you might try to mess with an AI... in the context of a fictional world like AoC, you can do things like define something as its opposite... try to quietly drop that "division" means multiplication and then just keep saying "division" right up to the final question. And "ratio" does that here. With the context, a human is going to be suspicious of dividing in an AoC problem and wandering into floating points... those create a lot of issues (even when when they're never an answer, the existence of float point native languages still influences integer solutions). The idea being that an AI might need additional prompting to not do the normal real world things.

As for the input. It's a 2D grid with some complexity in that it has some multidigit numbers on it (ie not one-cell objects). It does play nice in a number of ways... mine has no special characters on the rim, no number adjacent to other numbers, and no gears with more than two numbers (or numbers with more than one gear). Not having these makes things simpler, and also removes a bunch of potential bugs that beginners might stumble on. Some languages have wrap-around array indexing and those have caught unsuspecting people before. There is a test file in my directory that I think someone else made that tests things like that. I pretty sure it's not mine, because I wouldn't have bothered creating a test for wrap-around... my grid reading template adds sentinels to the edges and I would not remove them for this problem. It also tests things like a gear with two of the same number... seeing it, I can reverse engineer solutions that could have a bug with that, but that's not something my solutions would make me think of testing. It also has -21 on the grid... I suppose that would catch someone as a negative number.

The problem doesn't actually define what a "special character" is (only what it's not). In my input those are: # $ % & * + - / = @. Of particular interest is / which is ASCII 47, and between . (ASCII 46) and 0 (ASCII 48). And so we have special characters before, after, and in-between the non-special ones. And so I used "digit or ." for non-special, which has the De Morgan's Law negation of "not digit and not ." for special characters.

As for solving this, you could look for the special characters, which take a single-cell and thus have a fixed pattern of neighbours to look for digits in. But then you need to do a bit of code to search for the full number.

That last bit, made me decide from the start to go the other way... search for the numbers, calculate the neighbour box and search that for special characters (non-digit and non-period). Because the part numbers are all horizontal, I can use regex in Perl to easily dig out all the ones on a line:

while ($grid[$line] =~ m#(\d+)#g) {
    my $num = $1;
    my $x = pos($grid[$line]) - length($num) - 1;   # left edge of search block

    # Search surrounding block for parts and gears
    my $found = 0;
    foreach my $y ($line - 1 .. $line + 1) {
        my $str = substr( $grid[$y], $x, length($num) + 2 );

        $found = 1  if ($str =~ m#[^.0-9]#);
        push( $gears{$y, $x + pos($str)}->@*, $num )  while ($str =~ m#\*#g);
    }

    $part1 += $num if ($found);
}

This is all keeping things very simple... as we scan the number as well as part of our neighbours. The "trick" for part 2 being that, since we're doing things "backwards" for this (ie we're not the simple "find gear, count numbers" but finding the numbers first), we add the part number to a list that's in hash table keyed with the gear location. Then at the end, we scan for gears with exactly two part numbers:

my $part2 = sum map { product @$_ } grep { @$_ == 2 } values %gears;

One thing I like to do with Smalltalk solutions is to avoid regex. Which here provided a little extra to do, as I extended SequencableCollection with:

findRanges: aBlock [
    | res start |
    res   := OrderedCollection new.
    start := nil.
    self keysAndValuesDo: [:i :item |
        (aBlock value: item) ifTrue: [
            start ifNil: [ start := i ]
        ] ifFalse: [
            start ifNotNil: [ res add: (start to: i - 1). start := nil ].
        ]
    ].
    start ifNotNil: [ res add: (start to: self size) ].
    ^res
]

This is a nice general purpose method that takes a predicate aBlock and executes that as part of a state machine that collects the ranges in the collection where it's true. It's such a nice extension that I added this to my Smalltalk AoC toolkit.

So this was a bit rougher than usual for a day 3... I seem to recall the "good dog/scary dog memes" evolved into a meme of "scary" on odd days, something which day 5 will also support.

Today we land on the first (and ultimately last) sky island, Snow Island. And Elf comes over to show us around, and since it's a walk we introduced to another Elf game. Not involving a ring this time, but drawing from a bag of colour cubes. Our goal is to work out information about the contents of the bag from a series of draws.

The input is 100 lines, each representing a game and they're numbered and in order (as it typical). Meaning you can ignore the game number on the line if you want. After that, there's three to six semicolon sublists representing draws of numbers of red, green, and blue cubes.

However, it's not even important to parse out the sublists. For the information we're asked for, we can treat a single draw of "3 blue, 4 red" as two separate draws of "3 blue; 4 red" (and so commas and semicolons can be ignored). All that matters for each line is all the "number colour" pairs you see. This is because part 1 fails when any red, green, or blue is too large (this is one of the rare puzzles where specific the numbers for that are put in the description not the input file). Part 2 just wants the fewest number of cubes of each colour that can be in the bag (so no question there that colours are independent).

And that last bit ("fewest number") is particularly interesting to me, because a little while before this AoC started I was talking with a friend about how one might try to mess with LLM context to try and potentially mislead it for something like AoC to try and make sure humans stay involved. AIs normally assume that the user is trying to be help it produce the right thing... and one thing you could do is have a problem where "few" and "minimum" are used many times, but maximum is the function you need (and "maximum" and "most" are never in the description). I can't say that this was done for that here (I seriously doubt it)... this is probably the standard AoC description being a bit obtuse so the humans have to think and discover (even if they do hand the coding off to an AI after explaining that). I did mention the coincidence at the time... but only after day 3, which did the other little related thing I had mentioned in that conversation. Since that conversation wasn't online at all... there's no way it influenced AoC. But it was a remarkable one that I remember about the start of this year.

But for what I did, I just grab the maximum red, green, and blue counts on a line. And then it's just:

$part1 += $game  if (all {$want{$_} >= $max{$_}} keys %want);
$part2 += product values %max;

Doing this in Smalltalk was a bit interesting, because although the description involves a "bag" and a Smalltalk Bag is like a multiset, it's not really a multiset in functionality, as it lacks the operations that Set has. Bag is very barebones, and is often a let down. And here is wasn't even the best base class to subclass a MultiSet class from... I did from Dictionary. All so I could have a different type of solution... one that used set unions and difference to test things. It's not practical, and it's 33% slower than just using maximums. But it was something different to do.

For 2023, we're back to fixing snow production, but on a global scale so the weather machine from 2015 won't do. And so we need to travel to the sky islands. The map this time is a stack of sky islands, which we will work our way up from the bottom and then come back down. Making this another year where the numbers are out of order. And it all starts with us being launched to the sky by trebuchet. Which naturally needs us to do calibration for.

The input for this one is not just numbers this time... it includes lowercase letters which sometimes spell out the digits one through nine. Zero is not involved in any way, which is convenient for some solutions. I will note that vowels do not occur outside of the digit words (where they're required)... and quick test reveals that Chrome does not detect this as any language. So there is some protection against the autotranslate + copy-and-paste issue. Which is an untended gotcha that really don't want people to run into on the first day.

In general, 2023 stepped up difficulty and complexity a bit... and that's particularly noticeable on the early days. Which makes me wonder how much of that was the influence of AI... a little complexity and gotchas to mess a bit with the LLMs so that just maybe, they fail the first try and give the competition programmers a chance (because, they're really fast, especially when allowed to bring their toolkit).

The problem this time is simple... we want the two digit number made of the first and last digit on each line. For part 2, that includes interpreting the words as well. And the gotcha for part 1 is tested for in the word "treb7uchet"... it's a small wrinkle I special cased when the test failed and I saw it:

say "Part 1: ", sum map {(m/^\D*(\d)\D*$/) ? "$1$1" : (m/^\D*(\d).*(\d)\D*$/ and "$1$2")} <>;

For part 2, the gotcha is "twone", "eightwo" and "oneight". Which are present the given test input, but they aren't actually tested. I didn't really notice this issue until after, because I just took my regex to:

m#(one|two|three|four|five|six|seven|eight|nine|\d)#;
$part2 += 10 * $table{$1};

m#.*(one|two|three|four|five|six|seven|eight|nine|\d)#;
$part2 += $table{$1};

With table being a hash of of the words and the digits to their value:

my %table = ('one' => 1, 'two' => 2, 'three' => 3, 'four' => 4, 'five' => 5,
             'six' => 6, 'seven' => 7, 'eight' => 8, 'nine' => 9,
             map {$_ => $_} (1 .. 9));

This avoids special casing, and this is because I was thinking of how I was going to do dc for part 2.

perl -pe's#(.)#ord($1)." "#eg' <input | dc -e'[+d]sF[s.z3<Lq]sN0?[0d[3R48-d9<Nrd0=F3Rs.z3<L]dsLxrA*++?z1<M]dsMxp'

perl -pe's#(.)#ord($1)." "#eg' <input | dc -e'1dd:t18996:t2dd:t32285:t3dd:t24203441:t4dd:t1299471:t5dd:t694023:t6dd:t43444:t7dd:t39325060:t8dd:t49523414:t9dd:t683663:t[dsf]sF[lf0=Fdsl]sN[39-]sS0?[0ddslsf[r48-d9<Sr36*+36 5^%5[d3Rd3R36r^%;td0!=Ns.r1-d0<I]dsIxs.z2<L]dsLxs.llA*lf++?z1<M]dsMxp'

dc doesn't have any string processing, and so these are taking the input as lines of ASCII values. And so it does use ? to process the input (this would be the point where I fully adopted that and trusted it... although it's back to non-functional, so these are dc v1.4.1 solutions).

Half of that part 2 is building the table:

1d d:t 18996:t              # 14 23 24          eno
2d d:t 32285:t              # 24 32 29          owt
3d d:t 24203441:t           # 14 14 27 17 29    eerht
4d d:t 1299471:t            # 27 30 24 15       ruof
5d d:t 694023:t             # 14 31 18 15       evif
6d d:t 43444:t              # 33 18 28          xis
7d d:t 39325060:t           # 23 14 31 14 28    neves
8d d:t 49523414:t           # 29 17 16 18 14    thgie
9d d:t 683663:t             # 14 23 18 23       enin

This maps both the digits and the strings (as essentially base-36 numbers) to the value. The ASCII values are converted to values on the range of 1-35 (0 not being a value in the problem is good here). Note that the strings are backwards because the lines are loaded on a stack and so we parse the lines backwards.

The trick to matching strings here is keeping a window of a five digit base-36 number (36*+36 5^ shifts, adds in the new, and the chops off the oldest with a mod of 5^36 ). Then there's a loop that takes progressively shorter mods of the window to compare them against the table until it gets a match. When a match is found, the N macro is called, which always sets l to the value, but only sets f once. Yes, first and last do end up backwards, so we add 10 * l + f.

I also did a Smalltalk version, and chose to run with someone's comment about doing string substitutions on the words... I saw "o1e" as a substitute for "one" and immediately knew what was up, and ran to do it. The overlapping means you can't just replace all the words willy-nilly, but if you replace them in a way such that the later substitutions still can match, you're fine. And "o1e" is doing that... it's leaving the "o" at the front for a "twone" and the "e" at the back for an "oneight". Had 7 been spelt "sevon", then you'd need "on1e". Or, alternately, you could change the order of the substitutions so that the "sevon" is done first and "one" doesn't have to worry about it. In any case, it was easy to hand solve for a table of substitutions to start, but then I followed up with code that generates that table (and so is flexible for other languages). It was a fun little exercise that got some extra mileage from the problem.

And so we get a heavier start than we've seen before... numbers and strings together. This helps get us ready for the fact that more of the early problems are going to be heavier than in the past. I seem to recall a bunch of "good dog/scary dog" memes being posted about the shift back and forth between days.

Extraction is going to be hot air balloon, and to get them to fly requires heating the fuel with "Bob" the anthropomorphized (with a pair of googly eyes) fuel heating machine. And in order to do that, we need to sum the requirements, which are in balanced quinary (aka SNAFU numbers). More on balanced numbers (albeit ternary) can be found here:

https://en.wikipedia.org/wiki/Balanced_ternary

And so the input is a list of balanced quinary numbers, one per line, with - and = for the negative digits. All the numbers in the input start with a 1 or 2, which means they're all positive, and so add to a positive value. This makes the problem easier.

My initial solution in Perl didn't use any outside requirements. I did the base conversions myself, and so I did it directly from and to balanced quinary (with the summing done with the regular +). Of course, with everything being positive, and bringing in base conversion from the ntheory module, it can be done with shifting of the values by half the power (and back):

my $sum = 0;
while (<>) {
    chomp;
    tr/=\0550-2/0-4/;
    $sum += fromdigits( $_, 5 ) - floor( 5 ** (length $_) / 2 );
}

my $part1 = todigitstring( $sum + floor( (5 ** ceil(log($sum) / log(5))) / 2), 5 );
$part1 =~ tr/0-4/=\0550-2/;

print "Part 1: $part1\n";

This only works because everything is +'ve, though.

However, my initial Smalltalk solution does do negatives... it can handle cases like:

-1
=0

Which is -21. You can also test that with 10-1 + 10=0 - 2000 with a solution that only handles positives.

And the way it does that, is by subclassing Array for SnafuNumbers. So they're treated as arrays of digits, and I do the addition digit by digit handling the carries:

+ other [
    | res val |
    res := SnafuNumber new: maxDigits + 1 withAll: 0.  " +1 to catch overflow "
    (1 to: maxDigits) do: [ :i |
        val := (self at: i) + (other at: i) + (res at: i).

        " do appropriate carry, if needed "
        (val abs > 2) ifTrue: [
            res at: i+1 put: val sign.
            val := val - (5 * val sign).
        ].

        res at: i put: val.
    ].
    ^res
]

maxDigits is set to 32, and 5^32 is a 75-bit number, so that should be more than enough.

I also did a dc version, and in converting the input I went with an unusual order of 012=-, because it makes for a cleaner tr command than tr '=\055012 '0-4'`.

tr '012=-' '0-4' <input | dc -f- -e'1d:t2d:t[=]3:t[-]4:t0[r0r1r[A~2+5%2-3Rd5*_4R*4R+_3Rd0<L]dsLx*++z1<M]dsMx[5~d_3R1-2/+d0<C]dsCx+[;tnz0<P]dsPx'

And so we come to the end of another solid year (and I see that this time I remembered to submit part 2 before reading the story). This is the year where people using AI started to make some noise, but it was not a big thing yet.