This post captures notes on the standout problems for me in Advent of Code 2024. I’ll keep updating this post as I solve problems.

Last edit: 01/25/2025

Day 15 - Warehouse Woes Link to heading

Part 1 of this problem was not that hard to solve. Boxes above, below, left of and right of a robot cell were all in one line. The approach was to first make a set of all boxes adjacent to a robot, and in another step, move all the boxes in the direction indicated by the move code (v - down, ^ - up, < - left and > - right). cellsInDirection and moveCells do the major work here. Because boxes and robot are adjacent along the same vertical (column) or horizontal (row) axis, I could leverage these two generic routines for the two steps. The runtime for this part was 7ms on my MBP M3.

Part 2 turned out to be very challenging. After numerous false starts, I finally got an approach to work, that is essentially a Breath-first-search (BFS) algorithm to calculate boxes that are adjacent to a robot. Here’s how it works. Consider the following layout of the robot (@), walls (#) and boxes (horizontally adjacent cells with [ and ] respectively) -

  0 1 2 3 4 5
0 . # . . . .
1 . . @ . . . -- level 1
2 . . [ ] # . -- level 2
3 . [ ] [ ] . -- level 3
4 . . [ ] . . -- level 4
5 . [ ] [ ] . -- level 5
6 . . . . . . -- level 6

Let’s assume the move is v (move robot down). The BFS algorithm will be used to first figure out all the boxes that could potentially be moved down (see findAdjacentBoxesToMoveDown). These are boxes directly adjacent to the robot in the downwards direction (the single box in level 2), then boxes adjacent to that box in the row below (the two boxes on level 3), and so on till it terminates after adding the two boxes on level 5. BFS will determine that there are 6 boxes that can be moved down. Once the candidate boxes have been figured out, the next step is to determine individually whether each box can actually be moved or not, and if they can be, they are finally moved (see moveAdjacentBoxesDown).

Note, its not enough to just figure out whether the boxes in the last row can all be pushed down or not, its important to evaluate all of them. Two examples below show why - both with the same relative layout of robot and boxes but slightly different placements of walls. In the first one, notice the wall (X) at location (4, 1). That will prevent the box on the left at level 3 to move down. That in turn prevents the one box on level 2 to move, and that finally makes it impossible for the robot to move down. The other example shows how the wall at level 6 prevents the robot and box moves in the same way.

  0 1 2 3 4 5
0 . # . . . .
1 . . @ . . . -- level 1
2 . . [ ] # . -- level 2
3 . [ ] [ ] . -- level 3
4 . # [ ] . . -- level 4
5 . [ ] [ ] . -- level 5
6 . . . . . . -- level 6

  0 1 2 3 4 5
0 . # . . . .
1 . . @ . . . -- level 1
2 . . [ ] # . -- level 2
3 . [ ] [ ] . -- level 3
4 . . [ ] . . -- level 4
5 . [ ] [ ] . -- level 5
6 . . # . . . -- level 6

The logic for moving boxes up, works exactly the same way. The logic for moving boxes horizontally, left or right is different. Consider this layout -

  0 1 2 3 4 5 6 7
0 . . . . . . . .
1 . . @ [ ] [ ] .  
2 . . . . . . . .

Suppose the robot needs to move right (>). The algorithm would first compute the list of adjacent boxes to the right of the robot (see findAdjacentBoxesToRight). Here there are two boxes. Next, the algorithm will determine whether the box that is rightmost in the list (the one box on column 5 and 6), is able to move right or not (see this logic). Since (1, 7) is an empty cell, the box can. It’s then a simple matter of shifting all the boxes, and the robot to the right (see moveAdjacentBoxesRight). The algorithm works the same way for moving boxes to the left (move code <). An example below shows a case where a move is not possible, because the leftmost box is blocked.

  0 1 2 3 4 5 6 7
0 . . . . . . . .
1 # [ ] @ . . . .
2 . . . . . . . .

The runtime for the complete solution for part 2, disregarding the time taken to write the frames to disk, was 12ms on my MBP M3 (🎉). I think I have a fairly optimal solution here, though the code complexity is higher than for an average AoC solution till now. For part 2 it was not possible to develop common routines to determine candidate boxes to move, and to perform the move operation. If there was, it would have simplified the code and reduce the total loc.

I wanted to see part 2 in action so I decided to invest some time building a Python utility to animate this whole run for part 2. This program works by operating on grid frames (NxM matrix with all the warehouse characters in each cell) produced by the Java implementation. (writeFrameToFile) prints the grid frames to a file. The Python utility d15.py is used to produce the visualization from that file. It leverages the excellent Pygame toolkit to create the animation. It was enormous fun and immensely satisfying to see the algorithm in action!

Finally, here’s the complete animation for the robot moving boxes around for my problem input. Fair warning though, there are 20K frames (20K moves in the input), so the video is around 16 minutes long 😊.