Advent of Code 2024 - Day 15: Warehouse Woes

:: programming, python, puzzle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
from advent import parse, grid_to_hash

input1, input2 = parse(15, sep='\n\n')
lines          = str.split(input1,'\n')
instructions   = [ { '>' : 1, 'v' : 1j, '<' : -1, '^' : -1j }[c] for c in input2 if c != '\n' ]
gps            = lambda box: 100 * int(box.imag) + int(box.real)
is_box         = lambda c: c == 'O' or c == '[' or c == ']'

def push_boxes(grid, pos, dir, skip_recur=False, quiet=False):
    if not (quiet or push_boxes(grid, pos, dir, quiet=True)):
        return False

    box       = grid[pos]
    other_pos = None
    other_box = None

    if box == 'O' or dir == -1 or dir == 1:
        skip_recur = True
    elif box == '[':
        other_pos = pos + 1
        other_box = ']'
    else:
        other_pos = pos - 1
        other_box = '['

    if skip_recur or push_boxes(grid, other_pos, dir, True, quiet):
        next_pos = pos + dir
        next_box = grid.get(next_pos, None)

        if next_box is None or is_box(next_box) and push_boxes(grid, next_pos, dir, quiet=quiet):
            if not quiet:
                grid[next_pos] = box
                del grid[pos]
            return True

    return False

def move(grid, bot, dir):
    pos = bot + dir
    box = grid.get(pos, None)
    return pos if box is None or is_box(box) and push_boxes(grid, pos, dir) else bot

def solve(part):
    grid = part()
    bot  = [ pos for pos, val in grid.items() if val == '@' ][0]
    del grid[bot]

    for dir in instructions:
        bot = move(grid, bot, dir)

    return sum(gps(pos) for pos, val in grid.items() if val in ['[','O'])

# Parts ---------------------------------------------------------------------------------------

def part1():
    return grid_to_hash(lines, elem_filter=lambda c: c != '.')

def part2():
    expand_row = lambda line: [ c for sublist in [ { 'O' : [ '[', ']' ],
                                                     '@' : [ '@', '.' ],
                                                     '#' : [ '#', '#' ],
                                                     '.' : [ '.', '.' ] }[c] for c in line ] for c in sublist ]

    return grid_to_hash(lines, elem_filter=lambda c: c != '.', row_transform=expand_row)

# ---------------------------------------------------------------------------------------------

assert solve(part1) == 1497888
assert solve(part2) == 1522420

Parsing

We’re given two items in our input. A map of the warehouse, and a list of instructions. For example:

##########
#..O..O.O#
#......O.#
#.OO..O.O#
#..O@..O.#
#O#..O...#
#O..O..O.#
#.OO.O.OO#
#....O...#
##########

<vv>^<v^>v>^vv^v>v<>v^v<v<^vv<<<^><<><>>v<vvv<>^v^>^<<<><<v<<<v^vv^v>^
vvv<<^>^v^^><<>>><>^<<><^vv^^<>vvv<>><^^v>^>vv<>v<<<<v<^v>^<^^>>>^<v<v
><>vv>v^v^<>><>>>><^^>vv>v<^^^>>v^v^<^^>v^^>v^<^v>v<>>v^v^<v>v^^<^^vv<

I’d like to have a dict for the map, and a list of instructions. For the latter, I’ll convert the ASCII characters to a complex number for east, south, west or north:

1
2
3
 
input1, input2 = parse(15, sep='\n\n')
lines          = str.split(input1,'\n')
instructions   = [ { '>' : 1, 'v' : 1j, '<' : -1, '^' : -1j }[c] for c in input2 if c != '\n' ]

The warehouse map is the only thing unique to each part, so I’ll cover that later.

Prerequisites

Our first helper is a function to push boxes. We’ll do this recursively i.e. to push a box, we first push all the boxes beyond it, and lastly move the box we’re pushing. I initially solved each part separately, and then I refactored the push_boxes() function to work for both parts. For part 2, it’s helpful to know ahead of time if we’re able to push the boxes (otherwise, we’d have to implement an “undo” function to undo the changes we made in the failed attempt). I originally had a can_push_boxes() function, but I noticed it was extremely similar to the push_boxes() function, so I tweaked push_boxes() to do double duty. By passing in a quiet=True flag, it runs through the pushing logic without actually changing anything.

Another item of note is that for part we recur on both “halves” of the wider boxes, so I also added a flag, skip_recur so that when recurring on the “other” box, I don’t go back and forth forever :)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
def push_boxes(grid, pos, dir, skip_recur=False, quiet=False):
    if not (quiet or push_boxes(grid, pos, dir, quiet=True)):
        return False

    box       = grid[pos]
    other_pos = None
    other_box = None

    if box == 'O' or dir == -1 or dir == 1:
        skip_recur = True
    elif box == '[':
        other_pos = pos + 1
        other_box = ']'
    else:
        other_pos = pos - 1
        other_box = '['

    if skip_recur or push_boxes(grid, other_pos, dir, True, quiet):
        next_pos = pos + dir
        next_box = grid.get(next_pos, None)

        if next_box is None or is_box(next_box) and push_boxes(grid, next_pos, dir, quiet=quiet):
            if not quiet:
                grid[next_pos] = box
                del grid[pos]
            return True

    return False

Our next helper function is move(). This is pretty simple, we look at the next position, if it’s empty, we move to it. If it contains a box, and we successfully push the box, we also then move to the position.

1
2
3
4
 
def move(grid, bot, dir):
    pos = bot + dir
    box = grid.get(pos, None)
    return pos if box is None or is_box(box) and push_boxes(grid, pos, dir) else bot

Lastly, we have the solve() function. We compute the starting position of the bot, then remove it from the map (we’ll just keep track of its position separately). Then we process all the instructions, and return the sum of all the gps coordinates:

1
2
3
4
5
6
7
8
9
 
def solve(part):
    grid = part()
    bot  = [ pos for pos, val in grid.items() if val == '@' ][0]
    del grid[bot]

    for dir in instructions:
        bot = move(grid, bot, dir)

    return sum(gps(pos) for pos, val in grid.items() if val in ['[','O'])

Parts

With the above in place, we only need to define the parts, and they only differ in the map they return. For part 1, we return the map as is. For part 2, we first expand boxes, walls and empty spaces to make them twice as wide.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
 
def part1():
    return grid_to_hash(lines, elem_filter=lambda c: c != '.')

def part2():
    expand_row = lambda line: [ c for sublist in [ { 'O' : [ '[', ']' ],
                                                     '@' : [ '@', '.' ],
                                                     '#' : [ '#', '#' ],
                                                     '.' : [ '.', '.' ] }[c] for c in line ] for c in sublist ]

    return grid_to_hash(lines, elem_filter=lambda c: c != '.', row_transform=expand_row)

Conclusion

I enjoyed this puzzle. It took longer than I expected, but it often does :) I get a lot of gratification by trying to unify parts 1 and 2 as much as possible, and I’m pleased with that effort today.