Advent of Code 2024, Day 15

This is Sokoban! If you’ve not played Sokoban back in ye olde days of computing, I’m talking early 1990s, then this reference flies over your head. You have a room of some shape, a bunch of boxes, you’re a little guy, and you need to move the boxes into a specific target area. You can only push the boxes, and if they’re against a wall, you can’t push them any more.

Found an online Sokoban page:

Sokoban - Original & Extra - #1

Play Sokoban online and solve more than 7500 levels : Original & Extra - #1

SokobanSokoban

And the code for today’s solution:

adventofcode2024/day15 at main · javorszky/adventofcode2024

Contribute to javorszky/adventofcode2024 development by creating an account on GitHub.

GitHubjavorszky

Spoilers

Part 1

There wasn’t much complexity in part 1.

Gotta parse the map into a HashMap of Coordinates and Entity types. Gotta parse the string soup into Commands after joining the lines together.

Then it was a matter of actually executing all the commands. I figured because robot pushes boxes, boxes push other boxes, and everything stops if at the end of the chain we encounter a wall, or an empty space, I could collect all the actions that a command would do in a buffer as I go, and if I hit a wall, I can discard that buffer. If I don’t hit a wall, I can then execute every replacement in one go.

A replacement is basically just “at this coordinate, replace this entity with this other entity.” It always starts with “replace the robot with empty space on wherever the robot started.”

I ran what I thought was a half finished code on the example input, got correct result, so I ran it on my input, also got correct result, so yay ⭐! Part 2. After gym!

Part 2

Today is 18th December, I lost 3 days to this damn part 😆😭. And do you know what it was? A glorified off–by–one error.

There were a bunch of parts to it:

1. make the map W I D E. No problem, fairly straightforward, everything is doubled, unless it’s a robot, because @ becomes @., or a box, because O becomes []
2. do the push logic, as previously, again not a problem, for the most part
3. do this while the boxes push other boxes by their sides ☠️

So that third point gave me so much trouble. For context, it’s situations like this:

// Starting position, about to go down

##############
##....@.....##
##....[]....##
##...[][]...##
##..[][][]..##
##..........##
##############

If you push this one down, this is what you should get:

// Good, we want this

##############
##..........##
##....@.....##
##....[]....##
##...[][]...##
##..[][][]..##
##############

But due to some fancy logic, I always end up losing half a box somewhere so it looks like this:

// What I kept ending up with

##############
##..........##
##....@.....##
##....[]....##
##...[.[]...## <-- note the [. there
##..[][][]..##
##############

This is because when I’m pushing a box down, and I encounter its left side, I need to also push its right side. I don’t know whether the thing on the right to the robot, or another box part, also gets pushed down, so by default I replace that with an Empty space.

This results in situations where the same coordinate gets modified due to two different pushes, one of the replacements overwriting the other one.

In the end I decided to keep the replacements sorted by recursion depth, and if the replacing entity is not an Empty block, record that in a set of “I’ve already done this replacement”.

Recursion depth is due to the implementation of push. The rules are:

• robot pushes a thing. If that thing is a box, then box pushes a thing (depth +1)
• if thing is empty, we return the current list of replacements with Replacement{depth, coordinate, entity}
• once returned from a push, we merge those into our list, and return the merged vector
• if we encounter a wall, we return a None, so no replacements get done at all

Because the replacements is a vector, duplicate items might be present. That would cause the unwarranted overwrite.

Using the set I solve the problem of empty overwriting a non–empty

• if we’ve already replaced that coordinate, skip replacing it, whatever the new entity is
• if the replacing entity is not an empty space, then I add it to the set, and replace the tile
• next time an empty comes in for a coordinate that already had a replacement, it gets skipped
• if empty comes in for a coordinate that will be replaced later, it does not get added to the set, so the new replacement can take over

Luckily all other tests still pass. But also, a thousand lines of code. Granted most of it is commented out and inline comments anyways.

Don’t matter, ⭐⭐.

Spoiler photo by Tiago Ferreira on Unsplash