u/musifter

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 right at the end of the term and 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 an x^(2)).

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 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 got 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^(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.

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.

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.