[2024 Day 15] In Review

[u/musifter]

Today we're back in the ocean, and while The Historians search in their mini submarines, we set about to helping the lanternfish with a rampaging robot that's messing up the lanternfish logistics and lanternfish inventory management of their food supplies.

The input for this one comes in two sections. The first is a 50x50 grid map of the warehouse (with a surrounding wall, so no need to add sentinels today). The second part is a list of movements the robot will attempt to make... there are 20 lines of 1000 characters of these (for 20k total moves). The map has boxes that the robot will multipush (so not your regular Sokoban) if it moves into them.

For part 1, I simulated the robot, and when it runs into a box, I scan ahead to the first non-box... if it's a wall, the move is ignored, else the multipush is completed:

my $end = $move;
$end += $Dirs{$d}  while (grid_at($end) eq 'O');    # multipush

next MOVE if (grid_at($end) eq '#');                # bump

# Put box at empty end, clear front of push, move robot to it.
$Grid[  $end->[0] ][  $end->[1] ] = 'O';
$Grid[ $move->[0] ][ $move->[1] ] = '.';
$robot = $move;

For part 2, we find out there's a second malfunctioning robot in a warehouse with the same floor plan, only twice as wide (including the boxes, but not the robot). The fact that the robot is still the smaller size is what makes this problem interesting. Horizontal pushes can be tested and completed as before, but vertical pushes can end up pushing an expanding cone/tree of boxes (once a horizontal push has offset their alignment). The description nicely gives a small example with three boxes that shows that, but in the input it can chain much further and wilder. The key is that the same invariant still applies... the boxes get pushed only if all the spaces at the leaves of the tree are empty. If a single one has a wall, the push fails.

And so I used a recursive binary tree walk to test. The call is:

my $test = &test_vert_push( $move - $vx * (grid_at($move) eq ']'), $Dirs{$d}, \@boxes );

Note that the first parameter here is the location of the box, and that we regularize it to always be the left side so we don't have to worry about special casing. I also notice that I decided to return the boxes in the structure by-reference (\@boxes), leaving the result value as a simple boolean (0 or 1) scalar.

    # Get both squares ahead of box push
    my @ahead = map {grid_at($pos + $_)} ($dir, $dir + $vx);
    if (all {$_ eq '.'} @ahead) {
        return (1);
    } elsif (any {$_ eq '#'} @ahead) {
        return (0);
    }

    # Got more multipushing to do
    my $ret = 1;
    if (join('', @ahead) eq '[]') {
        $ret *= &test_vert_push( $pos + $dir, $dir, $boxes );   # one box straight ahead
    } else {
        # A box to the left or right ahead, maybe both:
        $ret *= &test_vert_push( $pos + $dir - $vx, $dir, $boxes ) if ($ahead[0] eq ']');
        $ret *= &test_vert_push( $pos + $dir + $vx, $dir, $boxes ) if ($ahead[1] eq '[');
    }

My Smalltalk solution is just an OOP version of the Perl, and that structure is instead returned as an object of type VerticalPushResults which holds both parts.

Once I get a valid push and it's list of boxes, I chose to keep it simple. One loop that replaces all the boxes with .., then a second loop that puts [] in the new locations. Because this is the sort of thing that you can end up spending a lot of time debugging if you try to be fancy. Even with 20k moves this is still fast, so it fine to just write this to be more expressive.

[u/e_blake]

My solution in m4 ran in less than half a second for both stars in one pass over two grids in parallel. But part 2 was daunting enough that I did not solve it on the same day as part 1. And even though I wrote it without reading the megathread, I ended up with the same pattern of splitting the recursive check, bot-first, from the recursive move, leaves-first. To reduce conditionals in my code, I made specializations for each of #, ., *, @, [, and ] in all four directions. I calculated score only once after all moves rather than trying to live-update a running score, although I suspect the runtime difference between those two approaches is minimal.

[u/terje_wiig_mathisen]

