Today we discover a strange pattern (a heart?) on Pluto, which is apparently a relic of the long-lost Pluto civilization, that could fold spacetime. The most notable thing is that this isn't news to us... Plutonians are apparently famous for this.

And so we get another maze search. This one isn't as big as the previous, because there's a huge hole in the middle. Which makes parsing one of the larger parts of this problem. The core basics are ultimately going to be the same as day 18, make the maze into a graph and search that. With the addition of the recursion in part 2 adding a third dimension (depth).

So for parsing, I find the dimensions of the hole while reading in. Then I do:

foreach my $x (3 .. $MX - 3) {
    $Port{ $Grid[0][$x].$Grid[1][$x] }{out}       = [    2,$x]  if ($Grid[0][$x] =~ m#[A-Z]#);
    $Port{ $Grid[$MY-1][$x].$Grid[$MY][$x] }{out} = [$MY-2,$x]  if ($Grid[$MY][$x] =~ m#[A-Z]#);

    $Port{ $Grid[$In_top+1][$x].$Grid[$In_top+2][$x] }{in} = [$In_top,$x] if ($Grid[$In_top+1][$x] =~ m#[A-Z]#);
    $Port{ $Grid[$In_bot-2][$x].$Grid[$In_bot-1][$x] }{in} = [$In_bot,$x] if ($Grid[$In_bot-1][$x] =~ m#[A-Z]#);
}

A scan along the four key lines for a label, get the other half to make the name, assign that to the location. Then another scan for y. It's not pretty, but the input is a bit tricky and this is functional and gets us something easier to work with.

With all the portals found, I can then make a jump table between the ins and outs. As well as mark the Grid locations with a *, so that the searching on the grid has a mark to easily tell it that there's a portal there.

For part 1, it's all searching on the grid, as there's no point in building the graph yet... you just want one path: AA to ZZ. The *s mark where jumping is available to queue up as a move. And I just use BFS. There's nothing weighted, and there's no easy way to judge how close you are when you're jumping around. And it's fast... the maze isn't that big and has a huge hole.

For part 2, I do the standard and build the graph with BFS and toss the grid away. Jumping adds ±1 to depth and there's a special case, in that ZZ is only on the outermost level. Now that it's a weighted graph, we move on from BFS. And I went A*... the heuristic being to add depth * width (of the doughnought). Because that's the minimum distance possible (cross from in to out, depth times). It helps keep us from getting too deep. And it does make things more than twice as fast. It's not so exciting for the Perl solution that runs under a second without it already. But for Smalltalk, it makes 11s into 4s.

I believe this might be the problem where I wrote my own Heap class for Smalltalk... because SortedCollection was was behaving awful. It was only last year that I actually bothered to look at the kernel implementation of that, and see that it is a heap, but instead of the top being at the front (like you'd expect from priority queue and the standard array implementation of heap), you need to use removeLast to get the proper behaviour. Which is just weird.

There is an interesting side to the examples, in that we're given an example in part 1 that goes infinite for part 2. So I added a limit to the depth to catch that for when the test harness tries it. The search space for mine goes to 77 layers (although the solution only goes to 36)... so I chose 200. For Smalltalk I added an exception not to test that file with the part 2 solutions... unlike the input which ticks through the layers really fast, that case explodes and starts grinding. I don't know how long it would take to even reach 78.

And so, another fun little search problem to play with, with its own little quirks.

I am doing intern from last 4-5 months in a company and they are open to give me full time. I am currently in last semester of B.Tech but I got 1 backlog which I will clear in Dec 2026. Hr or any person never asked me about backlog and CGPA score during hiring. Only one time during intern a senior developer asked and share my score but I didn't tell about backlog. So when I get full time what documents they will check ??? Will they find my backlog??? Or if they did what I can say ??

What are solutions do I have???

Should I give some edited documents? Is there any option to crosscheck???

Having "borrowed" the tractor beam to help snag Santa's ship, we need to test it. Using drones to detect where the beam is, controlled via Intcode.

Today's change-up for using Intcode is that the program just wants one coordinate (two values), and will return a value and halt. So unlike previous days where I was thinking of the Intcode machine as a big thing that I write small functions to plug into... today's it's a small thing I encapsulate in a function that tests a location. Then I can write algorithms to do the parts and just call that function when needed.

For part 1, it's just a standard check that you're working... how many squares in a 50x50 grid are in the beam. If you don't want to trust that it is a cone like shown in the example, you can easily scan all 2500. But if you assume it is a cone, then you can skip most of those points. On any given row, track when you entered the beam and stop when you exit it. For the next row, you then can skip to where you first entered the beam on the previous. For my input, you could start at +1 column from that, but some beams might be a little more slanted, so I figure I might as well be safe. Very little outside my beam is checked.

For part 2, I used the y range at x=50 to interpolate out to find where the beam is at least 100 high. The sample isn't great (and comes up quite a bit short) so I update my gradient as I go. The goal is to find the beam's lower edge at an x, treat that as the lower-left corner of the square and then test the upper right (x+99,y-99). That's all that's needed to know the square is filled (its the diagonal that goes across the cone... the other goes along it). Originally I just did a gradient/binary search thingy.

But later, I did do the sliding window. It does take either supplying a good start on faith, or taking a bad interpolation from part 1 and having to slide quite a bit... or doing at least one more bit of sampling out at range to get a better start. But it is elegant:

while (!&get_tractor( $x + 99, $y )) {
    $y++;
    while (!&get_tractor( $x, $y + 99 )) {
        $x++;
    }
}

Reverse engineering this one was entertaining. Are the edges of the beam actual lines? Yes. But, they're defined by quadratics (it truly is a conic):

a*x*y >= abs( b*x^2 - c*y^2 )   (a,b,c are constants in the code)

I just used that straight. But I did also throw it at WolframAlpha to see what it thought. It looks better (and graphs things), if you use actual values for a,b,c. Here's some that are similar to my input's:

https://www.wolframalpha.com/input?i=20++x++y+%3E%3D+abs%28+90++x%5E2+-+140++y%5E2+%29

If you look down you see that it resolved things to lines (well, one term resolved in terms of sqrt(x^(2) ), and the other is x... it is two lines through the origin). Put the a,b,c in and you'll see that the radical part is a^2 + 4bc (once the x^(2) /c^(2) is factored and rooted out).

For constants I grab them when they're set in the stack frame before calling the function at 303:

my $b = &get_value( 80 );
my $c = &get_value( 122 );
my $a = &get_value( 160 );

That function I was happy to just have figured out by looking at the results. And the fact that we have sample code for this, I now know that I figured out what it was... it's the one called mul_three(a,b,c). It multiplies three numbers together. How do you do that? When, first you sort them with bubble sort and recursion. Then (column on the right is to show things in terms of the original a, b, and c so you can see how this works):

a = b - a           b - a
c = bc              bc
a = ac              (b-a)bc = b^2 c - abc
b = bc              b^2 c
c = -a              abc - b^2 c
return b+c          b^2 c + abc - b^2 c = abc

Perfectly cromulent multiplying of three values.

Today we arrive at Neptune only to be tractor-beamed to Triton. Forced to land, we discover a massive underground vault. Of the ubiquitous twisty passages, but this time with keys and doors. Not knowing what key is needed for the tractor beam, we've decided to just collect all of them.

It is another standard cell-based maze, except for the center. The keys are all in the cells, and the doors are in-between the cells. For part 2, we need to alter the maze, filling in the center and turning it into 4 mazes. With a robot for each.

My code for this day really needs some cleaning up. My approach was pretty standard. First, I build a table of the distances between keys (including the start) with BFS. When you find a key, you can record both ways, and so you only need to continue a BFS from a key until it's found all keys after it. So you can stop early, and it takes practically no time. The search from the starting location is special, because it tracks doors and access as well. As the search goes on, it keeps a list of what doors it's gone through, so when a key is found, it knows what keys are needed to get to there. For tracking keys, I used bits. That way a set of keys is just a regular int, and it's quick to check if I have all the right keys for something (mask & ~keys is the keys still required). It also makes for quick and easy hashing of the current state for tracking what's visited (just stick that number after the keys the robots are at).

Once I have the distances, it becomes a graph search as I can jump from key to key. There's never a reason to stop anywhere else (including going back to the start). Each move collects a key, which may change accessibility. Although, I don't bother tracking accessibility, I have a memoized function that returns that for a set of keys... for my input it ends up with about 19k records, that get memo hits over 100k times. With the weighted graph, the search is Dijkstra for part 1.

For part 2, I improved things to reasonable levels by going A*. The heuristic is just the sum of the minimum distances possible to the remain keys (which will not over-estimate, and so will give us the correct answer on first arrival). This is easy to track and pass along (with minimum calculation)... you get the minimum distances for each key while building the the distance table, and you sum them. When you queue a move, you subtract the minimum of the key you went to.

This was the biggest improvement to part 2 (without it, it took over a minute and the queue just gets massive, with the heuristic it's less than 6s). And looking at the copious output I did on these scripts, it's easy to see why. There are some bad keys. The worst key to get is r... at least 218 moves. And that's from the start, and it is accessible immediately... and the key is the most popular requirement (tied with m which is required for all the same doors). And the A* heuristic will focus things along that way (any position with the r-key is going to have a strong priority over any position with a similar number of steps that doesn't).

And so we get a nice juicy heavy search. It's always nice for AoC to have at least one in a year. They do involve a lot of the same core (which provides some accessibility... once you've done a couple, they become familiar even if your solution is slow). But what makes them fun, is the nice little twists of the specific problem (keys and doors here... which makes the solution one of the valid topological sorts that the maze describes) and the fact that you can play around and tweak things to see what works better.

Now back in deep space proper, we get warning of an impending solar flare. Probably not too much of a threat, because we are 20+ AU out and the intensity will drop with inverse-square law. But there's small robots with sensitive electronics we need to warn and the Wi-Fi's blocked so we only have some cameras and a vacuum robot to use.

Today we get to add the ASCII interface to the Intcode machine. Sending a string is as simple as queueing up the ASCII values of the characters to send one at a time when asked. And output comes in the form of ASCII values, or large non-ASCII values. The cut-off between the two isn't explicitly specified... but there is a link to the Wikipedia page on ASCII with a table to show that it's 7-bit. Although assuming 8-bit or even 16-bit would work, because these values are answer and are substantially bigger.

Part 1 is going to output a grid and halt and we're given a simple test to verify that we've implemented ASCII correctly and can parse the output. It's finding intersections like on day 3, but on a tiny grid in a format where we don't get given the lines. It's easy to get an answer just by scanning and checking neighbours. But you will need to parse things as lines for part 2.

Where we modify the first address and it goes into an interactive mode. Which I can do with intcode -m0:2 -r input now (the -r uses readline library... originally I didn't have that in). This gives us access to a very different sort of AoC problem, in that we're given a little macro language to code in. And I initially did this one by hand. Because I like doing puzzles, and coming up with the macros by myself is something I wanted to do, before coding something to automatically solve.

An interesting thing here is that part 1's detecting of intersections puts the idea in your head that maybe this is a trapdoor dropping puzzle where we need to find a certain path as well. And in the problem text for part 2, it gives that 10,L,8,R,6 is a valid macro, suggesting that we might need to break up a "turn-distance" pair (making things less like day 3 were it's all direction-distance pairs). Both of which are kind of red herrings (although there may be solutions with them). And while solving by hand, I did have them in the back of my mind, but since I'm not a computer, I went with making simplifying assumptions (until they fail).

Those would be:

• that since there is a path from beginning to end without turning at an intersection (with only forced turns), we should focus on that and not the intersections
• that the command pairs weren't going to be broken, the robot has to turn right at the start, and it's simply best if all macros start and end on the same state (start with a turn, end with a move)

So first step was making the list of the single path I'd chosen. And that had distances only of 4, 6, and 10. A sign that this is way to go, as turning at intersections and making more different numbers is probably not good. And I still have the file I used to calculate from that list... It's got one move per line, and I'd start by picking a macro for A at the top, and adding blank lines to section off the parts where that occurs in the list. Then try for a B that only left a C. And at 4 lines for A, there was a 3 line B between two As at the start, that when sectioned off from the rest, left a single missing pattern C repeating in the holes. It wasn't too hard to find, and it fit the character limit, and so I typed it in and got my answer. Then wrote code to do that search.

I've never reverse engineered this one (it's easy to spot looking at the input that there's code, then ASCII values, then more code, then some data). Just dumping the run of part 1, results in labels getting up to $aqr, because it's clearly calculating and building the grid out past the code in memory (29 * 39 = 1131, which would be aqm in base-26). I also have a little script to do strings on Intcode and here they are (they are all plain text):

[334] Main:
[342] Expected function name but got:
[376] Function A:
[389] Function B:
[402] Function C:
[415] Continuous video feed?
[441] Expected R, L, or distance but got: $
[479] Expected comma or newline but got: +
[516] Definitions may be at most 20 characters!
[558] ^>v<

Of course, given the path string you can also throw regex at it to make it work out how to divide things up. It's actually really quite simple once you've seen it. Capture a group of up to 20, repeat it as much as you want, capture a second group, repeat both as much as you want, capture the third group, repeat all of them as much as you want... match the full the string and you've got the winner.

And so we get another great use for Intcode, in that you really probably weren't expecting to learn and use a new language. And if this isn't enough of a language for you, that will be covered later.

Today we find out that a portion of the ship has gone pink. In FTL, I might just leave it... it helps stops fires and boarders. Saves me from having to open the doors manually for them. But since we're not going to be shot at or boarded, it's probably safer to restore it.

This is a natural step-up from the previous Intcode problem. There it was beneficial to track locations received on output to decide on input. Here the input is like a function call that we receive later on the output side. And so the communication between the two is more involved. You need to track the robot's position while trying moves (which may fail) and explore the area. So maybe this isn't FTL, but Duskers or Suspended.

This is one of the benefits of Intcode, the map is in a black box that can be explored and not simply loaded. And I never took it further than that. There is official sample code, and quick glance in seems that there's a table of doors between the cells, and they're stored in binary using a threshold (looking at a dump, the table indexing is done at 206, and the threshold is tested at 210). Since I've seen the maze, I know it's a standard recursively generated one with no-loops, left-hand rule friendly. So it's a bunch of cells with doors between them... which is why I image the table is half the size you'd expect. That's my first impression at least.

But I've only done this one as a black box, exploring and building the maze. Since we're moving with our exploration, recursion would seem to be the way. Except for the fact that the communication is through a machine... so I skipped on recursion, and just did the equivalent stack algorithm myself. When I send a move push it on the stack. If the output tells me it fails, I mark the wall, otherwise I mark it empty/O2 and move there.

If the input can't find a place to try it's at a dead end, so we need to backup. So, pop the last move off the stack and do the reverse of it. The movement order in the list is interesting in that it's NSWE with a base index of 1. If it was 0, the function to reverse is easy because of the NS and WE pairing... just toggle the last bit (with XOR). Fortunately I was doing Smalltalk solutions and was very used to having to deal with this problem (1-base arrays vs 0-base mod residues). And so reversing is ((move - 1) ^ 1)) + 1.

Part 1 is easy, it's the size of the stack when we get to the O2. There's no open spaces or loops to short-cut. For part 2, I initially felt like doing something silly... so I did it as cellular automata (I just wanted to write one and it hadn't come up). For Smalltalk I did a more standard breadth-first flood fill. Of course, you could get fancy and build a weighted graph of paths between the intersections (there actually aren't many) as you explore, or try to collect the size of the longest path as you "recurse" back to the starting point. But, the fact that the intersections are few and make for a small graph also makes flood fill just rip down them. So I don't know how much benefit you'd get. Exploring the maze with the Intcode machine takes essentially all the time. That's the bottleneck.

And so we're continuing to expand into what Intcode allows for in the problem space. Overall, a nice little problem that I've been happy to just leave as a black box.

2015 day 9, day 13, and 2016 day 24 are all problems involving a variation of finding the longest/shortest path/cycle with 8 nodes that form a complete graph (every node has a distance to every other), also known as the Travelling Salesperson Problem (TSP). This is an NP-complete problem: there is no general-purpose polynomial-time algorithm known to solve it, and if you can come up with one, YOU will be rich for having proven P=NP; alternatively, if you can definitively prove the counter-conjecture P!=NP you will still be famous, even if the result is a letdown.

So the best you can do is either using an exponential-time algorithm, or find specialized algorithms for certain subclasses of the TSP problem (for example, relying on sparseness for pruning, or being satisfied with an approximate answer without proving it is the global answer). The saving grace for all three of these puzzles is that n=8 is small enough for the global answer to be easily tractable with an exponential-time algorithm (contrast that to things like 2019 day 18 where finding the shortest path with n=26 is prohibitively expensive if you were to attempt to do naive exponential searching).

That said, MOST solutions in the megathreads for these days just whip out a permutation engine (either one built into your language, or rolling your own, with Heap's algorithm being a common choice), performing O(n!) work to just check every possible path, or solve by recursion (where your call stack does the same factorial effort as a permutation engine). The naive approach says that once you have a working permutation engine, you then test 8! paths, or 40,320 different variations - still lightning fast for modern computers and programming languages. And if you get your star in less than a second, do you really need to try anything else?

But I wouldn't be writing this post if that were the best you could do. The first major optimization is to realize that if you just visit 7! permutations, you can still check all cycles with 8 elements by connecting your last item with your first, and turn that into a check of the longest path by creating the cycle and then tossing out the shortest edge. This adds complexity to each permutation checked (you are now doing 8 times as much work per permutation to find the shortest edge that will need to be tossed), but reduces the number of permutations visited to 5,040, and the work to find a shortest edge is probably more localized and less overhead than the work being done in your permutation engine to advance to the next permutation, so it is an overall win.

The next observation is that when your graph is undirected (the cost from A to B is the same as the cost from B to A - true for all 3 of these days), you can again cut the work in half if you avoid a permutation that is lexically reversed from an earlier permutation you already visited (path a->b->c->d will have the same weight as path d->c->b->a). Heap's algorithm does NOT make this easy, but there are other permutation engines that DO make it easy to stop iterating after just half the permutations, avoiding all lexical reverses in the resulting output. Among them is Steinhaus-Johnson-Trotter, which I implemented in Rust to get 2015 day 9 down to 2,520 permutations visited. But remember, even that is still doing 8 checks per permutation to cast out the shortest edge when looking for the longest path.

So today, I finished up a patch that goes for an entirely different approach. The Held-Karp algorithm solves TSP in O(n^(2)*2^(n)) - still exponential, but better than the super-exponential O(n!) that other solutions were using. It is based on a dynamic programming technique of using a table of n * 2^(n) distances; each distance g(set,k) represents the set of nodes in a path from the chosen start point, and a node k that is an element of that set and the last node visited along the path so far. When set is a singleton, the distance is obvious: the distance from your start point to that node. For any larger set, there are O(n) elements in the set, and so you need to generate O(n) distances to be stored as n values of g(set,k); computing any one of those distances is also O(n) work to find which out of n-1 g(set\k,m) for another point m!=k in the set added to d(m,k) produces the best path one element longer. The dynamic programming aspect says that if you iterate from 0 to 2^(n)-1, you will visit every possible set size, and all recursively-smaller sets that you depend on will already be populated by the time you need to reference them in building your larger set values. So even though the algorithm is defined by a recursive relationship, it is implemented with straightforward looping.

I was impressed that the result was still fairly legible. Below is my implementation for 2015 day 9. It produces 8*7/2 comparisons (the O(n^(2)) each pairing of bit m with k) /2 (even though there are 8*256 bits across all sets, on average half of them are not set) * 256 sets (the O(2^(n)) number of sets visited), or 3,584 total comparisons. That's more than the 2,520 permutations of the 7!/2 approach, but remember, the permutation approach required an additional 8 comparisons per permutation to find the edge to discard, whereas Held-Karp does not. Plus, permutations requires the overhead of moving to the next permutation (often work hidden behind your library interface), while set iteration is lighter-weight (admittedly, this code uses maneatingape's biterator() function to encode access the next bit index in a bitmask). Timing-wise, my patch sped up the solution from 40µs to 12µs on my laptop.

    // Initialize a table for each part: 2ⁿ sets with n distances per set. Default 0 matches
    // g({k},k) of zero for all singleton sets. Initial value of other sets does not matter.
    let mut table_one = vec![0_u16; stride * (1 << stride)];
    let mut table_two = vec![0_u16; stride * (1 << stride)];

    // Visit each non-empty set in order, with no work to do for singleton sets.
    for set in 3_usize..(1 << stride) {
        if set & !(set - 1) == set {
            continue;
        }

        // For a given set, compute each g(set,k) for all k in the set.
        for k in set.biterator() {
            let subset = set ^ (1 << k);
            let mut shortest = u16::MAX;
            let mut longest = 0;

            // For a given destination k, find which other bit m gives the best path from the
            // subset to m, and then m to k. All table[subset] references were filled in prior
            // iterations of the outer loop or the singleton base cases.
            for m in subset.biterator() {
                shortest = shortest.min(table_one[subset * stride + m] + distances[m * stride + k]);
                longest = longest.max(table_two[subset * stride + m] + distances[m * stride + k]);
            }
            table_one[set * stride + k] = shortest;
            table_two[set * stride + k] = longest;
        }
    }

    // With the sets now built, we have stride candidates for each answer.
    (
        *table_one.iter().skip(((1 << stride) - 1) * stride).min().unwrap(),
        *table_two.iter().skip(((1 << stride) - 1) * stride).max().unwrap(),
    )

2016 day 24 is even better. Days 9 and 13 must visit 255 sets (n=8) to ensure that you find the right path regardless of which point started the path. That is because Held-Karp forces you to pick a starting node; but while an arbitrary starting node will always be part of the longest cycle, it is easy enough to generate a graph where the longest path is not part of the longest cycle if you picked the wrong starting node (the 8! down to 7! optimization for permutations did not have that problem, because there you are casting out the short edge from every possible path, rather than just the one longest cycle). To find the longest path among 8 nodes, you can either run 8 iterations of Held-Karp on sets up to 127, or more efficiently do 1 iteration of Held-Karp on sets up to 255. But day 24 explicitly pins the path to start at node 0, so you only need to visit 127 sets. For that day, being able to use n=7 lets the number of comparisons drops to 1344 (=7*6/2*128/2), which is hands-down better than 7!/2 permutations.

And so we arrive at The Planet That Must Not Be Named. Really. We're "3/4ths of the way through the gas giants", the name is not mentioned once. Poor Uranus, you get a lot of flak for being boring and even AoC's visit to you doesn't involve anything specific about you other than your distance. So we essentially get a deep space problem but without using Intcode.

And so we get a number sequence/transform problem based on waves and FFTs. Part 1 is small and simple enough to do. And I did it in dc even. Looking at that code, it's a bit of mess, but its actually using tricks I used in my math library to keep registers clean (like having "return" macros). Which complicates things for no real benefit here. Registers are being abused all over, because this was at a time when I was avoiding the non-standard R (the large rotate), so stack control was overly limited.

I remember doing this because I had the cute idea of building a little macro state machine to cycle the pattern:

# State machine, lAx to init, lNx to move to next state
[  1 sm [lBx]sN ] sA
[  0 sm [lCx]sN ] sB
[ _1 sm [lDx]sN ] sC
[  0 sm [lAx]sN ] sD

It's not intended to be great or amazing... just to encode this one idea I had.

Part 2 is the classic scale up with a trick. And when doing part 1 it wasn't lost on me while looking at the examples that the lower halves of the calculation were very simple and filled with zeros. It took a little while to catch on to the fact that part 2 was asking for a section in the last 90% (essentially inside the last line of those size 8 examples). Deep inside the triangular matrix part where you can just use cumulative sum. It makes for short code, and a quick submission once you catch on to that.

But, that didn't feel quite right. So, I followed up by employing what I'd done before for Chronal Charge... prefix sums. Although, from the back so technically it should be called suffix sums. Prefix sums are just a way to pre-calculate values so you can get any sum of a range really fast (table[bigEnd] - table[smallEnd]). And the more ranges you want the better it is to build... and we want tonnes if we want to be able to get near to the front. And so I did a C version, it allocates buffers for the signal and suffix array, and calculates the suffix array, and proceeds to do the calculation. Repeat a hundred times. It does things really fast, unless you want an offset in the first 1000. Then it starts to grind a bit, because the number of ranges you need to sum increases like 1/x curve as you get closer to the front.

It was only afterwards, reading on Reddit, that I found out other ways involving Lucas' Theorem, CRT, and binomial coefficients. I do have a TODO in the directory telling me to probably do such a thing, but I never have. So I really can't talk to much about how that goes. I have a solution that does things in the first half, but is painful if you want things right at the front. It's more than an input needs.

This one felt pretty intense for a Monday problem. It has a trick to maker it easy, but you need to find that trick. But it is day 16.

Time to wrap up. As I said in my last post - this will be my last one since Days 1-4 had so many beginner-isms that it's, well, a little embarrassing. :-)

Sorry about the "dear diary" nature of this one.

Here's an example - for Day 1 (the rotary combination one) I implemented TWO objects. One for the Dial (which seems natural in an OOP experiment). But then another one that held a single method that parsed the line (like "R35") into a positive or negative number. It held no state. Just a "library" class with one method. Then... ok, check this out... here's how I used the resulting signed integer that it returned within the Dial class:

turnDial: turn
    turn abs timesRepeat: [
        position := (position + turn sign) \\ 100.
        position = 0 ifTrue: [zeros := zeros + 1].
    ].
    position = 0 ifTrue: [lands := lands + 1].

Wow. Using a period at the end of every statement like a terminator (my old JS habits of using the semicolon everywhere). This method takes the absolute value of the signed integer, then "clicks" the dial based on the sign of the turn instruction. That's... a little crazy. If I was doing it now, I would probably just do the parsing of the instruction inside the turnDial message. Then the question becomes just how "generic" do I want the solution to be.

Version 1 - not generic:

turnDial: turn
    | offset |

    (turn first = $R) ifTrue: [offset := 1] ifFalse: [offset := -1].
    
    turn allButFirst asInteger timesRepeat: [
        position := (position + offset) \\ 100.
        position = 0 ifTrue: [zeros := zeros + 1]
    ].

    position = 0 ifTrue: [lands := lands + 1]

An ifTrue/ifFalse sets whether the offset is going to be +1 or -1. The loop itself just adds the offset (regardless of what it is), and increments the "zeros" and "lands" instance variables as it goes. But if we wanted it more generic, where there might be a whole library of potential offsets that could be called, not just "R" or "L", we could do it this way:

turnDial: turn
    | offset |

    offset := offsets at: turn first.
    
    turn allButFirst asInteger timesRepeat: [
        position := (position + offset) \\ 100.
        position = 0 ifTrue: [zeros := zeros + 1]
    ].

    position = 0 ifTrue: [lands := lands + 1]

And the offsets library would be defined in "initialize" this way:

offsets := Dictionary new.
offsets at: $R put: -1; at: $L put: 1

Now, if a future version needed a +5 or -15 offset or whatever, it would be extremely easy to add in just one place. No more "if" blocks. Zero branching. Grab the offset value from the Dictionary and go. The Dictionary is only created once per Day1Dial instance, so pretty minimal load on the VM. But what if we wanted it EVEN MORE GENERIC so that the offset could be literally ANYTHING that could mutate the position... We could do it this way:

turnDial: turn
    | modifier |

    modifier := modifications at: turn first.
    
    turn allButFirst asInteger timesRepeat: [
        position := (modifier value: position) \\ 100.
        position = 0 ifTrue: [zeros := zeros + 1]
    ].

    position = 0 ifTrue: [lands := lands + 1]

This one pulls from a "modifications" Dictionary and stores into "position" whatever it returns when passed the current position. There could be a modification that doubles the number, or that resets it to 99 no matter where it is currently, or sets the dial to the square root of its current position, or that reads data from somewhere else entirely. Just add a Block to the "modifications" Dictionary and get additional functionality. For this puzzle, the Dictionary is pretty sparse:

modifications := Dictionary new.
modifications at: $R put: [ :x | x - 1];
    at: $L put: [ :x | x + 1]

Kinda overbuilt for something that just increments or decrements by one every time. But as a learning exercise... why not? And, of course, it would be better computationally to avoid simulating the dial by simply doing some division and adding the numbers to the zeros counter. But.... it's not that many clicks. And this way the Dial acts like a little machine managing its state as it does exactly what the problem says to do. Which leads to...

Observation 1

Smalltalk seems to nudge the developer in this kind of direction. Build it first as "true to life" and as generically as possible. Then, if there are efficiency problems, go refactor those out once they are apparent. But not before. Why put branching logic everywhere when you can pass in a block? Why make a bitmap Dictionary key for memoization when you can use the array itself as a key? Why not reach for the most abstract and "correct" possible representation of the domain? You only have to think about "the machine" (the actual computer) executing the code if there's a problem. Sure, you're dimly aware that there are pointers-to-pointers-to-pointers everywhere under the hood, that very large numbers are being transparently changed from SmallInteger into LargePositiveInteger, that creating a data object involves some dispatch somewhere for getting values out of it. Not your problem. Write it so the concepts are as evident and beautiful as you can.

I often found myself going back and forth on an implementation detail, not because one gave errors while the other didn't. But one was more "elegant" or "expressive" rather than "plain" and "clunky". I would find myself rewriting a working solution in order to have it make fewer assumptions about what was passed to it, or find some way to remove an instance variable so that it could be inferred from the data itself. I would look to see if I could take what was a procedural bit of code and turn it into a chain of collection methods. I found the whole process delightful, though I'm pretty sure each person will have their own take on this aspect of it.

Performance-oriented, or data-driven-development people would likely not enjoy this.

Observation 2

It turns out that I truly love OOP. After using Smalltalk for a few months I can't help the feeling that this is the best way to think about programming. Imagining tiny machines that do the work of the program, sending each other bits of data, each knowing things relevant to themselves and nothing more... It's delightful. Now, I realize it is only one of the ways to think about programming (with others being transformations, procedures, etc...), but it is just so dang satisfying to write. The syntax is incredibly clean and minimalistic, with all the behavior being done by the objects themselves (even control flow). Now that I'm accustomed to thinking about numbers and booleans as objects (with methods that can be explored), it feels very strange to look at a language that treats them as just part of the syntax.

Plus - the late binding gives the developer completely seamless incremental compilation. Methods are meant to be very short. They compile when you save them - you never wait on the compiler at all. It's so cool.

Observation 3

However, I don't think I would feel the same way about OOP in Java or C++. Smalltalk seems to encourage relatively shallow inheritance trees that follow, for the most part, Aristotelian/Boethian hierarchies. So, numbers really are magnitudes. And floating-point numbers really are numbers. And integers really are numbers that have a specific difference from fractions. In the real world we see similar shallow inheritances. Humans really are kinds of animals. Animals really are kinds of living things. But I think whenever that inheritance gets too deep we wind up with serious abstraction problems. And the real world doesn't allow just any set of inheritances. In the real world, "human" inherits from "animal" - but I'm afraid I'm a little skeptical that "mammal" is a real thing, especially since those seem to have gradually appeared with many "transitional" forms in between. Maybe "mammal" is kinda made up - just an abstraction currently popular in biological taxonomy. Is "doctor" a kind of "human"? Or is "doctor" a kind of "job" that can be held by (composed) any number of different kinds of beings?

My limited experience with Smalltalk makes me think that if OOP means "inheritance, and lots of it" then I'm not a fan. My instinct is to use it sparingly, only when "A is a kind of B" is unambiguously true AND there is real usefulness in passing along that behavior from parent to child. OTOH, if OOP means "discrete bundles of data and behavior, interacting with clear messages" then I'm a huge fan. 

Does it scale? I dunno. Is it efficient? Probably not. But my goodness is it fun to write.

Observation 4

Being able to inspect the standard library and see how things are implemented and find new methods that I would use later, or employing the "method finder" tool (amazing) was an incredible experience. Once I was more-or-less "oriented" in the image I felt like it had fantastic discoverability. It was easy to learn how to do new things by looking through the entries in the System Browser. I'm not used to this. My previous "language reference" was a LLM.

LLMs are bad at Smalltalk. Not universally so. But they make many mistakes in this language that I was not used to in JS, where they feel nigh-omniscient at times. Back when I was learning JavaScript, I typically had Qwen3-Next-80b running on my system to act as a language reference. Anytime I needed to know some syntax, or if I got an error I didn't understand, I would ask it. My chat logs are full of mundane questions about how to remove elements from a Set, or what was the difference between "for...of" and "for...in" when doing iteration (hint: "for...of" is the one you want). But for Smalltalk, LLMs would routinely give terrible answers. They would hallucinate plausible-sounding methods that didn't exist, they would get confused about implicit returns in a method, and they would miss obvious bugs.

One particularly annoying one happened when I was noticing that I was getting far worse performance out of a hot loop than I thought I should. I finally figured out that I was passing an expression instead of a block to and:. This makes a huge difference in performance. If and: gets an expression (in parentheses) that expression evaluates FIRST, and then its result (the Boolean true or false) will be passed into the and:. But if it's a block (in square brackets) then it won't be evaluated unless the Boolean being given the and: is already true. The "false" object just returns "false" when given an and: block (Yay for polymorphism!). Most LLMs didn't catch it. The code "worked" and so this kind of issue probably would have survived an agentic coding loop. No errors. But the whole problem executed 3x slower by having parentheses instead of brackets. The LLM wrote a whole thesis about how lower performance was to be expected. WRONG. #sigh

Fortunately, I almost never needed a "language reference" since I had the System Browser right there. And I usually didn't generate errors I didn't understand because I could just visually go through the stack trace and see where the problem occurred. After asking some questions to help me get started, I basically left the LLM behind. Occasionally I would ask it for a code review. When I did sometimes it would find some things that were genuinely helpful. Often it hallucinated bugs that weren't there. Not great.

Observation 5

I can't help but feel a bit wistful and sad when I use the image. It seems to have everything that could possibly be included to help a developer be productive and happy. The language is relentlessly pure, which is, for me at least, very satisfying. I wish it had become more dominant. Many of the ideas persist, of course. But the language itself isn't showing up on any top-25-most-used lists. And I wish it was.

Since I came to this to learn "pure" OOP, I think the purity is part of what I like so much. Whenever I get around to learning another language, I think "purity" will be a non-negotiable. If that means my other options are Oberon7, Haskell, or Clojure, then so be it. :-)

Until then, I have more to learn in this thing. I want to start learning the Morphic GUI and make some desktop applications for myself. I'm already 10 puzzles into Advent of Code 2015 using Pharo. I miss String arithmetic from Squeak6, but Pharo has some cool features that I can appreciate. When I first started I tried Pharo but it was so different from the "Learn Smalltalk" resources that I had, I couldn't make any headway. Now I know enough to make the switch and I'm digging the Calypso browser.

The journey continues.

Today we're at Saturn to do some ISRU and mine the rings (if it's Saturn you must visit the rings) and manufacture fuel. Lots of fuel. For part 2, we're going to be using an input of a trillion ore. The number is there to copy-paste to help make sure you get the right trillion (this isn't long scale) and the right number of 0s. It is the sort of number that's so big you really want to express in a better way in the code so it's clear what the number is later (and so you can easily see it's the right number). A trillion is also nice in that for locales that use myriad dividers, it also ends up with just a 1 in front... 1_0000_0000_0000 (1-chou in Japanese... the chou character also means omen/portent).

As the title suggests this isn't going to be simple reactions... there's going to be ratios. Multiples of reactants producing multiple of a product. It makes things a bit more complicated, so it's a sign that we've definitely moved into the harder problems now. And a trillion being thrown around is another one.

I remember doing this one. I started with a recursive approach and eventually decided against it after making a bit of a mess, so I tossed it and started over. I thought I'd gone immediately to a job queue, but apparently that was the follow-up Smalltalk solution. The Perl one is clearly the first as it's a good deal messier (it could use some clean-up), and it does it with a simpler looping over the ply. Make a list of what's wanted, fill what you can, submit what you need. Loop until there's nothing wanted left. It's a simple approach, and multiple orders in the same ply for the same thing get combined for the next one. The sort of thing that someone that's started over would write.

One thing that's really nice about this problem is the lots of examples of increasing complexity. Including two short simple ones that are fully explained. Although it doesn't give results for those two for part 2. And looking at the numbers in the part 2 example list and doing the division, I saw what I expected to see... you get close just by interpolating. And come up short, like expected, as there's efficiencies of scale (multiple little chunks combine to save ore when making more fuel). And so, I remember using the part 1 script to interpolate and find the answer by hand. It only takes a few iterations. It took longer to write the code to automatically do that later.

This problem is clearly inspired by the rise of factory games at the time. Factorio and Satisfactory were both in early access in 2019. With Factorio preparing for release in 2020.

Today the Elves have sent us a version of Breakout to prevent space madness. Apparently we're either lazy or on a massive ship like Red Dwarf, because we're not willing to go the arcade on the other side of this ship. And so we need to build our own Intcode running arcade cabinet. Or maybe we just wanted to do that anyways.

Part 1 is much like the previous Intcode problem. If you have a good implementation it's a simple state machine to track the output statements (and no input function is needed).

Part 2 finally gives us a taste of what Intcode problems will be... as we don't just have to follow an input protocol, we need to come up with the values to send ourselves. Which can be done by implementing an interface and playing the game if you want. But this isn't a great version of Breakout, the paddle only can angle things at 45° (and also isn't controlled by a "paddle" aka potentiometer)... so we might as well hack the game to play itself.

The simplest way is just to track where the ball and paddle are (when they get drawn) and move/keep the paddle under the ball:

sub input {
    return ($Ball[0] <=> $Paddle[0]);
}

But what made this fun, was that it encourages finding other ways to cheat. Just looking at the input, it's clearly in three sections. The first has the signature values and feel of Intcode. The second is mostly 0s, 1s, and 2s... it is very clearly the starting board layout. The final part is a bunch of 2 digit numbers which is clearly data and there's only purpose for that, a scoring table. The last value is a 6 digit number, which seems to only be there to verify that the input is fully received.

So, first thing to try: draw a wall at the bottom of the input. The board layout is right there, and modifying it is easy for this (and send 0 for input when asked). And it works. So there's nothing special about the paddle in the code. The code reflects off walls, including at the bottom.

Doing this with code requires finding the size of the board and the location. You could just scan from the end for it. I found the loops that draw the board and the less-than instruction against the sizes (x is at 47, y is at 60). I've seen two inputs, and the code section doesn't seem variable length, resulting in the board starting at 639. The table length is variable, because the board is different sizes for different inputs. But, none of that was needed for this... scanning works.

That sort of thing is needed for reverse engineering the scoring. Because the score table is the same size as the board, but it's not accessed directly. It's a transposition multiplied by one constant and adding another, taken mod the size. There's a function to build the stack frame for a score call that sets the magic values (that starts at 601).

my $mult = &get_value( 611 );
my $add  = &get_value( 615 );
my $size = &get_value( 619 );

Getting $size here is more of a validation thing. We can compare it against the x and y dimensions from the loops as well as the expected board start (639) and the values of the table locations that we can grab from the instructions that index the tables:

my $board = &get_const( 588 );      # indexing board instruction
my $table = &get_const( 630 );      # indexing table instruction

The &get_value function evaluates a set (and checks that it is one), the &get_const is getting the immediate mode parameter (as they can be in either position) of the key add. And so my code was filled with warns and dies asserting that the input is what's expected. There's multiple ways to get values, and its easy to compare them for sanity. For example:

die "Mismatch: start of table ($table) with end of code"    if ($table != $#Code - $size);
die "Mismatch: start of board ($board) with end of code"    if ($board != $#Code - 2 * $size);

In the end, the scoring for a block at ($x,$y) is:

my $sc_off = (($y_size * $x + $y) * $mult + $add) % $size;
$score += $Code[$table + $sc_off];

The routine that does this is at 429 to 455. But the routine from 456 to 546 was also fun to look at. As you see, we need mod, but Intcode doesn't have it. The 456 routine does mod by repeated subtraction. But not just a plain and simple loop... the mod is of a multiplication which can get fairly large. And to accommodate that in a faster way, it does it in steps... first by subtracting 64 * $size then 8 * $size and finally $size. Without that, the code would be slower. And the run of my input is already at 550k instructions.

I just loved this one. It reminds of back when me and my friends were hacking around exploring and modifying games.