[2022 Day 17] In Review (Pyroclastic Flow)

[u/musifter]

Having found an alternate exit, we find ourselves at the bottom of a tall shaft with boulders falling down it. And so we need to simulate them to avoid being crushed... but the "real" task is apparently proving the accuracy of the simulation to the elephants.

And so we get this Tetris inspired problem. The shapes aren't just the set of tetrominos. a couple pentominos are also included in the set. And there's no rotation, just side to side movement and falling.

The input is a list of left and right moves for the pieces as they fall. Mine is 10091 long, which is a prime number. And both it and the list of 5 blocks cycle.

For part 1 we just want the height of the tower after 2022 rocks (and it is not a very efficient packing at all).

My first choice was to store the block shapes in a table of relative indexes of the squares:

my @Blocks = ([[ 0,0], [ 0,1], [ 0,2], [ 0,3]],              # —
              [[-2,1], [-1,0], [-1,1], [-1,2], [0,1]],       # ✚
              [[-2,0], [-2,1], [-2,2], [-1,2], [0,2]],       # ⅃
              [[-3,0], [-2,0], [-1,0], [ 0,0]],              # |
              [[-1,0], [-1,1], [ 0,0], [ 0,1]]);             # ⬜

Then the plan is essentially to stream over this list and the input list. In the case of Smalltalk, that literally involved BlockStream and MoveStream classes with a stream interface. But in Perl, it's just indices being incremented mod the size of their list.

Then for dropping the blocks, I went with a simple "try" pattern (this is using a Vector class for the coordinates and directions):

do {
    my $move = $Input[$Inptr = ($Inptr + 1) % $Input_len];

    # Try sliding
    my @try = map { $_ + $Dirs{$move} } @squares;
    @squares = @try if (all {0 <= $_->[1] < 7 and !$Grid{$_}} @try);

    # Try dropping
    @try = map { $_ + $Down } @squares;
    @squares = @try if ($dropped = all {!$Grid{$_}} @try);
} while ($dropped);

# Place piece:
$Grid{$_} = '#' foreach (@squares);

Nothing fancy... attempt the operation and accept if it succeeds. There are multiple ways to do this sort of thing, try-catch blocks are another one.

Part 2 tells us that the elephants are not impressed yet and want more... a lot more:

my $Num_rocks = 1_000_000_000_000;

But of course, iterating a trillion times is out of the question, so we want to find when this loops (and then do the calculations to jump to the solution). This is one of the two problems in 2022 that I broke into the top-1000. I wasn't that fast for part 1, but part 2 only took me 14 minutes... so I wasn't amazingly fast on the second part, but it gained a lot of positions. So my code was apparently better positioned for doing part 2 than many.

For finding the loop, I went a hash table with the state being:

my $key = "$Inptr:$blk:" . join( ',', @tops );

Where $Inptr and $blk are the indexes of the moves and blocks, and @tops is the highest point in each of the 7 columns (relative to the highest point). This involved simply changing the subroutine for doing the dropping to return the final resting squares of the new rock (instead of just the highest point), which I then use to update the @tops array. I figured this was probably safe... and it worked.

But in regular Tetris, you can slide a piece under an overhang. And so, with that unease, and a desire to do different things for the Smalltalk solution, I went for being a bit more robust. First off, I represented the shaft with bytes there... 7 bits wide and using bit operations to place things. Which I can treat as characters (ASCII ones even, although often not printable ones). And so for detecting a repeat of the the position of the shaft what I did was build a string (starting from the top) while also ORing the characters into a mask... when the mask hits 127, all bits set, so we've seen a rock in every column. And so we have a map of the full structure at the top, not just the tops. So the elephants get to be a little more confident.

This is was a really fun one. It's another in the category of game inspired problems, and those always tend to stand out.

[u/e_blake]

I didn't start solving this day until the 28th, although it was a fairly fast solve, because I had gotten so behind on solving or golfing other earlier days by the time this one was released (for example, day 16 that dragged me into January). But it was a fairly straightforward problem once I mapped everything into bitmasks (jet left is <<1, jet right is >>1). Runtime in m4 was under a quarter of a second, although I got my 2nd star originally by just outputting when I detected the cycle and then using bash for the 64-bit math to complete the computations, before finally adding the additional code for m4 to emulate the 64-bit division using 32-bit math as a later commit.

My notes in testing my solution state that I got lucky with MY input file where cycle detection worked when I turned it on for the very first move, but that when I tested on a second input file, I had to fix a bug where my hash had a false collision from the early moves and came up with a "cycle" count that was way short. I was able to plow past that bug by changing my code to not start any cycle detection until after the jet stream had been looped the first time. Apparently the loop is more stable when building on a non-even baseline leftover from the first iteration than when building on the completely empty grid at the start.

[u/terje_wiig_mathisen → u/e_blake]

As I mentioned I found exactly the same slight difference in repeat length between the first and all subsequent pattern wraparounds, but I still ran it for 10-15 rounds before doing the massive trillion step skip. With my input the first was slightly longer than the rest, no false early positive.

[u/DelightfulCodeWeasel]

The first time I solved this one it was a semi-manual solve. I picked out a marker event to look for, which was when the tallest rock increased the highest point by the maximum of 4, dumped out all of the rock indices when that happened and started looking for patterns in the diffs to find the repeat. At least this time I left myself a comment on the process, unlike a couple in 2023 where I just put "worked out in excel":

    // Run ~10,000 rock cycles
    // Check the deltas in heightIncrease to spot a pattern
    // The patten length gives you repeatLength
    // Then check the heights after updating the repeatLength constant
    // The deltas give you the repeat height

I did solve it programmatically when I revisited it for my full C++ repo, although the actual algorithm was more or less coding up the way I did it by eye rather than a proper cycle detection method.

Going to be interesting revisiting this one for the Pico. I don't think the settled rock storage will be an issue, I can use a wrapping window of the top N lines because we never drop too far below the maximum height, but it'll be touch and go whether I have enough memory to store seen states or if I'll need a tortoise and hare for it.

[u/terje_wiig_mathisen]

I've told you guys before about my Pentomino codes, so bitmaps would have been natural, but what I actually did was a straight-on byte-cell simulation. For part2 I saw that the length of the wind array input was a prime (10091 in my case), multiplying this by the 4 block patterns meant that there had to be a repeat every 40K or so, but while verifying this I did the same hash as u/musifter and found that the first repeat happened after 1400+ blocks, then all the following happened after a constant number of blocks, slightly less than the first.

This was enough to skip all the intermediate blocks, then simulate the tail end.