<jupyter_start><jupyter_text>Day 23: A* search- This puzzle can be solved with a straight-forward implementation of [A* search](https://en.wikipedia.org/wiki/A*_search_algorithm), by treating the different possible states of the burrow as a graph, and the edges are the costs to move from one state to another.Because this is A*, you need to define a _heuristic_ ($h()$) function to provide an estimated cost from that state to the completed goal state. This should be the _minimal_ cost. Mine increases the cost if an amphipod can't reach their side room directly due to other amphipods blocking their way, but only by one extra movement step; I found this to improve execution time slightly.I also implemented detection for _blocking_ states, where an amphipod sitting in the hallway blocks movement between side rooms. E.g. the following state is _deadlocked_ because the two pods in the hallway can't reach their respective side rooms:```plain...C.A.......BD  BDCA  ```while in the following situation, there is no point in moving anything to the right of the A amphipod, as it blocks everything to the left from moving to their rooms on the right. The moves on the right-hand side of the burrow are expensive, so it is worth postponing those until A no longer blocks the path through.```plain.....A......CBD  BDCA  ```By not generating states for deadlocked states and for cases where high-energy amphopods can't reach their side rooms, we can prune the search tree even further.I've hand-tuned my implementation as much as I could, but as this is Python, I can only _barely_ keep part 1 under 1 second. There are just too many states that must be generated and examined, even with the A* heuristic.<jupyter_code>from __future__ import annotations

from dataclasses import dataclass
from enum import IntEnum
from heapq import heappop, heappush
from itertools import count
from typing import Final, Iterator, TypeAlias


class Amphipod(IntEnum):
    a = 0
    b = 1
    c = 2
    d = 3

    def __bool__(self):
        # not False, even when 0
        return True

    def __init__(self, value):
        self.cost = 10 ** value


Pos: TypeAlias = Amphipod | None
SideRoom: TypeAlias = tuple[Pos, ...]
SideRooms: TypeAlias = tuple[SideRoom, SideRoom, SideRoom, SideRoom]
Hallway: TypeAlias = tuple[Pos, Pos, Pos, Pos, Pos, Pos, Pos]

# precalculated values for state generation and cost estimation.
# distances from hallway to each entrance to a side room
DISTANCES: Final[tuple[tuple[int, int, int, int]]] = (
    (3, 5, 7, 9),
    (2, 4, 6, 8),
    (2, 2, 4, 6),
    (4, 2, 2, 4),
    (6, 4, 2, 2),
    (8, 6, 4, 2),
    (9, 7, 5, 3),
)
# slices into the hall tuple that must be empty for an amphipod to move from
# hall index to sideroom or vice versa.
INTRA: Final[tuple[tuple[slice, slice, slice, slice]]] = (
    (slice(1, 2), slice(1, 3), slice(1, 4), slice(1, 5)),
    (slice(2, 2), slice(2, 3), slice(2, 4), slice(2, 5)),
    (slice(2, 2), slice(3, 3), slice(3, 4), slice(3, 5)),
    (slice(2, 3), slice(3, 3), slice(4, 4), slice(4, 5)),
    (slice(2, 4), slice(3, 4), slice(4, 4), slice(5, 5)),
    (slice(2, 5), slice(3, 5), slice(4, 5), slice(5, 5)),
    (slice(2, 6), slice(3, 6), slice(4, 6), slice(5, 6)),
)


@dataclass(frozen=True, slots=True)
class BurrowState:
    sides: SideRooms = (None, None) * 4
    hall: Hallway = (None,) * 7
    energy: int = 0

    @property
    def location(self) -> tuple[SideRooms, Hallway]:
        """The 'location' is the burrow state without the energy value"""
        return self.sides, self.hall

    @property
    def is_goal(self) -> bool:
        return all(p == i for i, s in enumerate(self.sides) for p in s)

    @classmethod
    def from_map(cls, maplines: str, _rem=dict.fromkeys((32, 35, 46))) -> BurrowState:
        """Read side-room state from input map"""
        # remove all spaces, # and . characters (ASCII 32, 35, 46), leaving just
        # the amphipod characters.
        sidechars = zip(*maplines.lower().translate(_rem).split())
        return cls(tuple(tuple(Amphipod[p] for p in side) for side in sidechars))

    def __str__(self) -> str:
        s = ({None: "."} | {p: p.name.upper() for p in Amphipod}).__getitem__
        hall = s(self.hall[0]) + ".".join(map(s, self.hall[1:-1])) + s(self.hall[-1])
        top, *rest = (f'  #{"#".join(map(s, l))}#' for l in zip(*self.sides))
        return "\n".join(
            [
                f"#############  {self.energy}\n#{hall}#\n##{top.strip()}##",
                *rest,
                "  #########",
            ]
        )

    @property
    def heuristic(self, _dist=DISTANCES, _intra=INTRA) -> int:
        """Estimated minimal cost to completion"""
        hall = self.hall
        return sum(  # cost from hall to sideroom + penalty for amphipods in the way
            p.cost * (ts[p] + sum(1 for q in hall[ii[p]] if q))
            for p, ts, ii in zip(hall, DISTANCES, INTRA)
            if p is not None
        ) + sum(  # move cost from side room to hallway
            (abs(pod - pos) * 2 + d + 1) * pos.cost
            for pod, side in zip(Amphipod, self.sides)
            for d, pos in enumerate(side, 1)
            # amphipod needs to move out if a) it's in the wrong side room or
            # b) a pod below it is in the wrong side room
            if pos and (pos is not pod or any(o is not pod for o in side[d:]))
        )

    def __iter__(self, _dist=DISTANCES, _intra=INTRA) -> Iterator[BurrowState]:
        """All possible burrow states reachable from this one"""
        sides, hall, energy, cls = self.sides, self.hall, self.energy, type(self)
        for i, pcd in enumerate(hall[2:4]):
            # is this state deadlocked? Happens if C or D block access to the A
            # or B side rooms and A or B block access to the corresponding C or
            # D side rooms. At i == 2, only A is blocked, at i == 3, A and B can
            # be blocked. If blocked by D, the other pod could sit at positions
            # i == 3 or i == 4, while at position 4 C would not be blocked.
            if (pcd and pcd >= Amphipod.c) and any(
                pab and pab <= i for pab in hall[i + 3 : 2 + pcd]
            ):
                return

        for i, (pos, dist, intra) in enumerate(zip(hall, _dist, _intra)):
            if pos:  # possible moves of an amphipod to their destination sideroom
                if any(hall[intra[pos]]):  # one or more spaces in-between are occupied.
                    continue
                side = sides[pos]
                if not {None, pos}.issuperset(side):
                    # there is still a misplaced amphipod in this side room
                    if (
                        1 < i < 5
                        and pos <= i - 2
                        and all(p and p > pos for side in sides[: i - 1] for p in side)
                    ):
                        # this amphipod is blocking access to all side rooms to
                        # the right that all amphipods to the left must travel
                        # to. States from the right-hand side of the burrow can
                        # be pruned until this situation is resolved.
                        return
                    continue
                # empty position before the top-most occupied position
                d = next((i for i, p in enumerate(side) if p), len(side)) - 1
                yield cls(
                    (*sides[:pos], (*side[:d], pos, *side[d + 1 :]), *sides[pos + 1 :]),
                    (*hall[:i], None, *hall[i + 1 :]),
                    energy + pos.cost * (dist[pos] + d),
                )
                continue

            # possible moves from side rooms to current hallway position
            for pod, side, dd, ii in zip(Amphipod, sides, dist, intra):
                if any(hall[ii]):  # one or more spaces in-between are occupied.
                    continue
                if {None, pod}.issuperset(side):
                    # all amphipods here are in their correct side room
                    continue
                # top-most occupied position in the side room
                d = next(i for i, p in enumerate(side) if p)
                pos, side = side[d], (*side[:d], None, *side[d + 1 :])
                yield cls(
                    (*sides[:pod], side, *sides[pod + 1 :]),
                    (*hall[:i], pos, *hall[i + 1 :]),
                    energy + pos.cost * (dd + d),
                )

    def solve(self) -> int:
        open, closed, costs, unique = {self}, set(), {self.location: 0}, count()
        pqueue = [(self.energy + self.heuristic, next(unique), self)]
        while open:
            node = heappop(pqueue)[-1]
            if node.is_goal:
                return node.energy

            open.remove(node)
            closed.add(node)
            for new in node:
                if new in closed or new in open:
                    continue
                loc, cost = new.location, new.energy
                if costs.get(loc, cost) < cost:
                    continue
                open.add(new)
                costs[loc] = cost
                heappush(pqueue, (cost + new.heuristic, next(unique), new))


test_map = """\
#############
#...........#
###B#C#B#D###
  #A#D#C#A#
  #########
"""
assert BurrowState.from_map(test_map).solve() == 12521

import aocd

burrow_map = aocd.get_data(day=23, year=2021)
print("Part 1:", BurrowState.from_map(burrow_map).solve())<jupyter_output>Part 1: 19019<jupyter_text>Part 2 - larger burrowFor part two, I only had to refactor part 1 slightly to allow for arbitrary-size side rooms. This time, there is no way to keep the execution time under 1 second, not in pure Python, not unless we can come up with more creative ways to prune the search tree (pruning deadlocks and blocked sides pruned the search by about 10%).Still, a runtime of under 3.5 seconds is not a bad result.<jupyter_code>def unfold_map(map_lines: str) -> str:
    return map_lines[:42] + "  #D#C#B#A#\n  #D#B#A#C#\n" + map_lines[42:]


assert BurrowState.from_map(unfold_map(test_map)).solve() == 44169

print("Part 2:", BurrowState.from_map(unfold_map(burrow_map)).solve())<jupyter_output>Part 2: 47533
{'fraction_non_alphanumeric': 0.11681693453547629, 'fraction_numerical': 0.01773814190513524, 'mean_word_length': 2.1970551378446115, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 17, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '579030', 'license': 'MIT', 'n_tokens_mistral': 3294, 'n_tokens_neox': 3023, 'n_words': 1217, 'path': '2021/Day 23.ipynb', 'repo_name': 'AwesomeGitHubRepos/adventofcode', 'size': '10204'}