Solution to the 15th problem

The problem basically requires to execute a sequence of movements into a map. The map contains empty cells, boxes and walls. The movements are executed with following these rules:

• The player can freely move into any empty space.
• If the player has to move into a box, the box will be shifted into the same direction if there's an empty space after that position. However, if multiple boxes are aligned, the player would move as many boxes as required. If there's a wall after all the boxes, the boxes cannot be shifter and the player won't move.
• If there's a wall, the player won't be able to move.

Parsing the map and executing the movements taking into account the rules is enough to get over the first problem. The second part is a bit more tricky as the initial map is extended. All parsed positions from the map are duplicated, meaning that boxes take up two spaces. This makes vertical movements more tricky, as a box may partially be in contact with another box. In order to solve this, instead of finding the first empty vertical space, we will find them with a triangular approach. The way I opted to solve it was to check if all boxes that were in contact could be moved. Unless they were all able, no movement would be made. The drawback about this approach is that you iterate twice (once for the search and a second time for the movement). Despite having a big map, the solution is really fast.

» cargo build -p aoc-24 --release && hyperfine ./target/release/aoc-24 -N --warmup 5
Finished `release` profile [optimized] target(s) in 0.05s
Benchmark 1: ./target/release/aoc-24
Time (mean ± σ):       4.9 ms ±   0.6 ms    [User: 1.5 ms, System: 0.8 ms]
Range (min … max):     4.1 ms …   8.6 ms    604 runs

• Code for this solution: d15.rs
• Problem statement