In order to make our flight, we need to rent a toboggan to get to the coast. But in order to do that, we need to fix rental shop's password database. And so we get a classic type of puzzle, string validation.

Each string this time has its own special rule, given by two numbers and a letter. The numbers are presented as a range, but only used as such for part 1.

For part 1, we want letter counts... and that's always fun with Smalltalk, where it's just "throw the string in a Bag" (a Bag being a multiset... internally you expect it to be a dictionary mapping values to their counts). Resulting the in the check being range includes: (password asBag occurrencesOf: letter). An example that really shows the era that Smalltalk was created in (where natural language-like was the goal). Of course, you don't need anything that fancy, making things very approachable for a beginner. You only have one letter of interest, so you can just iterate over the string and count it (parsing the input is harder).

For part 2, you just need to look at the positions in the original string, which seems simpler. But it does add two small complications... one is that the indexing is base-1. Which is how Smalltalk indexes strings (so this one was extra nice for Smalltalk)... but most modern languages are base-0 and need to shift (and the problem provides warning in the description that this will be needed... it is day 2). The other is that it wants only one of the ends to match. Which just means, we should use our old friend XOR (exclusive-or). Something that's always nice to remind or show beginners that it exists. Because it is a very useful thing.

For 2020, we decide to take a vacation after saving Christmas five years running. And 2020 was a pretty rough year all round, and this AoC did take things noticeably easier on us. I know a number of people who regularly end up dropping out in the middle that made it to the end of this one. Although, they skipped day 20 (which isn't so much hard, as a lot more work than most others in this year).

The map for this one is notable because, after the first 8 days, there's a mixed section where we go down-up-down (looping on the map) before finally getting another run at the bottom. It's harder to follow on the finished map than when doing the problems, where I could just follow the line to the end to get the next problem. Another fun thing about this year is that all the names are alliterative... except for the "Combo Breaker".

Anyways, we need 50 gold coins called "stars" in the currency of our destination. And to start, the Elves are going to catch us on the way out to fix the expense report. A simple day 1 problem involving working with a list of numbers.

The list is 200 numbers, all less than 2020, and unique (and nothing less than 200 in mine). We need to first find the pair that adds up to 2020, and then the triple that does (which is why there's definitely not going to be a 0 in any list). Easily brute forced if you want, but it's easy to just keep a table of what's seen... if the complement is there, you've got your answer. For part 2, I mapped the sum of pairs to their multiplied value. That way when a third one looks for the compliment, it can see it exists with the key and then multiply the value by itself for the answer.

As usual, I did day 1 in dc... it's nice to have input that dc can understand directly:

dc -e'[?d1r:ad2020r-d;a0=L]dsLx*p' <input

dc -e'[?d0[rd3Rd1+r;i3Rd3Rd3R*_3R+:ad;i0<I]dsIx:id2020r-;ad0=L]dsLx*p' <input

Originally, these weren't using ? for input or the R operator. Part 2 involved a bunch of messing with registers, mostly to do stack operations 3-deep (which are such a common thing... you duplicate the top of the stack to have a copy to do an operation and now the other number you wanted to work with is 3rd). You can see in part 2, there's a d3R d3R which is a common idiom I call ABBA because it copies the top two items on the stack (and that's the shape you get... if you want AABB that's Sad Lad). Then there's a * _3R+ :a, which multiplies 1 pair, tucks it, adds the second, and then sets the array.

I was surprised to find that these still work with with the newer GNU dc 1.5.2... the change in ? behaviour only causes things to be spammy here. The newer version feels it necessary to output all the values it reads.

Another thing to note about these is that they assume there's a solution and that it's unique... that if there are two pairs of numbers that sum to the same thing and multiply to different values, they will not be part of the solution. This is a classic example of "meta-puzzling". Technically it's something you should handle, but it can be ignored because this is a puzzle with a unique answer.

Today we arrive at Santa's Reindeer-class starship. Now dead in space. We breach the hull to get a small droid on board to find the password to the airlock. And thus begins ADVENT for Advent of Code. Back in the 90s, me and a couple friends were having fun playing Infocom games together, with lots of silliness. Discussing each move and coming up with the stupidest things. While playing Plundered Hearts ("Swoon!"), it drove one of our younger friends to go off and play the game himself... only seriously. It didn't take him long to hammer through, but we had a lot more fun.

This was a change of pace... for Christmas we get gifted a text adventure game to play. So that's what I did that day. Map the ship, collect the items (everyone gets a selection of 8 from a longer list... I remember discussions that day collecting the list) and discover the traps (everyone gets the full set of 5... it'd be a shame to miss one). Then solve a little logic problem of matching the correct weight on the pressure plate.

I remember the first thing I solved with my input was that the mutex was the heaviest item... and carrying everything but the mutex wasn't enough. So it was required. The candy cane and the loom when added to the mutex made things too heavy, which ruled them out. After which I pretty much stumbled on the answer quickly while doing tests of the rest.

I did find a second input, and that one was a little harder. A few tests left me knowing that either mutex or candy cane was needed, and testing the mutex discovered that mutex + anything is too heavy (mutex happening to be the heaviest there too), so mutex wasn't in the solution, candy cane was. And so on.

So it's a little logic problem, and it did feel like the heavy items were really heavy... like orders of magnitude. Any given item was always heavier than the sum of all lighter items than it. So it wasn't surprising when I reverse engineered things much later than the masses are essentially bit flags.

First step to reverse engineering was decoding the strings (well, I did spotted the powers of 2 table, and biggish numbers in the 4600s that I thought were likely weight related data). The first thing the code does is output the text for the Hull Breach room, and it needs to run the decoder to do that, so just watch it run. Strings aren't null terminated, they start with their length... the character values are shifted by + index + length. My decoder function does this:

my $len = $code[$addr++];
for (my $j = 0; $j < $len; $j++) {
    $ret .= chr( $code[$addr + $j] + $len + $j );
}

With this I could run through the code and dump all the strings, getting their addresses, which allows me to find where specific routines and data are. Like that the first statement (after setting the stack pointer) is to load the address of the first room (Hull Breach) data (3124) to print it. Examining that area we can work out the room data structure:

3124 - @3131 Hull Breach (name of room)
3125 - @3143 Description of room
3126 - 0 or 1553                               false or check inventory routine
3127 - 0                                       NORTH
3128 - @3252 (Crew Quarters structure)         EAST
3129 - @3401 (Holodeck structure)              SOUTH
3130 - 0                                       WEST
3131 - Name length
3131 - Name start
...
3143 - Description length
3144 - Description start
...

And so on. Last two are the Checkpoint (@4457) and the Pressure Plate (@4556).

After which we get the items staring at 4601. The structure for them is four values for each:

+0 - location
+1 - name
+2 - mass (+27 + index in item table)
+3 - 0 or address of special take routine (for traps)

The masses are 0 for traps and distinct powers of 2 for the others (bit flags), once you subtract 27 and the index. (Both the inputs I've seen use 27 here).

The answer is encoded in a table from 1901-1933... one bit per value, determined by a threshold. The threshold is calculated by the instruction at 1582. The values accessed by that are hidden by storing them between functions at 2486 and 1352:

[2483] 2106
[2484] 0
[2485] 0
[2486] 89
[2487] 109
[2488] 1

The first three values are how a return statement is done (the other way is 2105,1,0), and the last two are allocating stack (the start of a routine).

Both inputs I've seen, the solution is 4 items and so 4 bits. So the threshold could be ignored if the number of bits is always 4 (just find the four largest numbers in the table).

There are a bunch of other interesting things to look at, like the parser and the function that outputs the number for the answer (doing printf).

Of course, reverse engineering isn't the only way to code a solution... you could do a little "expert system" that can play the game, build the map, knows what's a valid item, picks those up (avoiding traps), and heads to the checkpoint and does some algorithm to find the combination. I haven't bothered doing that yet... instead I have a messy little randomizer, which I think is important to have first, because it allows me to mess with things and produce new inputs with specific characteristics (like different numbers of bits, maps that have loops, new descriptions and items) to properly test such a system.

I love this problem... it's an example of something that can only have been done in the Intcode year. Intcode is most of what defines this year, with problems that can be treated as black boxes that just provide an interface to an unknown machine, but can also be examined. It also gave us the experience of coding in a new language. The problems in-between those are also really solid... we got some nice exploration of linear transformations and recursive geometries. It was nice going through now to notice that the oxygenation maze is similar to the Universal Orbit Map, something I hadn't really thought about before. This is probably my favourite year, part of that is that Intcode makes everything gel together into a larger experience.

Landing on Eris (née Xena), we find it infested with bugs. The fact Eris is 5x5 is not surprising. Five is a sacred number in Discordianism. And Eris is truly a planet of Discord, it made the IAU come up with a new definition for planet which changed the status of Pluto and Ceres. I suppose there's also an element of irony in "5 by 5" in that a signal being strong and clear wouldn't help us... signal delay is why we need to deal with the problem ourselves.

And so we get a cellular automaton. Part 1 is on an extra small grid... it's 25-bits, and you want the first repeat, and the answer is those bits in reverse at that point. If you add sentinels then they need to be stripped, so I didn't for this one. Other than that, I just went double buffer with a hash for finding the repeat. Nice and simple.

Part 2 changed the geometry, and we're back to infinite recursive doughnoughts. This complicates the neighbourhood. But since there's only 24 different cells, it's easy to build a table of their neighbours... (y, x, depth), with depth being a delta (-1, 0, or 1) to add to the current depth, and y and x being direct indices. That way all the special casing is done once at the start. Not that that's crucial, At 200 generations, things have only expanded 100 layers in each direction and there's only 24 cells per. That's easy to just statically declare and do whatever type of automaton method you like, and still be reasonably fast. So it's a pretty accessible problem for day 24.

I don't really have a lot to say about this one... I do like cellular automata, and the geometry is interesting for this one. But I didn't really do anything special. I do have a Smalltalk version in the directory that was done after 2020, which had a number of cellular automata that year and so I wrote a class to generalize the solutions. That allows me to do this:

auto := Automaton space:    (Eris load: input)
                  dieRule:  [ :neigh | neigh ~= 1 ]
                  liveRule: [ :neigh | (neigh = 1) | (neigh = 2) ].

('Part 2: %1' % {auto runTurns: 200}) displayNl.

The Eris class is a sub-class of the virtual class Space that requires its subclasses to define the geometry by supplying a #neighbours: method and load the input by sending #setAlive:. And then Automaton will use that to track active cells and apply the rule blocks. It's not necessarily the fastest... it just generalizes the problems to a simple interface.

i was trying to solve this problem by grouping the intervals into two categories: the overlapping ones and the non-overlapping ones. Then, I could group the overlapping intervals into one and calculate the size of that big interval.

I implemented it in python and it works in the test case the problem showed and any test case I can think of.

can someone help me?

the code is the first code block here

https://colab.research.google.com/drive/1GjizwT87FN9xJ3GWQRnTnGTyRGPptkHq?usp=sharing

(ignore second code block its another day's code)

Having repaired the hull, we now work on rebuilding then network. And so we get another multi-process Intcode problem.

Up until this point, my day 7 solution was an enigma... this weird little thing that didn't use my standard Intcode module at all. Getting a second multi-process problem meant I finally added, not the multi-process functionality, but the ability to build that functionality on top of the module.

And that was done by implementing the ability to have the machine break on input. So I built the processes in a table:

foreach my $pid (0 .. PROCESSES - 1) {
    $Proc[$pid]{inq}  = [$pid];
    $Proc[$pid]{outq} = [];
    $Proc[$pid]{vm}   = new Intcode( Mem => [@Code], break => OP_IN,
                                     input => \&input, output => \&output );
    $Proc[$pid]{running} = 1;
}

And run the entire machine with:

while (1) {
    my $op_code = $Proc[$pid]{vm}->run();

    if ($op_code == OP_IN) {
        &yield() if (!$Proc[$pid]{inq}->@*);
    } else { # OP_HALT
        $Proc[$pid]{running} = 0;
        &yield();
    }
}

Co-operative multitasking. Where processes have complete control until they &yield, which runs the scheduler. In this case, they hand things back if they have nothing in the input queue or have halted. Of course, a process doesn't really block on input, so the trick here is that when the process runs again, it's always forced to run at least one instruction before breaking a second time (and that instruction will be the OP_IN it broke on). This means that if the process still has no input when the scheduler comes back to it, its then forced to send -1.

Part 1 is done by the output handler, which buffers output in its queue until it has a message to send (3 items). That's either to the NAT, or to another process' input queue.

Part 2 is done in the scheduler. When pid 0 is chosen, it checks if all other processes are idle (dead or waiting), and if so, it handles the check for part 2 (and sending the message).

Overall, a simple little multitasking OS that was fun to write. And then I went back to make day 7 use the same break feature and the standard module, making everything using the same library.

As for what this does, I never reversed engineered it myself. Beyond that it starts with getting an input, adding that to 11, and using that to reference a jump table between 11-60 (which is followed by a bunch of 0s... there's also a big table of binary bits in there that really sticks out). So the code is a bunch of small routines, which apparently send constants, add/multiply/divide values, and calculate some cubic polynomial.

Here's a thread on it: https://www.reddit.com/r/adventofcode/comments/een9mk/2019_day_23_part_2_what_is_the_network_computing/

Today we're still in space waiting for the ship to be repairs and shuffling cards. But we do get a fly-by of Halley's Comet (1P/Halley). Which has passed apoapsis since this this question originally ran, and is now closer to its next appearance than its last.

Today we're getting another scrambling problem. Part 1 with the small prime sized deck of 10007, and part 2 with a much larger (47-bit) prime. The part 2 deck would have a mass of about 1/1000th of Halley's Comet.

For part 1, it's easy to just manually do it, the shuffles are all simple things. It was not lost on me that this time there wasn't a non-linear thing like a swap in there. But I still put off doing the composition while doing a more efficient part 1 to think about if there wasn't some dynamic trick I might also be missing.

But ultimately, it came down to the fact that, this time, unlike previous scrambles, the shuffle methods are all linear and compositions of linear transformations are linear. I remember the first math class in high school to bring that up... it was just mentioned at the very end of the term, dropped like it needed to be in the curriculum and not explored or tested. It wasn't until years later in University that Linear Algebra made the point of how useful this is. And this problem is also a great example why.

The shuffles are (in mod p):

• deal into a new stack (-x - 1)
• cut c (x - c)
• deal with increment m (mx)

They're all linear of the form Ax+B and when you compose them you always get some A'x+B' (ie things don't suddenly explode into quadratics with a new x² term).

For example, composing a stack deal with an existing Ax+B:

-(Ax+B) - 1 => -Ax + (-B-1), giving A' = -A and B' = -B-1

In general, for an Ax+B and Cx+D:

A(Cx+D) + B => ACx + AD+B, giving A' = AC and B' = AD + B

And with a function that does that, you can compose all the shuffles listed together into one A'x+B', and then compose that with itself the number of times you want to shuffle, producing some A"x + B" representing the entire transformation.

But the number of shuffles we need to do is also a 47-bit number. Fortunately, we can easily divide and conquer. Because if you compose the initial full shuffle with itself you get the transformation for shuffling twice. If you compose that with itself, you get 4x, and again gets you 8x, and so on. We've done this for previous problems before. It just happens to be extra good here.

Because we still need to find the answer once we've got the constants for the linear transformation of all the shuffling. Which is to say, what x for our Ax + B ≡ 2020 mod p?

Ax + B ≡ 2020 mod p
    Ax ≡ (2020 - B) mod p
     x ≡ A^-1 * (2020 - B) mod p

That's our x, and so we're left with needing to find A^-1, the multiplicative inverse of A mod p (to multiply 2020-B by). Which is where another theorem that's immensely useful comes in: Fermat's Little. Typically expressed as "a^p ≡ a mod p" or "a^p-1 ≡ 1 mod p", but we want to see it as "a⸳a^p-2 ≡ 1 mod p" here. Because that tells us what to multiple A by to get 1 (which is the inverse), namely A^p-2. Which can be found with the same divide and conquer we used to shuffle... the exponentiation is just composing Ax with itself p-2 times (with x=1). There's the extra good.

I loved this little math based problem. Linear transformations and Fermat's Little Theorem are two very useful tools to know.

Today we're apparently flying in the direction of Santa. But if you're watching the animation on the AoC 2019 page... you'll see that we're actually going perpendicular to where Santa is. Anyways, we run into a Kuiper Belt object and need to inspect the hull using a springdroid, which accepts input in springscript as parsed by our Intcode computer.

And so we get to program in another specialized language today. And that's how I solved it. And I 've come back and solved a few times over the years, resulting in different solutions. All by hand... except for when I reverse engineered it.

In looking at the problem now, I first worked out another solution for each part. And then I ran the various solutions through my command line Intcode runner to dump stats on them (I found two that were actually the same). My new solution for part 1 ended up being the shortest length by 1 character (43 characters... it uses two ORs), but runs slightly slower than the best (23759 instructions to 23304). My new solution to part 2 ended up being the most efficient one I have (at 445574 instructions to the previous best of 457345... one of those takes a whopping 821844 instructions, it is 14 lines which is one short of the max allowed).

My best for part 2 is:

NOT H T
OR C T
AND B T
AND A T
NOT T J
AND D J
RUN

The second best is almost exactly the same, but it only uses the J register (never T). Apparently, if you want to bum springscript, you should use T over J when possible.

Reverse engineering this one wasn't that hard (and there's sample code now so its now trivial if you use that). There's a clear data block in the middle that looks like 8-bit numbers mapping out in binary holes for the test cases. There's a few at the start beginning with 255 and ending with a delimiting 0 which are the tests for part 1. The 255 test isn't just a solid floor... all the tests involve a hole in the 9th-bit, so it's the test you see drawn in the example of jumping into the first hole. Part 2 includes part 1 and the remaining values.

The scoring is classic video game scoring... you get points when you're jumping and over a thing (ie a hole is under the player). The base points for it are based on the bit the 0 is in. Since we're going left-to-right, they count up from the high bit (bit 9) starting at 10 (at least for my input... I haven't really looked at the sample to check that). The sum of all the zero locations then gets multiplied by the address of the test and test value itself. Which means that different orders of tests produce different scores.

Something that's important because part 2 appears to test every pattern with gaps of no more than 3 (our jump distance). Outputting all the values in the table in binary and sorting them makes this clear (it has the binary count look, only skipping numbers with holes too big). So we have a situation in that all the inputs are doing the exact same cases (just in a different order). And the "solution" really feels like it's the springscript code, but the "proof of work" for that is calculated differently for everybody. There are problems that come close to this, but never quite this much on the nose about the nature of what's submitted compared to the solving. It's a philosophical difference, that this problem really make me feel.

Maybe that's just because I've never written code to generate solutions for this. That could just be writing a systematic search for scripts that handle all situations. Or you could write a genetic algorithm to refine scripts until one works.

Maybe it's also the levels of indirection that give that feeling... normally a "solution" is unique code you write, that will produce the same answer as other people's to a given input. Here the solution is the unique stuff you do (hand or code) to get springscript (still somewhat unique), that your Intcode machine verifies, to produce a proof of work, that the website validates.

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.

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² ), 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² /c² 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.

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???

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.

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.

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

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

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.

One of the biggest performance surprises I've had so far squishing my solutions onto a Raspberry Pi Pico (RP2040) is day 25 for 2015. I knew the RNG was going to need 64-bit maths and that it would fall back to a software implementation, but I didn't predict just how slow that would be. The straightforward form of the solution takes a whopping ~27s to run through the ~17.8M multiply & modulo operations required!

Still, it's a good excuse as any to mess around with some maths and and some assembly.

64-bit multiply

The M0+ in the RP2040 doesn't have the UMULL instruction that produces a 64-bit result from two 32-bit values; you're stuck with MULS producing a 32-bit result. Grid method multiplication allows you to produce a full 64-bits across two 32-bit registers by splitting the input values into 16-bit pairs and doing the multiplication piecemeal:

[b:a] * [d:c] = [hi:lo]

Where:

• [b:a], [d:c] - 32-bit input values
• a, b, c, d - 16-bit halves of the input values
• [hi:lo] - 64-bit output in two 32-bit values

Then:

• [lo] = (a*c) + (c<<16) + (d<<16)
• [hi] = (b*d) + (c16) + (d16) + carry from lo

The carry is a pain to represent in C++. GCC provides __builtin_addc which is supposed to map to the correct ADCS instruction, but I didn't see it doing so in the generated code. I can only assume the structure of my code wasn't exactly right for GCC to perform the substitution.

It's much easier to control in the asm though.

64-bit modulo

This part took me a while to get my head around, but it turns out we've been quite lucky with the constants chosen for this puzzle.

The two basic rules of modular arithmetic we're interested in are:

• a1 * a2 === b1 * b2 (mod m)
• a1 + a2 === b1 + b2 (mod m)

Where:

• a1 === b1 (mod m)
• a2 === b2 (mod m)

Which allows us to do this:

• [hi:lo] % m === (2^32 * hi + lo) % m
• [hi:lo] % m === (2^32 * hi) % m + (lo % m)
• [hi:lo] % m === (2^32 % m) * (hi % m) + (lo % m)

2^32 % m is just the constant 4992:

• [hi:lo] % m === 4,992 * (hi % m) + (lo % m)

Each loop of the RNG is:

answer = (answer * 252,533) % 33,554,393

Which means the the largest intermediate value for the RNG is 33,554,392 * 252,533 = 8,473,591,274,936. The value in the upper 32-bits is therefore less than or equal to 8,473,591,274,936 / 2^32 ~= 1,972.

Since 4,992 * 1,972 = 9,844,244, and that's less than 33,554,393, it means that 4,992 * hi value is already modulo m.

• [hi:lo] % m === (4,992 * hi) + (lo % m)

We're adding two values that are both modulo m, so there's a chance that it will go over m, but it will always be less than 2 * m.

The net result is that we can do the 64-bit modulo with a single 32-bit multiply, a single 32-bit modulo operation and a single 32-bit subtraction if we're above 33,554,393.

Thankfully the Pico does have 32-bit integer divider hardware, so we can make use of that.

Putting the two reductions above into C++we get ~8.5s.

Hardware trickery

In order to push this even further I made the jump to asm. I couldn't seem to get enough control over the code generated from the C++ to really optimise the multiply, and the real party piece is to make use of the 8 cycles that the CPU has to wait for the divider hardware to generate a result.

By sheer coincidence the five instructions that weren't dependencies for the lo register just so happen to have a minimum cycle count of 8; meaning we get precisely zero wasted cycles waiting for the hardware div/mod to complete!

My final runtime for my input ends up being ~5s, which is about half a second faster than my intial guess at where I thought I might be able to get to. Quite pleased with that.

[Full solution]

At Jupiter we find ourselves needing to track the Galilean moons. And so we get to work with a discrete physics model again. This time we're not given a value for acceleration, but a method to calculate the current gravitational acceleration of an object in the system. Not a realistic one, but it provides the same functionality of holding the system together.

The title alludes to the fact that there typically isn't a nice general formula for the orbits of objects in a system, and so this sort of simulation is a common thing to do. I remember having code for an N-body simulator on the C=64. Put in the values for a model of the Solar System, and after a year, Jupiter rips through the inner system, flinging itself and all inner planets out. You need high precision and processing power (to do tiny steps), and this lacked both.

As for this problem, it's not much different than the last problem of this type (apply acceleration to velocity, then velocity to position), except that we need to work out the gravitational effects between all pairs. I did speed up my Smalltalk solution by pre-building a list of the pairs of Moon objects as I read the input and created them (instead of the triangle loop of indices and doing look-ups all the time, just make the list once of all pairs of object references). You calculate the gravitational acceleration between them, and add it to one and subtract it from the other (because symmetry).

Part 2 comes along and nicely warns you not to brute force it (my answer is 48-bits). My first solution made the easy jump to the fact that the dimensions are independent. They'll each have a cycle, and the lcm will get us the answer. But I didn't think further than that to start... so I looked for loops on each dimension with position and velocity. I did conveniently print out the states when I found a cycle, though. Which lead me to noticing that there was a column of 0s in the velocity vector at the dimension that was looping. Leading to thinking a little bit more and realizing that the system is invertible. Since any state can run backwards, it must loop at the start. Reducing the check to look for just 0s in a velocity column revealed the final detail when I didn't get the correct answer. That the system reverses half way through the cycle (momentarily stopping before the symmetry reverses things), so you can find the "half-loops". Which for lcm means that all the values have additional common factor of 2 that was missing.

And so, this is a nice little problem. Discrete physics is always a little weird, in that physics is normally Applied Math and Calculus, but we end up finding ourselves getting into Pure Math and Number Theory territory.

Today we get a warning from the Space Police and need to build an emergency hull painting robot (we have painting emergencies often enough that this is a thing?) to put our registration on the hull.

Today's Intcode puzzle seems to be about checking that we're ready to attach the input and output to custom applications. If you have a good API, this is short and sweet. Two short functions/methods to use the Intcode machine to get the data, and a function to display it.

Part 1 is another Langston's Ant thing... this one shows what's interesting about Intcode type problems. If we're given the details of the machine to implement, then we need to be given a starting grid in order to have different answers. The Intcode machine reverses that... everyone starts blank, and the input is a black box. You could reverse engineer it, but it's simpler to just use the Intcode machine and not care. This allows for types of problems that couldn't be done otherwise.

Part 2 outputs the ASCII art text of our identifier. Initially when I ran it, I just dumped the final image. But, on the day, I followed up with a version using curses to show the painting in action. And when you do that, you see the zig-zag pattern the robot takes. It was clear that there wasn't any funny state machine over tracing going on. And so it works fine with replacing the input subroutine with input => sub{1}.

So with that, I figured there were some big numbers that were bit patterns of the image that it was dumping. They were not hard to spot, and outputting the first in binary and the bits along the pattern I saw it tracing revealed it wasn't being obfuscated (other than with the path). And so I initially did a reverse engineered solution that just grabbed those numbers and traced them out (jumping the bot and reversing it every two).

But, that's not very robust, so I decided to improve it a notch, by having the code find the numbers. To do that, I use this loop:

for (my $curr = $code[4] + 6; $code[$curr] != 99; $curr = &get_value( $curr + 4 )) {
    ...
}

Address 4 is the jump location for part 2. This is the location of the instructions that build the stack frame, with the first setting the bit pattern we want, and the one after (at $curr + 4), setting the address to return to. Which is either the next place we want, or the code for a turnaround (in which case it will have opcode 3, because those are a sequence of in/out/out) immediately followed by it. When we get a turnaround, we can use it to reposition the robot (the turns are given by the second out). Which leaves us on the instruction with the magic number (which we can get with &get_value( $curr )... that's the function that gets the value from a set instruction). Once we have that, we rip it into 4-bit chunks and trace out the little us. And so, I have a solution that runs several times faster than the VM one (not that part 2 takes any time, it's 8k instructions to part 1's 100k). And it's still capable of some flexibility (wider image or more layers in addition to different sized part 1s). The point of doing this originally was to explore the code, more than out of need to have a faster solution.

Today we're at Ceres monitoring asteroids... and later shooting them. The input is a grid, but that's really just a way to provide coordinates to them. Because we're not just interested in orthogonal or diagonal lines between them, and so we can "slip through the cracks". Not that that that's hard... space is really big. There's lots of room. It's only exactly the same slope lines that block line of sight.

And that's really the key... you need to reduce the deltas into a slope you can use. You could go with floating point, but that feels like defeat to me. All you really need is to reduce the ratio of the delta-y : delta-x to lowest form. Which involves find the gcd. I coded my own version of Euclid's Algorithm for this from memory, and then refactored to just ($a, $b) = ($b, $a) while ($a %= $b). With that, we get nice integers to compare (and don't have worry dealing with float point quirks). And the gcd is also useful for part 2... for any slope the gcd is the multiple of steps along it, so it can order asteroids to show which gets shot first.

As for the ordering of that, there's a number of ways. I know a lot of people used atan2, but not me (ick floating point). There are other ways, like pseudo-angle formulas designed for exactly this... they give you a value that orders the same, for when you don't care about the exact angles, just the relationship.

Me, though... I went with 2D cross-product. It's something I used in my first job for a similar task. Cross-product is normally a 3D function between two vectors that provides a perpendicular to them, with handedness (fingers are a and b and the thumb points points up or down depending on the order). When we take two points in the plane z=0 (as vectors from the origin), the perpendicular is going to be of the form (0,0,z), with the sign of z giving us order information.

There's only a slight problem... cross-product does care about specific directions and we do here. It's not going to treat 12 o'clock special (11am is before 1pm), and it's going to assume that you want consider direction of angle that's smaller. But that's easy to fix. First off, a vector at 12 o'clock wins (conveniently we don't have to worry about equals because we're sorting the reduced slopes which have been made unique):

if ($a->[0] == 0 && $a->[1] == -1) {
    return( -1 );
} elsif ($b->[0] == 0 && $b->[1] == -1) {
    return( 1 );
}

Next up, if the sign of the x co-ordinates is different, then the one on positive x wins, which conveniently corresponds to the sign of bx.

if (sign( $a->[0] ) == -sign( $b->[0] )) {
    return( $b->[0] );
}

And finally, now that we've established the start and made it so we're only comparing things on half the circle, 2D cross product (this is all that's left when the 0s wipe most of it out):

return ($b->[0] * $a->[1] - $a->[0] * $b->[1]);

That's it. It's simple and all integer. Exactly how I like it. And that's why I remember and like this puzzle (plus, Ceres). I got to pull out something from way back that's cool and figure out how to make it work again.