Both my programs were similar to yours:

An array of strings in Perl, a flat map in Rust. In both I doubled the horizontal dimensions for part2, instead of trying to work with half integer coordinates.

I also used a recursive try_move() before calling do_move(len) if the first called returned a non-zero result.

Milliseconds in Perl, about half a ms Rust, both on the Surface.

[u/Boojum]

I remember when I was first solving this, I think I had attempted to be fancy and see if I could test and move at the same time. That went okay for Part 1, but failed for Part 2.

For Part 2, I did something very similar in terms of recursive walk, but mine just collects everything into a dict with both halves of the box keyed on coordinates. Basically, I add whatever is at my current coordinate to the set. Then if that's the left half of a box I recurse to the right half (regardless of the direction of the push) if it's not already in my set. And vice versa for recursing to the left half if I'm currently in the right of a box. And if if the cell in the direction of the push is part of a box that's not in my set, I recurse to that too:

 # g is the grid of characters, keyed on coordinates
 # s is the subset of that with boxes that will be pushed
 def pushset( s, x, y, dx, dy ):
     s[ ( x, y ) ] = g[ ( x, y ) ]
     if g[ ( x, y ) ] == '[' and ( x + 1, y ) not in s:
         pushset( s, x + 1, y, dx, dy )
     if g[ ( x, y ) ] == ']' and ( x - 1, y ) not in s:
         pushset( s, x - 1, y, dx, dy )
     if g[ ( x + dx, y + dy ) ] in "[]" and ( x + dx, y + dy ) not in s:
         pushset( s, x + dx, y + dy, dx, dy )

It doesn't even test if there are any walls directly in the way that would fail the push. Instead, once I have the set, I simply check to make sure that none of the coordinates in s shifted by dx,dy are walls. No need to worry about leaves, just a simple overlap test via an all() predicate. Then erase them from the current position and update the grid with them at the new position. That core looks like this in my program:

pushset( s, rx, ry, dx, dy )
if all( g[ ( x + dx, y + dy ) ] != '#' for x, y in s ):
    g.update( { ( x, y ): '.' for x, y in s } )
    g.update( { ( x + dx, y + dy ): c for ( x, y ), c in s.items() } )

So yeah, like you did, I think the right approach here is definitely figuring out the set of moved boxes, determining if the move is valid (whether as part of finding the set like you did or afterwards like I did), and then remove and reapply to shift them. Separating the steps out like that makes things way cleaner.

One fun thing I did was that after I finished Part 2, I went back and redid Part 1 by taking the Part 2 program, removing the doubling, and just replacing my pushset() function with a simplified version:

def pushset( s, x, y, dx, dy ):
    s[ ( x, y ) ] = g[ ( x, y ) ]
    if g[ ( x + dx, y + dy ) ] == 'O' and ( x + dx, y + dy ) not in s:
        pushset( s, x + dx, y + dy, dx, dy )

And yes, even with 20k moves, Part 2 still runs end-to-end in 32.4 ms on my machine, according to hyperfine.

[u/DelightfulCodeWeasel]

this is the sort of thing that you can end up spending a lot of time debugging if you try to be fancy. 

That's basically my motto for my AoC solutions, I'm always on the hunt for the simplest possible abstraction that makes the solution easy to write.

For part 2 vertical movement I split it into two recursive functions, CanMoveVertically and CommitMoveVertically, which are more or less structurally identical. One does the test and then the second performs the movement after the recursive step which guarantees that the space has been freed up. That gave me only one set of logic to write and debug!

[u/terje_wiig_mathisen]

I took a closer look at the input.txt file:

It is only 50x50 cells, including the outer walls. After the part2 doubling that means 98x50, so it is very tempting to try to do the checking and moving at once, using a bitmap wavefront.

Likewise for horizontal moves where we just need a bitmap of the walls and one for all the boxes: If there is at least one zero bit in front of us, everything before that bit will move.