commit 2f41fa16e2b71497ab2599939664efe08cff03ee
parent d838a5e4566e7bb71a52e17946fd296537608752
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date: Sat, 25 Dec 2021 08:51:52 -0500
Solution to day 23, part 1
Diffstat:
| A | day23_part1.py | | | 343 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 343 insertions(+), 0 deletions(-)
diff --git a/day23_part1.py b/day23_part1.py
@@ -0,0 +1,343 @@
+#!/usr/bin/env python
+"""Advent of Code 2021, day 23 (part 1): Amphipod
+Play a shrimp shuffling game"""
+
+# I think this is another problem that can be solved through graph search. The
+# tricky bit (IMO) is that I can't just enumerate all of the possible states
+# ahead of time and then plug them into SciPy or NetworkX and have them solve
+# the problem. No, I think it'll be "easiest" to solve the graph and figure out
+# states as we go. The next hard part is figuring out a _hashable_
+# representation of the state of the board. The example started off like this:
+#
+# #############
+# #...........#
+# ###B#C#B#D###
+# #A#D#C#A#
+# #########
+#
+# Another intermediate state looked like this:
+#
+# #############
+# #.....D.D.A.#
+# ###.#B#C#.###
+# #A#B#C#.#
+# #########
+#
+# There are 19 different spots through which an amphipod can pass (labeled 0 -
+# I below), although they can't "stop" in all of them:
+#
+# #############
+# #0123456789A#
+# ###B#D#F#H###
+# #C#E#G#I#
+# #########
+#
+# And additionally, there are 8 amphipods, 2 of each type, with the different
+# types having restrictions on which rooms they can enter and costs associated
+# with moving. So while there may be some real overhead in manipulating this
+# scheme, we can represent the state of the game using an 8-tuple that
+# specifies the location where each amphipod is currently standing.
+#
+# The next big implementation decision is how to handle move restrictions, and
+# I see two approaches: amphipods can either move to their final standing spot
+# in one "step" of the algorithm (at the cost of more complex pathfinding
+# logic), or they can take one step at a time, but extra logic can handle the
+# fact that amphipods are "frozen" in place in the hallway until they can
+# complete their move into their final room and can't stop in front of doors.
+# I'm going to try the first approach since it seems like a smaller search
+# problem. Basically, an amphipod can move from their starting room to one spot
+# in the hallway, and then move to their final room, so maybe Dijkstra's
+# algorithm would suffice; otherwise there are so many "low energy" moves to
+# explore before the type D amphipods would ever move that we'd need A*, which
+# means I'd need to implement a whole heuristic algorithm. The path-finding
+# seems worth it.
+
+from typing import Tuple, List, Union, Dict, Deque, NewType
+from heapq import heappush, heappop
+from collections import deque
+
+from utils import get_puzzle_input
+
+EXAMPLE_INPUT = \
+"""#############
+#...........#
+###B#C#B#D###
+ #A#D#C#A#
+ #########
+"""
+
+GameState = NewType(
+ 'GameState',
+ Tuple[int, int, int, int, int, int, int, int]
+)
+
+def parse_input(input_string: str) -> GameState:
+ """Given the puzzle input, return the initial state of the game"""
+ # This implementation assumes that all amphipods start in a room; it's
+ # unable to parse a game state with amphipods in the hallway
+ lines = input_string.rstrip('\n').split('\n')
+ state_list: List[Union[None, int]] = [None] * 8
+ for room_line in range(2):
+ amphipods = [2 * (ord(c) - ord('A')) \
+ for c in lines[2 + room_line].replace('#', '').replace(' ', '')]
+ for room_num, amphipod in enumerate(amphipods):
+ if state_list[amphipod] is not None:
+ amphipod += 1
+ state_list[amphipod] = room_line + 2 * room_num + 11
+ return GameState(tuple(state_list))
+
+# Because of my stubborn decision to represent the game state in an awkward
+# way, I need a bunch of little functions to help me actually make sense of the
+# state of the game.
+
+def valid_hall_locations() -> Tuple[int, ...]:
+ """Return all of the hall locations in which an amphipod can legally stop"""
+ return (0, 1, 3, 5, 7, 9, 10)
+
+def is_in_hall(location: int) -> bool:
+ """Returns `True` iff a location is in the hall"""
+ return location < 11
+
+def get_room(location: int) -> Union[None, int]:
+ """Return the room number of the given location, or `None` if it's the
+ hallway"""
+ if is_in_hall(location):
+ return None
+ return (location - 11) // 2
+
+def get_spot(location: int) -> Union[None, int]:
+ """Return the room spot number of the given location (0 at the top and 1
+ below it), or `None` if it's the hallway"""
+ if is_in_hall(location):
+ return None
+ return (location - 11) % 2
+
+def get_entrance(room: int) -> int:
+ """Return the location of the hallway spot immediately outside a room"""
+ return 2 + 2 * room
+
+def get_location(room: int, spot: int) -> int:
+ """Given a room and spot number, find the location"""
+ return 11 + room * 2 + spot
+
+def is_empty(location: int, game_state: GameState) -> bool:
+ """Just indicates whether a location is empty; nothing special"""
+ return location not in game_state
+
+def get_type(amphipod: int) -> int:
+ """There are 8 amphipods, but four types; this is useful because the type
+ ID is also the target room number"""
+ return amphipod // 2
+
+def get_amphipod(location: int, game_state: GameState) -> Union[None, int]:
+ """Return the amphipod ID of the one in the given location, and `None` if
+ there is none"""
+ if location not in game_state:
+ return None
+ return game_state.index(location)
+
+def get_energy_per_step(amphipod: int) -> int:
+ """Different types of amphipod consume different amounts of energy per
+ step"""
+ return (1, 10, 100, 1000)[get_type(amphipod)]
+
+def is_home(amphipod: int, game_state: GameState) -> bool:
+ """An amphipod is 'home' if it's in its final room and there are no
+ amphipods below it in the room that aren't also 'home'"""
+ room = get_room(game_state[amphipod])
+ # Now *this* is spaghetti code
+ if room is None:
+ return False
+ # Let's take a second to appreciate that tests for equality in Python work
+ # across object types, so this doesn't return None
+ if get_type(amphipod) == room:
+ spot = get_spot(game_state[amphipod])
+ assert spot is not None
+ if spot == 1:
+ return True
+ next_location = get_location(room, spot+1)
+ if is_empty(next_location, game_state):
+ # The amphipod in question is in the right room, but there's
+ # weirdly an empty spot below it?
+ return False
+ return is_home(game_state.index(next_location), game_state)
+ return False
+
+def everybody_home(game_state: GameState) -> bool:
+ """Return `True` iff every amphipod is in a home spot"""
+ return all(is_home(a, game_state) for a in range(len(game_state)))
+
+def is_blocked_in_room(amphipod: int, game_state: GameState) -> bool:
+ """An amphipod is 'blocked' if they are in a room and another amphipod is
+ above them in the room (they might not be able to move anywhere in the
+ hallway, this function doesn't address that)"""
+ room = get_room(game_state[amphipod])
+ if room is None:
+ return False
+ spot = get_spot(game_state[amphipod])
+ if spot == 0:
+ return False
+ return not is_empty(get_location(room, 0), game_state)
+
+def steps_between(from_location: int, to_location: int) -> int:
+ """Count the steps between a hall location and room location; one end must
+ be in a room and the other in the hallway"""
+ hall_location, room_location = sorted([from_location, to_location])
+ assert is_in_hall(hall_location) and not is_in_hall(room_location)
+ return abs(hall_location - get_entrance(get_room(room_location))) \
+ + get_spot(room_location) + 1
+
+def path_clear(from_location: int, to_location: int,
+ game_state: GameState) -> bool:
+ """Return `True` iff there are no amphipods blocking the way between one
+ hallway location and another"""
+ # We allow an amphipod to be in the _from_ location, but not in the _to_
+ # location (nor in any intermediate location)
+ assert is_in_hall(from_location) and is_in_hall(to_location)
+ if from_location == to_location:
+ return False
+ if from_location < to_location:
+ test_range = range(from_location+1, to_location+1)
+ else:
+ test_range = range(to_location, from_location)
+ return not any(i in game_state for i in test_range)
+
+def make_state(game_state: GameState, amphipod: int,
+ new_location: int) -> GameState:
+ """Return a new state where the selected amphipod is in the given
+ location"""
+ game_state_list = list(game_state)
+ game_state_list[amphipod] = new_location
+ return GameState(tuple(game_state_list))
+
+# End of various helper functions. Next we're going to implement a version of
+# Dijkstra's algorithm (that doesn't require the enumeration of every possible
+# game state--which are the nodes in our graph).
+#
+# I'm going to use Python's built-in heap helpers and implement a version of a
+# priority queue to support the algorithm. Normally, one of the trickiest
+# operations in a heap-based priority queue is "removing" or "updating" entries
+# from the queue (usually this is achieved by marking them as 'removed' somehow
+# but otherwise leaving them in the queue). However, since queue entries are
+# only being updated when a new distance to a node is *lower* than the previous
+# one, that means anything that would be otherwise be removed/updated will
+# appear as "already visited" when it's popped off the queue. In other words,
+# as long as we don't consider states that have already been visited, we don't
+# need to worry about removing/updating anything in the heap.
+#
+# In addition to the heap, we'll use a dictionary to quickly look up the
+# current estimate of the minimum distance to a given node, and a set to keep
+# track of visited nodes. Everything is built into Python.
+
+def list_reachable_states(game_state: GameState) -> List[Tuple[GameState, int]]:
+ """Return a list for every (legal) game state that can be reached from the
+ current one, as a tuple containing the state itself and the energy that
+ would be required to move there"""
+ # This function, and not the simple implementation of Dijkstra's algorithm,
+ # is the meat of this solution, since there's a lot of tricky logic to
+ # figure out which amphipods can move and where they can move to. This
+ # finds all of the nodes connected to the current node in the graph.
+ reachable_states = []
+ for amphipod, location in enumerate(game_state):
+ amphipod_type = get_type(amphipod)
+ amphipod_locations = []
+ if is_in_hall(location):
+ # The only valid locations for a hallway amphipod to go to are its
+ # home room, and then only if it's empty or only occupied by
+ # amphipods of the same type.
+ if path_clear(location, get_entrance(amphipod_type), game_state):
+ for spot in (1, 0):
+ spot_location = get_location(amphipod_type, spot)
+ spot_amphipod = get_amphipod(spot_location, game_state)
+ if spot_amphipod is None:
+ amphipod_locations = [spot_location]
+ break
+ if get_type(spot_amphipod) != amphipod_type:
+ # The wrong type of amphipod is in this room so our guy
+ # can't enter it
+ break
+ elif not is_home(amphipod, game_state) \
+ and not is_blocked_in_room(amphipod, game_state):
+ # If the amphipod is in a room (that's not its home), then the only
+ # valid location is somewhere in the hallway.
+ current_room_entrance = get_entrance(get_room(location))
+ amphipod_locations = [l for l in valid_hall_locations() \
+ if path_clear(current_room_entrance, l,
+ game_state)]
+ # else: pass
+ for new_location in amphipod_locations:
+ reachable_states.append((
+ make_state(game_state, amphipod, new_location),
+ get_energy_per_step(amphipod) \
+ * steps_between(location, new_location)
+ ))
+ return reachable_states
+
+def reconstruct_path(start_state: GameState, final_state: GameState,
+ best_parent: Dict[GameState, GameState]) -> Deque[GameState]:
+ """Return the step-by-step solution to the problem"""
+ # I didn't need to implement this to solve the puzzle, but I did to debug
+ # my solution. :(
+ current_state = final_state
+ # Honestly a deque is overkill for this but I didn't use any for AoC and I
+ # wanted to appendleft so bad
+ path = deque([current_state])
+ while current_state != start_state:
+ current_state = best_parent[current_state]
+ path.appendleft(current_state)
+ return path
+
+def find_lowest_energy_use(start_state: GameState) -> Tuple[GameState, int,
+ Deque[GameState]]:
+ """Use Dijkstra's algorithm to find the lowest energy use to get all the
+ amphipods from the starting game state to a completed game state"""
+ priority_queue: List[Tuple[int, GameState]] = []
+ visited_states = set()
+ best_distance: Dict[GameState, int] = {}
+ best_parent = {}
+
+ (energy_to_current_state, current_state) = (0, start_state)
+
+ while not everybody_home(current_state):
+ # One of the ways this departs from a usual graph traversal is that
+ # there are multiple "goal nodes" (game states). Any state that has
+ # every amphipod in its home location will do, and there's no point in
+ # enumerating them if we terminate the search once we find one.
+ visited_states.add(current_state)
+
+ # For each amphipod that can move, find all the states that are
+ # reachable from the current one. Add newly discovered nodes, or better
+ # than previously seen energy usage, to the queue.
+ for reachable_state, energy_between in list_reachable_states(current_state):
+ energy_to_reachable_state = energy_to_current_state \
+ + energy_between
+ visit_neighbor = reachable_state not in visited_states and \
+ (reachable_state not in best_distance or \
+ best_distance[reachable_state] > energy_to_reachable_state)
+ if visit_neighbor:
+ heappush(priority_queue, (energy_to_reachable_state, reachable_state))
+ best_distance[reachable_state] = energy_to_reachable_state
+ best_parent[reachable_state] = current_state
+
+ # Select the next lowest-energy state to visit next. The heap will
+ # become full of longer paths to various states that we've already
+ # visited, but we can skip past them quickly.
+ (energy_to_current_state, current_state) = heappop(priority_queue)
+ while current_state in visited_states:
+ (energy_to_current_state, current_state) = heappop(priority_queue)
+
+ return (current_state, energy_to_current_state,
+ reconstruct_path(start_state, current_state, best_parent))
+
+def solve_puzzle(input_string: str) -> int:
+ """Return the numeric solution to the puzzle"""
+ return find_lowest_energy_use(parse_input(input_string))[1]
+
+def main() -> None:
+ """Run when the file is called as a script"""
+ assert solve_puzzle(EXAMPLE_INPUT) == 12521
+ print("Lowest energy use:",
+ solve_puzzle(get_puzzle_input(23)))
+
+if __name__ == "__main__":
+ main()
