Advent of Code 2024-Day 15: Warehouse Woes
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:
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 :)
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.
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:
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.
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.