Warehouse Woes

Advent of Code 2024 Day 15

Part 1

Oh, cool: Sokoban!

It's a genre of puzzle games involving precise movements that eventually position objects on designated cells in a maze-like grid.

The fun part is in figuring out the precise movements.

Here, the movements are given in the input.

The fun part, then, is simulating those movements in an algorithm.

The main difference between typical Sokoban rules and this is:

• In Sokoban, an object can't move if it is adjacent to an object in the direction of movement
• In this puzzle, however, the only thing preventing movement is a wall; otherwise, moving an object into another will move all touching objects one space in the direction of movement

Considering all scenarios for movement

Let's see, there's...

Onto an empty space
..@..

>

Onto a wall
..@##

>

Onto an object next to an empty space
..@O.

>

Onto an object next to a wall
..@O#

>

Onto an object next to an object
..@OO

>

Onto an object next to an object next to an empty space
.@OO.

>

Onto an object next to an object next to a wall
.@OO#

>

Onto an object next to an object next to an object
.@OOO

>

Hmm, I'm detecting a pattern for when the robot is next to an object:

Continue checking adjacent cells in that movement direction
Until the first non-object character
If it is an empty cell
  Move all visited objects by one cell toward the current direction
Else if it is a wall
  Don't move any objects

So, three scenarios:

1. Empty cell? Swap places with it
2. Wall? Stay put.
3. Object? Initiate a loop...

...For each next cell:

1. Empty cell? Shift all previous cells by one
2. Wall? Change nothing
3. Object? Loop again

I think I understand how this part of my algorithm should work.

What about the swapping of cell contents, though?

Especially when I have to shift several objects by one cell?

Stepping through a sample shift

Imagine my program is processing this state:

#...@OOOOO.# 

>

I want the next state to look like this:

#....@OOOOO# 

What will it take to accomplish that?

I think what I need to do is:

Track current position
Track next cell position
While next cell contains an object
  Adjust appropriate axis by one
If next cell is empty
  Do for i from current position to starting position
    Update grid cell contents

Wait wait wait. It doesn't have to be quite that complicated.

Putting both states side-by-side:

#...@OOOOO.# 
#....@OOOOO# 

Only three cells changed:

1. @ became empty
2. The first adjacent cell became @
3. The empty cell became O

I think I just need to worry about the book ends in scenarios involving one or more objects and an empty-space end.

That should make things a bit simpler, right?

Starting to write my program

Splitting the input, transforming string into grid, consolidating the instruction strings, and "geolocating" the robot:

let [grid, dirs] = input.split('\n\n')
dirs = dirs.replaceAll('\n', '')
grid = grid.split('\n').map(str => str.split(''))
let robot = null
for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
        if (grid[r][c] == '@') {
            robot = [r, c]
            grid[r][c] = '.'
        }
    }
}

The map of moves and relative coordinates:

let moves = {
    ">": [0,1],
    "<": [0,-1],
    "v": [1,0],
    "^": [-1,0]
}

For each instruction:

• Look-up the relative coordinate for each subsequent move
• Calculate the next move
• Re-calculate each next move as long as it is an object
• Stop once an empty slot or wall is reached

dirs.forEach(move => {
    let dir = moves[move]
    let next = [robot[0] + dir[0], robot[1] + dir[1]]
    while (grid[next[0]][next[1]] == "O") {
        next = [next[0] + dir[0], next[1] + dir[1]]
    }
    switch (grid[next[0]][next[1]]) {
        case ".":
            break;
        case "#":
            break;
    }
})

And now for the three swaps.

1. Update the robot's position by one cell
2. Update the grid so the cell occupied by the robot is empty
3. Update the grid so the first empty cell after any/all objects is now an object

        case ".":
            robot = [robot[0] + dir[0], robot[1] + dir[1]]
            grid[robot[0]][robot[1]] = "."
            grid[next[0]][next[1]] = "O"
            break;

Running, Wondering, Struggling, Debugging, A-ha!ing

I ran my program in saw an end grid state I wasn't expecting.

So I added statements to print the grid after instruction.

Within a few steps, the grid was getting messed up.

What was happening?

It was messing up on the first box move, where one box is moved right.

The robot was putting a box behind itself somehow.

...

Or was it?

Turns out, I wasn't accounting for scenarios where the next cell's contents are empty. I was jumping straight to cells containing objects!

With that fixed, my updated forEach looks like this:

dirs.forEach(move => {
    let dir = moves[move]
    let next = [robot[0] + dir[0], robot[1] + dir[1]]
    if (grid[next[0]][next[1]] == ".") {
        robot = next.slice()
    } else {
        while (grid[next[0]][next[1]] == "O") {
            next = [next[0] + dir[0], next[1] + dir[1]]
        }
        switch (grid[next[0]][next[1]]) {
            case ".":
                robot = [robot[0] + dir[0], robot[1] + dir[1]]
                grid[robot[0]][robot[1]] = "."
                grid[next[0]][next[1]] = "O"
                break;
            case "#":
                break;
        }    
    }
})

With logging statements added, I see the grid I expect after the instructions are processed.

Yay!

Fingers crossed

Will I see the same result using the larger example input?

Yes! Awesome!

How about using my puzzle input?

Well, boxes appear to have been moved around.

I guess I have to trust that the robot and boxes moved correctly.

That is, unless the eventual answer I submit is wrong.

Tallying up the GPS scores

Now for the easy part:

• Use each box's array indices to generate a score
• Sum all scores to generate an answer

Here's my GPS-calculating algorithm:

grid.reduce((total, curr, row) => {
    let score = curr.reduce((sum, cell, col) => {
        if (cell == "O") {
            sum += ((row * 100) + col)
        }
        return sum
    }, 0)
    return total += score
}, 0)

Checking for accuracy

Running it on the example input generates...

...the correct answer!

Running it on my puzzle input generates...

...the correct answer!!!!

Woohoo!!!

That was really fun!

What twist could Part 2 have in store?

Part 2

Quite the wrench: two tiles, one box

My head keeps spinning over all the scenarios where boxes down the line don't line up perfectly and must move.

It feels beyond the realm of conditional logic to effectively account for it all.

It's certainly beyond my level of patience, let alone technical ability.

So - sadly - I'm not even going to attempt Part 2.

It just doesn't feel worth more time.

I'm thrilled with having earned one gold star.

But gosh, the Part 2 puzzles this year are fierce!

Bring on another day!