2021-12-23 - Amphipod
(original .ipynb)
Day 23 puzzle input is the position of some amphipods inside some rooms and a little hallway connecting them all. Mine is here. Part 1 involves using some rules about where and when they can be moved to determine how many moves are required to return them to their proper room. Part 2 involves modifying the input by adding a couple more amphipods per-room and doing the same calculation.
Verdict: got the result in the end but P2's test eludes me, it's like 4k lower than expected :-/ Not super happy with the end result:
- there's a lot of repeated code (like inside
step()) - I don't parse the input, I just initialize a
dictdirectly - I store hallway places as
listand rooms as adict, and serialize to string when pushing the state to the priority queue and deserialize back when working on it. But actually the serialized representation is pretty workable as well as being compact + usable in the heapq. It's probably possible to make a couple of changes to eliminate the serialize/deserialize - There are plenty of optimizations to be had.
- No real need for two separate "completed" funcs tbh
Will come back to this one again.
from advent import listify
puzzle_input_str = open("puzzle_input/day23.txt").read()
test_input_str = """#############
#...........#
###B#C#B#D###
#A#D#C#A#
#########"""
@listify
def parse_input(input_str):
for line in input_str.split("\n"):
yield list(line)
amphipod_energy = {
"A": 1,
"B": 10,
"C": 100,
"D": 1000
}
test_rooms = {
"A": ["A","B"],
"B": ["D","C"],
"C": ["C","B"],
"D": ["A","D"]
}
puzzle_rooms = {
"A": ["D","B"],
"B": ["D","C"],
"C": ["A","C"],
"D": ["A","B"]
}
hallway_adjacent = {
"A":2,
"B":4,
"C":6,
"D":8
}
cannot_move_to = set(hallway_adjacent.values())
def can_move_to_hallway(hallway, from_pos, to_pos, transitional=False):
if from_pos == to_pos:
return True
if (not transitional) and (to_pos in cannot_move_to):
return False
if to_pos < 0 or to_pos > len(hallway)-1:
return False
pos_step = to_pos - from_pos
pos_step //= abs(pos_step)
for pos in range(from_pos+pos_step, to_pos+pos_step, pos_step):
if hallway[pos] != ".":
return False
return True
def can_move_to_room(rooms, room, amphipod, room_size):
room_contents = [a for a in rooms[room] if a != "."]
if room != amphipod:
return False
if len(room_contents) == room_size:
return False
if len(room_contents) > 0 and room_contents[-1] != amphipod:
return False
steps = room_size - len(room_contents)
return steps
def moves_from_hallway(amphipod, rooms, hallway, pos, room_size, transitional=False):
hallway_moves = []
room_moves = []
max_range = 9 + room_size
for move in range(-max_range, max_range, 1):
if move == 0:
continue
if transitional and can_move_to_hallway(hallway, pos, pos + move):
hallway_moves.append((pos + move, abs(move)))
for room, hallway_pos in hallway_adjacent.items():
if transitional:
pass
elif room != amphipod:
continue
else:
if can_move_to_hallway(hallway, pos, hallway_pos, True):
adjustment = abs(hallway_pos - pos)
if room_steps := can_move_to_room(rooms, room, amphipod, room_size):
room_moves.append((room, adjustment + room_steps))
return hallway_moves, room_moves
def moves_from_room(room, rooms, hallway, room_size):
if len(rooms[room]) == 0:
return [], []
pos = hallway_adjacent[room]
hallway_moves, room_moves = moves_from_hallway(rooms[room][-1], rooms, hallway, pos, room_size, True)
steps_out = room_size + 1 - len(rooms[room])
return [(p,s+steps_out) for p,s in hallway_moves], [(r,s+steps_out) for r,s in room_moves]
from heapq import heapify, heappush, heappop
from copy import deepcopy
def step(rooms, hallway, total_energy, room_size):
for room in rooms:
if is_room_completed(room, rooms[room], room_size):
continue
if len(rooms[room]) == 0:
continue
hallway_moves, room_moves = moves_from_room(room, rooms, hallway, room_size)
dbg_print(hallway_moves, room_moves)
for pos, steps in hallway_moves:
new_rooms = deepcopy(rooms)
amphipod = new_rooms[room].pop()
required_energy = steps * amphipod_energy[amphipod]
new_hallway = deepcopy(hallway)
new_hallway[pos] = amphipod
yield (total_energy + required_energy, new_hallway, new_rooms)
for new_room, new_steps in room_moves:
new_rooms = deepcopy(rooms)
new_hallway = deepcopy(hallway)
amphipod = new_rooms[room].pop()
required_energy = new_steps * amphipod_energy[amphipod]
new_rooms[new_room].append(amphipod)
yield (total_energy + required_energy, new_hallway, new_rooms)
for pos in range(len(hallway)):
amphipod = hallway[pos]
if amphipod == ".":
continue
hallway_moves, room_moves = moves_from_hallway(amphipod, rooms, hallway, pos, room_size)
dbg_print(hallway_moves, room_moves)
for new_pos, new_steps in hallway_moves:
required_energy = new_steps * amphipod_energy[amphipod]
new_rooms = deepcopy(rooms)
new_hallway = deepcopy(hallway)
new_hallway[new_pos] = amphipod
new_hallway[pos] = "."
yield (total_energy + required_energy, new_hallway, new_rooms)
for new_room, new_steps in room_moves:
required_energy = new_steps * amphipod_energy[amphipod]
new_rooms = deepcopy(rooms)
new_hallway = deepcopy(hallway)
new_rooms[new_room].append(amphipod)
new_hallway[pos] = "."
yield (total_energy + required_energy, new_hallway, new_rooms)
def serialize_state(hallway, rooms, room_size):
rooms_str = []
for _, room in rooms.items():
r = "".join(room)
rooms_str.append(r)
rooms_str.append((room_size - len(r)) * ".")
hallway_str = "".join(hallway)
rooms_str = "".join(rooms_str)
return f"{hallway_str}|{rooms_str}"
def deserialize_state(state, room_size):
hallway_str, rooms_str = state.split("|")
hallway = list(hallway_str)
rooms = {}
for i, r in enumerate("ABCD"):
room = []
for n in range(room_size):
amphipod = rooms_str[(room_size*i)+n]
if amphipod != ".":
room.append(amphipod)
else:
break
rooms[r] = room
return hallway,rooms
def is_room_completed(r, room, room_size):
good = 0
for a in room:
good += 1 if a == r else 0
return good == room_size
def completed_rooms(rooms):
good = 0
for r, room in rooms.items():
for a in room:
good += 1 if a == r else 0
return good
%%time
from pprint import pprint
from collections import defaultdict
from math import inf
def part_one(initial_rooms, quiet=False):
room_size = len(initial_rooms["A"])
previous_states = defaultdict(lambda:inf)
h = ["."] * 11
q = [(0, serialize_state(h, initial_rooms, room_size))]
heapify(q)
states = 0
while state := heappop(q):
states += 1
(energy, state) = state
hallway, rooms = deserialize_state(state, room_size)
if completed_rooms(rooms) == (4 * room_size):
return energy
if completed_rooms(rooms) == (4 * room_size) - 1:
if not quiet:
print(state, energy)
for new_energy, new_hallway, new_rooms in step(rooms, hallway, energy, room_size):
new_state = serialize_state(new_hallway, new_rooms, room_size)
if new_energy < previous_states[new_state]:
previous_states[new_state] = new_energy
heappush(q, (new_energy, new_state))
return energy
# assert 12521 == part_one(test_rooms, quiet=True)
print("part one:", part_one(puzzle_rooms))
...D.......|AABBCCD. 12053 .D.........|AABBCCD. 12057 .D.........|AABBCCD. 12367 D..........|AABBCCD. 13057 D..........|AABBCCD. 13367 ...D.......|AABBCCD. 14033 .....D.....|AABBCCD. 14053 .....D.....|AABBCCD. 14129 .D.........|AABBCCD. 14167 D..........|AABBCCD. 15167 .....D.....|AABBCCD. 16033 .......D...|AABBCCD. 16053 ...C.......|AABBC.DD 17969 .........B.|AAB.CCDD 17993 ..........B|AAB.CCDD 18001 ..........B|AAB.CCDD 18003 .........D.|AABBCCD. 18033 .......D...|AABBCCD. 18033 .B.........|AAB.CCDD 18037 B..........|AAB.CCDD 18039 .........A.|A.BBCCDD 18043 ..........A|A.BBCCDD 18044 .A.........|A.BBCCDD 18049 .B.........|AAB.CCDD 18049 .C.........|AABBC.DD 18049 A..........|A.BBCCDD 18050 ...........|AABBCCDD 18051 part one: 18051 CPU times: user 17.9 s, sys: 27.8 ms, total: 17.9 s Wall time: 18.2 s
%%time
test_rooms_2 = {
"A": ["A", "D", "D", "B"],
"B": ["D", "B", "C", "C"],
"C": ["C", "A", "B", "B"],
"D": ["A", "C", "A", "D"]
}
puzzle_rooms_2 = {
"A": ["D", "D", "D", "B"],
"B": ["D", "B", "C", "C"],
"C": ["A", "A", "B", "C"],
"D": ["A", "C", "A", "B"] # you're god damn right
}
def part_two(initial_rooms):
ans = part_one(initial_rooms)
print(ans)
return ans
# assert 44169 == part_two(test_rooms_2)
print("part two:", part_two(puzzle_rooms_2))
D..........|AAAABBBBCCCCDDD. 50061 ..........A|AAA.BBBBCCCCDDDD 50236 A..........|AAA.BBBBCCCCDDDD 50242 ...........|AAAABBBBCCCCDDDD 50245 50245 part two: 50245 CPU times: user 23 s, sys: 12 ms, total: 23 s Wall time: 23.2 s