2024 day 23.

src/holt59/aoc/2024/day18.py

@@ -1,7 +1,58 @@
 from typing import Any, Iterator
 
 from ..base import BaseSolver
+from ..tools import graphs
 
 
 class Solver(BaseSolver):
-    def solve(self, input: str) -> Iterator[Any]: ...
+    def print_grid(self, grid: list[tuple[int, int]], n_rows: int, n_cols: int):
+        values = set(grid)
+        if self.files:
+            self.files.create(
+                "graph.txt",
+                "\n".join(
+                    "".join(
+                        "#" if (row, col) in values else "." for col in range(n_cols)
+                    )
+                    for row in range(n_rows)
+                ).encode(),
+                text=True,
+            )
+        else:
+            for row in range(n_rows):
+                self.logger.info(
+                    "".join(
+                        "#" if (row, col) in values else "." for col in range(n_cols)
+                    )
+                )
+
+    def dijkstra(self, corrupted: list[tuple[int, int]], n_rows: int, n_cols: int):
+        return graphs.dijkstra(
+            (0, 0),
+            (n_rows - 1, n_cols - 1),
+            graphs.make_neighbors_grid_fn(n_rows, n_cols, set(corrupted)),
+        )
+
+    def solve(self, input: str) -> Iterator[Any]:
+        values = [
+            (int(p[0]), int(p[1])) for r in input.splitlines() if (p := r.split(","))
+        ]
+
+        _is_test = len(values) < 100
+
+        n_rows, n_cols, n_bytes_p1 = (7, 7, 12) if _is_test else (71, 71, 1024)
+
+        bytes_p1 = values[:n_bytes_p1]
+        self.print_grid(bytes_p1, n_rows, n_cols)
+
+        path_p1, cost_p1 = self.dijkstra(bytes_p1, n_rows, n_cols) or ((), -1)
+        yield cost_p1
+
+        path = path_p1
+        for b in range(n_bytes_p1, len(values)):
+            if values[b] not in path:
+                continue
+            path, _ = self.dijkstra(values[: b + 1], n_rows, n_cols) or (None, -1)
+            if path is None:
+                yield ",".join(map(str, values[b]))
+                break

src/holt59/aoc/2024/day19.py

@@ -1,7 +1,42 @@
+from functools import cache
 from typing import Any, Iterator
 
 from ..base import BaseSolver
 
 
+@cache
+def is_valid(design: str, towels: tuple[str, ...]) -> bool:
+    if not design:
+        return True
+
+    return any(
+        design.startswith(towel) and is_valid(design[len(towel) :], towels)
+        for towel in towels
+    )
+
+
+@cache
+def count_valid(design: str, towels: tuple[str, ...]) -> int:
+    if not design:
+        return 1
+
+    return sum(
+        design.startswith(towel) and count_valid(design[len(towel) :], towels)
+        for towel in towels
+    )
+
+
 class Solver(BaseSolver):
-    def solve(self, input: str) -> Iterator[Any]: ...
+    def solve(self, input: str) -> Iterator[Any]:
+        towels_s, designs_s = input.split("\n\n")
+
+        towels = tuple(s.strip() for s in towels_s.split(","))
+
+        designs = [
+            design
+            for design in self.progress.wrap(designs_s.splitlines())
+            if is_valid(design, towels)
+        ]
+
+        yield len(designs)
+        yield sum(count_valid(design, towels) for design in self.progress.wrap(designs))

src/holt59/aoc/2024/day20.py

@@ -1,7 +1,95 @@
-from typing import Any, Iterator
+import itertools
+from collections import Counter
+from typing import Any, Callable, Iterable, Iterator, Sequence, TypeAlias
 
 from ..base import BaseSolver
+from ..tools.graphs import dijkstra, make_neighbors_grid_fn
+
+Node: TypeAlias = tuple[int, int]
+
+
+def make_neighbors_fn(grid: list[str], cheat_length: int):
+    n_rows, n_cols = len(grid), len(grid[0])
+
+    def _fn(node: Node):
+        row, col = node
+        return (
+            ((row_n, col_n), abs(row_n - row) + abs(col_n - col))
+            for row_d in range(-cheat_length, cheat_length + 1)
+            for col_d in range(
+                -cheat_length + abs(row_d), cheat_length - abs(row_d) + 1
+            )
+            if 0 <= (row_n := row + row_d) < n_rows
+            and 0 <= (col_n := col + col_d) < n_cols
+            and grid[row_n][col_n] != "#"
+        )
+
+    return _fn
 
 
 class Solver(BaseSolver):
-    def solve(self, input: str) -> Iterator[Any]: ...
+    def find_cheats(
+        self,
+        path: Sequence[Node],
+        cost: float,
+        costs_to_target: dict[Node, float],
+        neighbors_fn: Callable[[Node], Iterable[tuple[Node, float]]],
+    ):
+        cheats: dict[tuple[tuple[int, int], tuple[int, int]], float] = {}
+
+        for i_node, node in enumerate(self.progress.wrap(path)):
+            for reach_node, reach_cost in neighbors_fn(node):
+                n_cost = (
+                    i_node + reach_cost + costs_to_target.get(reach_node, float("inf"))
+                )
+                if n_cost < cost:
+                    cheats[node, reach_node] = cost - n_cost
+
+        return cheats
+
+    def solve(self, input: str) -> Iterator[Any]:
+        grid = input.splitlines()
+        n_rows, n_cols = len(grid), len(grid[0])
+        start = next(
+            (i, j) for i in range(n_rows) for j in range(n_cols) if grid[i][j] == "S"
+        )
+        target = next(
+            (i, j) for i in range(n_rows) for j in range(n_cols) if grid[i][j] == "E"
+        )
+
+        reachable = dijkstra(
+            target,
+            None,
+            make_neighbors_grid_fn(
+                n_rows,
+                n_cols,
+                excluded=(
+                    (i, j)
+                    for i in range(n_rows)
+                    for j in range(n_cols)
+                    if grid[i][j] == "#"
+                ),
+            ),
+        )
+
+        # note: path is inverted here
+        path, cost = reachable[start]
+        costs_to_target = {k: c for k, (_, c) in reachable.items()}
+
+        self.logger.info(f"found past from start to target with cost {cost}")
+
+        for cheat_length in (2, 20):
+            cheats = self.find_cheats(
+                list(reversed(path)),
+                cost,
+                costs_to_target,
+                make_neighbors_fn(grid, cheat_length),
+            )
+
+            for saving, count in sorted(Counter(cheats.values()).items()):
+                self.logger.debug(
+                    f"There are {count} cheats that save {saving} picoseconds."
+                )
+
+            target_saving = 100 if len(grid) > 20 else 50
+            yield sum(saving >= target_saving for saving in cheats.values())

src/holt59/aoc/2024/day21.py

@@ -1,7 +1,121 @@
-from typing import Any, Iterator
+import heapq
+from dataclasses import dataclass
+from typing import Any, Iterator, Literal, Sequence, TypeAlias, cast
 
 from ..base import BaseSolver
 
+Action: TypeAlias = Literal[">", "<", "v", "^", "A"]
+
+NUM_PAD = ((7, 8, 9), (4, 5, 6), (1, 2, 3), (None, 0, "A"))
+MOV_PAD: tuple[tuple[Action | None, ...], ...] = ((None, "^", "A"), ("<", "v", ">"))
+
+
+@dataclass(frozen=True, order=True)
+class Node:
+    robot_1: tuple[int, int] = (0, 2)
+    robot_2: tuple[int, int] = (0, 2)
+    robot_3: tuple[int, int] = (3, 2)
+
+    code: str = ""
+
+
+def apply_action(
+    robot: tuple[int, int],
+    action: Action,
+    pad: tuple[tuple[int | str | None, ...], ...],
+):
+    d_row, d_col = {"^": (-1, 0), "v": (1, 0), ">": (0, 1), "<": (0, -1)}[action]
+    row, col = robot[0] + d_row, robot[1] + d_col
+
+    if 0 <= row < len(pad) and 0 <= col < len(pad[row]) and pad[row][col] is not None:
+        return (row, col)
+
+    return None
+
+
+def create_node(node: Node, action: Action) -> Node | None:
+    # main pad moves -> move first robot
+    if action != "A":
+        robot = apply_action(node.robot_1, action, MOV_PAD)
+        if robot is not None:
+            return Node(
+                robot_1=robot,
+                robot_2=node.robot_2,
+                robot_3=node.robot_3,
+                code=node.code,
+            )
+
+        return None
+
+    # activate pad 1 -> action on robot 1
+    robot_1_action = MOV_PAD[node.robot_1[0]][node.robot_1[1]]
+    assert robot_1_action is not None
+
+    if robot_1_action != "A":
+        robot2 = apply_action(node.robot_2, robot_1_action, MOV_PAD)
+        if robot2 is not None:
+            return Node(
+                robot_1=node.robot_1,
+                robot_2=robot2,
+                robot_3=node.robot_3,
+                code=node.code,
+            )
+        return None
+
+    # activate pad 2 -> action on robot 2
+    robot_2_action = MOV_PAD[node.robot_2[0]][node.robot_2[1]]
+    assert robot_2_action is not None
+
+    if robot_2_action != "A":
+        robot3 = apply_action(node.robot_3, robot_2_action, NUM_PAD)
+        if robot3 is not None:
+            return Node(
+                robot_1=node.robot_1,
+                robot_2=node.robot_2,
+                robot_3=robot3,
+                code=node.code,
+            )
+        return None
+
+    value = NUM_PAD[node.robot_3[0]][node.robot_3[1]]
+    assert value is not None
+    return Node(
+        robot_1=node.robot_1,
+        robot_2=node.robot_2,
+        robot_3=node.robot_3,
+        code=node.code + str(value),
+    )
+
 
 class Solver(BaseSolver):
-    def solve(self, input: str) -> Iterator[Any]: ...
+    def dijkstra_for_code(self, target: str):
+        queue: list[tuple[float, Node, tuple[str, ...]]] = [(0, Node(), ())]
+        preds: dict[Node, tuple[str, ...]] = {}
+
+        while queue:
+            dis, node, path = heapq.heappop(queue)
+
+            if not target.startswith(node.code):
+                continue
+
+            if node in preds:
+                continue
+
+            preds[node] = path
+
+            if node.code == target:
+                self.logger.info(f"found [{target}]: {''.join(path)} ({len(path)})")
+                return path
+
+            for action in cast(Sequence[Action], "A^v<>"):
+                node_2 = create_node(node, action)
+                if node_2:
+                    heapq.heappush(queue, (dis + 1, node_2, path + (action,)))
+
+        return None
+
+    def solve(self, input: str) -> Iterator[Any]:
+        yield sum(
+            len(self.dijkstra_for_code(code) or ()) * int(code[:-1], 10)
+            for code in input.splitlines()
+        )

src/holt59/aoc/2024/day22.py

@@ -3,5 +3,57 @@ from typing import Any, Iterator
 from ..base import BaseSolver
 
 
+def mix(secret: int, value: int) -> int:
+    return secret ^ value
+
+
+def prune(secret: int) -> int:
+    return secret % 16777216
+
+
+def next_number(secret: int) -> int:
+    # Calculate the result of multiplying the secret number by 64. Then, mix this
+    # result into the secret number. Finally, prune the secret number.
+    secret = prune(mix(secret, secret * 64))
+
+    # Calculate the result of dividing the secret number by 32. Round the result down
+    # to the nearest integer. Then, mix this result into the secret number. Finally,
+    # prune the secret number.
+    secret = prune(mix(secret, secret // 32))
+
+    # Calculate the result of multiplying the secret number by 2048. Then, mix this
+    # result into the secret number. Finally, prune the secret number.
+    secret = prune(mix(secret, secret * 2048))
+
+    return secret
+
+
 class Solver(BaseSolver):
-    def solve(self, input: str) -> Iterator[Any]: ...
+    def solve(self, input: str) -> Iterator[Any]:
+        starts = [int(r) for r in input.splitlines()]
+
+        ends: list[int] = []
+        prices: list[int] = [0 for _ in range(2**16)]
+
+        for secret in self.progress.wrap(starts):
+            checked: list[bool] = [False] * len(prices)
+            hashed: int = 0
+
+            for i in range(2000):
+                last = secret % 10
+                secret = next_number(secret)
+                next = secret % 10
+
+                hashed = ((hashed << 4) & 0xFFFF) | ((last - next) & 0xF)
+
+                if i >= 3 and not checked[hashed]:
+                    checked[hashed] = True
+                    prices[hashed] += next
+
+            ends.append(secret)
+
+        for start, end in zip(starts, ends, strict=True):
+            self.logger.info(f"{start}: {end}")
+
+        yield sum(ends)
+        yield max(prices)

src/holt59/aoc/2024/day23.py

@@ -1,7 +1,36 @@
+from collections import defaultdict
 from typing import Any, Iterator
 
 from ..base import BaseSolver
+from ..tools.graphs import iter_max_cliques
 
 
 class Solver(BaseSolver):
-    def solve(self, input: str) -> Iterator[Any]: ...
+    def solve(self, input: str) -> Iterator[Any]:
+        connections: dict[str, set[str]] = defaultdict(set)
+        for row in input.splitlines():
+            src, dst = row.split("-")
+            connections[src].add(dst)
+            connections[dst].add(src)
+
+        if self.files:
+            content = "graph G {\n"
+            for row in input.splitlines():
+                src, dst = row.split("-")
+                content += f"{src} -- {dst}\n"
+            content += "}"
+            self.files.create("graph.dot", content.encode(), False)
+
+        cliques: set[frozenset[str]] = set()
+
+        for node1, neighbors in connections.items():
+            for node2 in neighbors:
+                for node3 in connections[node2].intersection(neighbors):
+                    cliques.add(frozenset({node1, node2, node3}))
+
+        self.logger.info(f"found {len(cliques)} cliques of size 3")
+        yield sum(any(node.startswith("t") for node in clique) for clique in cliques)
+
+        # clique = max(nx.algorithms.clique.find_cliques(G), key=len)
+        clique = max(iter_max_cliques(connections), key=len)
+        yield ",".join(sorted(clique))

src/holt59/aoc/inputs/holt59/2024/day19.txt

@@ -0,0 +1,402 @@
+ggrru, ugu, gwgg, bwrw, bww, brg, brwu, ruugb, grggr, wrgbuug, bbbrbr, rgrrbrbw, gbwg, wuruug, gbgwbg, rgw, buu, ggbgb, rwg, gr, ggurggr, wruuwgrr, wbgg, gggrb, rgwuu, uuwww, bgrw, uuguubw, bbbrwu, ugurb, uwbggg, rurg, ubb, wrr, rbbbbg, gguuug, gbur, wb, bubbu, gbwru, bgg, ugg, bbrrg, wubr, bgwgbwgg, rguurb, bugu, wuww, urugr, bwb, wug, brr, u, rru, wwgbw, gwu, bw, ugrwggr, rgubuw, bbg, bwru, uwgbwu, gbrugg, rgub, rgbbuwwg, wwr, grw, rwggwwrw, bbbu, wr, wbwu, wwrbuu, rbbgwru, gur, buurr, ggbrg, gwg, wrg, urw, uubub, gwrgb, bbw, rrw, ugrurw, rubrw, bgb, bwgbwbw, guw, ur, wgrbu, bgu, rrrrbrw, uww, uuu, wuugbw, wwbugw, rwbr, ruwbr, uwu, wgrb, b, rrwugru, gwb, burw, rurb, rbrrbgu, uwgw, brubr, bwu, rbw, ugbu, gww, wwrb, wbgbrww, brrwgrg, rugug, grgrrb, wuubbgu, brub, rrwwwb, ugr, wbw, ruwgguu, wgw, rrwrg, bwbbrwbg, rggg, gbgrguw, rwgw, rbbgwbr, gub, rgrrg, wbgggu, bbbgww, ugb, rbbgr, wru, rubbuu, bggrbu, gbg, bgrgbb, wwrwugbg, rrgu, wrrubwu, wrbuu, rgug, bbu, wrww, wbb, wgrwu, bbrurru, wgrugwu, uuw, uggwg, rrbuwu, gruw, ubr, urgug, www, wgrwrrw, rruw, rbg, bbwu, brww, rbwbw, grgr, bgr, wgwwu, wur, gubu, rrubgg, wbrurbb, ugub, wrrr, gbbr, wwubu, uwwbuw, wuu, rgb, bbr, rbrbuwg, urwb, gg, grug, br, wwguuwb, wu, ruu, guuwrw, wgb, gbr, wgggug, rw, brggww, wrgrw, guggub, gbbrug, gbbrb, bugrg, bwr, gwwg, wwbbrggw, urwu, rgwr, rwb, rrub, ggb, wbwrrbw, wrub, wwg, ww, ggg, brugwrr, wbur, ubbbrw, uwugrg, buw, grg, rrr, bgwu, rbggg, rgr, wuwub, rg, guuwu, rrwwwrbr, rrg, gurwg, wburrwug, rwr, wbg, grwbr, bgwbwug, bwg, bru, rbwuug, gggg, gurb, bbb, ubwu, gugbr, buru, gbbg, brb, wgr, guwg, gurgrbug, wgwugwwu, uw, wrbbr, wgwugurr, uwww, urr, bgubug, bbgu, bbuugb, rwug, gurbb, bguw, ubbbub, bbwb, gugbgwb, bb, wrrg, ggr, wrbub, uu, wwbw, ub, uggw, ugbggrw, bur, uuuguru, bgwuu, gwr, uurrrw, rb, buwugrr, brwrrrgb, guu, bgur, wggur, wub, gbb, rr, wubw, uuwgww, bwurwur, gubgg, ubwg, grbr, rwgr, wrubw, grgwb, uuguu, rwgwb, bwrrgg, ubu, bwbwggrw, uwg, bgguu, wwu, grwgw, bwrr, uur, rwuww, bwbb, gwrr, gwgrww, rbgw, grub, wugu, grrwuwg, bburbb, wbgb, ubbr, gggu, wbu, rrbugrbu, gbbubrwg, gwwurw, grbb, gbugu, wguwrw, ubggbb, rbgbu, rwub, gb, wbrgr, wubwwb, brwg, bwwbur, gugwg, gru, rbrwurr, wrb, gwubug, ggbguu, bubg, uruub, wuw, gubbr, gu, uwrubg, wggrbug, uub, ggrb, rwu, ug, ugrggw, wgg, rrb, bbug, wrw, uubbbur, uwgb, bwgr, uru, bu, guuuguw, gwwu, uwb, uwwwb, w, rur, wguuw, guru, gwrrwwb, wwrww, rww, bbur, ruuwr, rbb, bugubgrr, ru, rbubwr, grr, bbrbu, gwww, uwwgw, wwwu, uwr, uguw, rbwrr, bguwg, rguw, guwgbbg, rub, rrur, bwwbgw, rrrg, bgggru, ggu, wrrggu, rug, uuburg, rbu, wggrbgb, brguurw, r, guwrr, bwbgrb, urwgbb, rwgur, urg, gbwrw, grb, gwburg, wbr, bwww, brwr, ugw, uwgu, uggwr, brw, wgu, gug, gbu, gwrur, ggbrb, rbubr, rrggurbw, rwrru, uug, urb, grbu, gbgug, bugg, gbw, rgu, rgurrw, gwbw, ggw, bgub, wwgugug, ugubwg, wuggr, ruw, rbr, bbwuwwgb, wg, ubw, rwwg, wggbr, urubb, wwb, bubr
+
+ggrbbwbbwbuguwbuguwbbuwrbbbrwgurgwggbbwbguurb
+gruurruwgbwwrbbggwuwrwugwrguuwwrurugbbgubrurubrgwubg
+wguwwgbbggbbrbwurguububrwgbubwbwwuwgrgbuwgubg
+gbgrwggwbgwuwbgwgwgubwguwwwuwbwugbwgwrgrubg
+uubwgrwrwrruwrwggggwwrbgbbwgwwbwguwbrrwrgugbrbwrurggb
+rgruubburgubugugbwuguwururrbbgwuurwwbugburgrbbgbbgugwgbgg
+urggwuuwgubugurguwwrrbwuggbwbruuwbwugwwrwrguubbbbw
+bgrwuggburgggbubbgrwwrbuuwgwrrwuuurbugwgurubrwwrrugru
+rrbbrwgurwgrrgburbwurgbbuwrgrwwgrrgwrbrbrubbrwrg
+uururbwwwurbruwwwbubgbrugubrwubgwuuubggburbbu
+wrwrrgbrgwgububrgwggbguurgugwbuwgwwbggurbrw
+uugbgwuwbgwggrbwrwruwgrrwugbguwguuuuwurugwwbbruwuubg
+gwgrrwrguwgwbwgbuwuurgugugguwbrrrbguwrwubgwrgubggbburbu
+bbugbburwuggwrugrbgbbubbrrurbwbwburwrgubgwurgubg
+wuwubwguwuwwbbwgwugwugurgrbugurwbuubbuurrrrwwbgrgwgwgwgubg
+wurgwbwrgguwbbuuurrgrrgrgurgbrubbrgrgwbrrbgrurguurw
+brrburwwuwugbwrrrwruuwgrrrgruwrwgrbbgwwrruwwwbrbguuuww
+wgurrugrwbbrgubwrgbuwuubrggubbrwwwbwrggwggbrbg
+gurgrrwgruwbruwrbbbrugrgrrwrbbubgrbgbbgrwurwuguubgw
+rwrrruwrwwruugbgbbururbubgrrugguggbwgwgwguwwurb
+wuguguruwrurbwbwggrwuuwwrbwrbguuwwwruuwrguubgwbg
+wggbrgubrwrwgwubbgbuwgwggwgubrwurrrrrbggubg
+urgbbgggurgrbugbbubwbugrburgrurbgwbwuuuugbbuuuuub
+gwbuubrgwrwrguwbwubbruurgrrwwuwrrrrrwbbwuguugguwbrurrbbugw
+rrwuubbwruwuwbbbrrgbguwbguwgbruruubggbrbrwbwgbrbrbggu
+gbrruuwuwruwgwuubrwwwuugubwubwuwbwwrrgbrgwrr
+rwwrrbbgurgwuwgugwrgbgbgurwruwwwruugrbggwubwr
+uwbrrugrbgwwgwrguwgrbgwbrbbruugggwgggwwbwrwgr
+wguubgwuuwbrbgrgggrgbbguugrwgwgbrgugbrugbbuuurrruruuggrbr
+uwggbgrugruguggrrgwbwbguwwgugbgrbuuwugrubbgbuubg
+wbuwggugwruuurbwwrrrrbbwruugurwurrbggwgubg
+buwrbburrubggwurgburuwrurrgwgbuugrruugbbbgrgurw
+ubugwbrbwwrugrbwwrgwugubrrbbrwbbwbubugbububwwwubrrubwur
+gwgwwuwurgruubbwgrguuggubrrubgrwwwbwbwbbrrburbbbu
+rrbrwrwwrwrwbwbrbrgwwbrwwwrgwubwrrgbuugrugurrbug
+wurgrrbuurrbwwgwbguuuwgruwuubuwwgrrrwubgrbgw
+bbrwbrbbwgubbbwgubbruwrrbrbrrrgwbbruggbgrr
+buurbwrurgwrbugruuwrbbubbbubgbuwurugrbwrubuwbwwgb
+uwbwwgugruugbururbgwgrbbwruwrbruggbrrgbburggbwg
+grurbwwuwruwwbrrguwbwwrgrruuguubrrubrrrwruwwrrggbuugwu
+ubgrrwbwrrbbgrrgwuugrggbwgrrwrrrwbbwubrrrugugwubg
+urwbugwwwbrbbggwgwggwuwwggbuurrbuguubbrgubrwgrwubbrgubr
+wbbrgrugrgwuuwbubgwrgwrwuubgwwubuguugwgbgwuubg
+gwwrwbruwwgwbgwbgrggwwububurbbgggruurwwbgbbrugubbwuwb
+grggruggrgggbrubguwggruwbbbgrgruurrrgwguwuubrwbrrurgrubg
+wugbrrurrwbgurwgggwwgrurrbwubbuwwwburrwuggubgwwggbwggubgu
+bbuwrruwgrwuuwgrwrwgggbwrgrrbugubgururrwuubg
+bgwgbwgguwbugrrbwwugwuwgwbuwbwuwrgwbuwubggurbruwruuubr
+bwwrrggbuwwgrrgugruuurgrgrubrbwuuwbwgrubg
+brbrwrurruwurrwwbuwbggbuwwrwbwwruuwguubbuubgrbbuwwgbrrr
+rbwrwwrrurrrgrbuubburbrrruuurruurwwgbbguwrwgggu
+wuurbgwrggbuggbgwbubgbubgrrwbrbwgwwrrbgububrbr
+rgbugbrgrgwurbguuwburggwubggwrubwwggbbrrbbugbbrggrgwbbuugr
+brbubwwubwbwwwrrubwggwgwwgwrbwgwwurwbugrrguurbb
+grugwurwrwubbbbgubgbwrugrwwbgwburwwbrgwubu
+gurrgwbbbubbggrwrrrwbburwruurgrguwggrbwbuuwguugubrwbwb
+rrbgrrubuurwubrrbrrwguugrwrgrrguwggrgbrbgubububbrb
+wgrwgwgrgbguwgbrwwgrwbuuubwrgbwguwbbbbuguugrwwwburrbruuuubg
+uwgrrgrrbrwbrrbubggggubggbbgbbwbrugwrwrbrrwwgbwr
+uburgubgbbbwgwubggwuugwbbgruwubbugbbuurwruggrggwrugrbwubg
+rbguwurwwrbggrrgruuwubwgbbrgwwrgbrugguguuwwbbrggwbwurbgubg
+wrurwburbugrrubggubgbwwrbwbwggrwrrrwwuguwgguwrbubbubwrb
+ugrburuubbrbwgrbugrggwgbwuurgrwuwbuwrrbgubg
+wgubrbggbwubgruwgrgrwrrgrugubugrwgrurguwrgrububbbg
+bwgbbgwgurwgwugrbbgburgwbburrurubwbbruwgwbububgrgbrwgbuwubg
+wuwbuwrbuuggwggbbugbwbbuurgbgrrubbbrgggwrbwugguwubg
+wwbgbgugbgggugwrrwwguwbwubggbwgurgwurwrgwubg
+bwwubrrwurbgwubbuguuubrgrwrrwuwrugguuwwurubgw
+rrbbuwwrwbbruwwububbrbrwburrrrbubugwugbbgrwrw
+grrrbwgwugurrwuwwrrbwggubwuugbuwwwgurwgbuurubggbgw
+rwgbbgbrgubgugubwwbbruwggbwwwgbuwrrguuwwbubbrwgbgrwg
+urgrwrgbrgbggrurubwwrwrwgrbgubbruurbugubww
+gbburgbuggrwwgrgguugwbugwwrgurbwbugurubwbrrug
+bbruuuruurrgggrwburgbrurwurgrrrbrgwbuwrwrugurwwwbb
+wggguggbwguwrrrbwrgugrgwuwrubburbgbruubwuggbubuurgww
+ggrubgrggwgburgwurubuubugrgrbrwwwgbbwrbuwwwruwwwwrugwb
+rrrbugggrwuubwrbbgbgrwggbggwwwrwbrugruurwgrruuuubg
+grurwggwgrubrbbbubgwrbrrwgwugurubgrwwwguwwbrbubwbuuuwgwwbw
+uwrrguggwbrgbgrwbgguubgrrbuwurrwbubrggrwbgu
+wbwgrbgwgwrwgguwrrugbwburrwugbuwwugwwurrguuuwbbwburubgrbgw
+bbbrbrgwbwwgugggwwbggruwwbwurgwggbbbrurrwwbugrrgubg
+gbuuguugwrburruuwbbwbbwubrwbrgwwwurrbgwbbugwwbuwuwgruubg
+bwbgbwubugwgrwbubbugbwuwbubrrrwwggwbrggubwrbrbubgggw
+bbbggrurgggubbbbbburugrwggwwrwggbwuwbbgbggbrbuurugbwugbg
+ubgbwbguuwbrbruggwguburwwgbrwuwguwguwurbrbrrurww
+bruwrrurrwwwrbrubgrrguwwrrgggbbwrwwgbggrubg
+bbwugggwrwgurbrbgrwrwuurwwwruuugbgrrbuwbwbwgbgrwwburuubugg
+rgbgugwwwrubgggwwbuwrugwbbwwbwuwwbbgugbwburgrr
+rwrgrwbggwugguggrgurbugwbuggrrrrguwbgwubg
+urwruuwgrrwggwgrwuwgrggwbuwwbrbwuwwwrubg
+urwrbrrbrubbruwbguuwwggubuguwwggwwrugbuwwrbbwwgrrrbggb
+uurguwwgbrbbuwrrbrrgrbggrrurbwbrwugrwugruurbgbbu
+ggguuubrgwgbwuburubruuggrwwururubgwwbbubbrwbgwbubbwrg
+grwbrgwbbgbwwwruubgbwbbbrbgwurrrururrgurubugbrrrugwwbuwbw
+rgrubwgbwwgrbwburgwuubwbwwwbgrbbbwbbwbrwgbbrggrwubg
+uuggwggrgwugrgruurgbwrugwbrrbbbgwrbbgbrubg
+wurrguubwrbwuubgguuwrgrrugbgrrrwrbrwrrrgbuwwrbwrbgrgrgbwbu
+gubgbwubgbbbubwgrbubbgwrrguburururbgbbruuuruu
+ubwgbrwbwbgguwwruububgrrggrurruuuwwuwubuubgubwwgrubwwurggubg
+grwwwubuwurruububbwugubgggwrbgrguwwwugruruubgwbbrwuruubg
+ugrgbwwgbrwrwugwubbwuubburrrgrbbgruubgwug
+bgrgggwurrbggwubbrgrwbgwwwwwwbgwwbwrwbbrugwrububwgubg
+uugwwurrwggwrrbgwbrrgrrurugbgurggurubgbwwubbwrru
+bwgggbrubwguurrgwrggggbgrwwwuggbrwbgrgbgbrrugbwwwgbbrbwu
+bwgubrubrgbuwgbbuwgbwuurguwuuwwbruwuwbrrbuubg
+gbuwugubrbbburrwbrwuubrwwrwburwbrwguggugbrbwburww
+brguguururwgwwwbrwuwbgrrrgwwrguwwbuwrwguwgwwgwugwwugubg
+brubrwbwwrgwgrgguwwgrrbggbrwgbbwugbrgwggbbgbgrbwgr
+wrwgguwbrggwbgururwbrurggurwwrbuurwrrrrwburugggugbwrgubg
+grwwwggubgrrrwuwggbwrwgbrrbugrrbuguggwuruwugr
+wrwwwwrwubwuugurrbgugrwrbgrurgbgbubgbguuwubbwubg
+rgguruwrugrrrbwwuwwrwrrrgguwbgbggwwbuguguguwwgggbr
+wwwgwbbgbgbgbuwugwgrrgwbrwguguwgrggbwwbwwggbuuububgwbggugg
+ubwruwgbbwwuuwuurburgwgugwuggrbbgrgwguggwrgrggru
+rwrwguruubbgubrgubuwgrbwgbgbruwgurgwbbbgbrw
+wuggwrbrwwurwuuuruwwrwubwrgwrwwbrugruwbgwbgguuggbubwrrwguu
+ubwwuuwbggrwgbuwburuwrubgrgrbubgwrubwbwburubbbgu
+bggrbbuuuubrwwrrbgrggrgurugbuwbbbgbwubrrgu
+bgrwuggwwbbgubbwrggubrwwwrwwwrwgbuwbbgggwuurbugrg
+ggbgubrggbwgrgwbbbbbgugurguwggbrbbgrwuguwwruwbwwruuguww
+gbwbrrgwwggguwgguubwubwgrrrwrwbrgbrwbrbwbwuwrr
+uwbbwrrugbgrrbwwrwgwbggbwwrwggbruwururbwgrggrrggggwbbu
+uubbwuwbgbwgbugbugwrgurrgubwuguwrrbwbbbrgg
+bbwrwrwurubrgrbugbgwrgruubuurwurbggbbrguubg
+bbgrgbgwbbugwggwbrwubwwugwbwgrbubbubbbgwrururwwgubuuwg
+rwbwgwrbgbugrbwgburburbuuggwuguggrgrwwurggwuubgw
+uuuurubugrrbgwwrbuwwwbwuuwrgwrgbbwubggbwggwrgrbb
+ruuwugbgbrrgrwgwwwgwrbuggbgwubwrrbbrwrrwwgwbgrwrwbg
+wbbbwubwgrgwrwgwgwubwrwbwrwuuwbrwggwwrwrrugubgubg
+ubwbubugggggrrbggrwwrguubgrwrrbgwuubgbbuwwubuuwubgbuguubg
+rrwugrgurguguwggbwurwguuruwgwwrbwugbwrbbggbrrwgww
+ruguwurwgwbrwwgburubwuugwbgbgwwrurggbrubbrubwrugugugrwrg
+ggburgrubrbbbwgwuuwuugwuubrbuuwgrbwbrurbwuruu
+grbbbbrwuurguruurwwgbwrbburrbwugggwrwuruurgbrwwrwgb
+ruurgwgggwgbwrgrwbruuurgrbwrbgwuwbbrbggrbrrbgubbw
+gurgbwbggrwbrwbbgbwuwwbugrurrbuburbwbgbgrugr
+urrbgwugbuwbuwbwgrbrbugrbruwbwbwwwbugrrgrgbubbuurrrugwbwuubg
+ruuwgbgbbgrgwrgurgbbggwwuwrrrugwwbgruwugbwrgrruurbrbguu
+grbuurbrubrgggbbubrwgbwwgbgrbwubrurbgbuwgubgbwuguwrubgubgw
+bwbbrwwruurgugggbuwugwbuuwwrruurguwbuurwgbguurbgbrwbgurgubg
+rwggrwbruwgwrbuuwrruguwbbrrwwwrrgruurbwuwggrwbwgurwuubg
+gguruuguurugwuwuwuwurwwbgbgbuwrrwwgwugrbuubbbwrrggrubbw
+gggrbwgbggurgwrwrwgrurrrgguuwggbwwbrbbbrgwbrubrg
+ububggbgrbwbbrwbggwugbwrbrgwbrgrbwugwurgwrubg
+ubgugruruururwrwgguggbbgruwwruwuururbgwurwbrubgwgrw
+gbgrruwurrbbwbgwbuwggggbwuwwuubrbwurrbrwrrrubg
+rgwgrubrwbrwgggruwwbrwrubwwwrwbggwuugrruuwugbrg
+ubgwrrgbrgbbrgwbbwubururwbwuwwwugwwwrgbbrbrwgrgrbbur
+wbgbwgubbrbuwgrubbbgrwgwrgguburrgbwgbbwrgbgbwwwrwbubr
+wurubbubrgwwgwrbwrurrbwgbuugugwbgwbgubbubwuwbwbugbgrwurrg
+wrgggrguwgrwbbrgbrbbwwuwggrggburugwwgwuguburbwugrrgbburw
+rrrruwugurugwrggbgggwrgwbuwuguwbubbwgrbwgr
+rbwbbwbbwgbwggggwrbruwbugrgugubbgwrrrugubg
+rbrrbrgurwbgurwbgrwuwgrwwgbbrgurgggrwbuguw
+gbbgubwbguururbgrwuwrwbbbgwuurbbuwgwwruwwgubgwwbg
+buwrgbgggrruugugbwuruwgwgwwurwugbbbbbrwuwwwbbugubrgrgu
+gwbwrubugbrrwurwgrwwwwbwbbrgwubbguurwguuwrrb
+rwugguuubbbrrgurrbbwrrwuurrggrruwururrrwwgububwgurubg
+bbgbbrbgrwrgwuuwrrwubbuwuwrwuwrburggwwburwbugubgrr
+uurwbwubwbgrruwwbbwgwgrrbrubrrbubwrwgubg
+rrrgwguwwrwugbggrbururbgrrgugrbgbwugbgrwubg
+gbuuwbrubgrrwrgwbwbgbrgbuuubrugwggwurrggbbwuwwgbwwbbuugubg
+bbwbgwbwrrwgguwbrwgrgbbubwubwgwgrwguwurrrwburbgugbburuwubg
+ggbuubrwrwurwgwbwburwwwgwwwrgguwgurrggbwurrgwgw
+grrwrubwgbbrwburgrguurgrurwbwbrbuugrwuwrbwurubgwgu
+brwwwrruggbbuwrbbgrugrbwgbwwwrbgbwgburrwrurgubg
+grbwugwrugrwrwrgrrbruguwugggbrgbrwbwruwgrgguugbgwbgrur
+urwgwwrgurrubugwwuwrbrrrbwwrrbwuuwuuwuwururuguruwbwurgr
+urgrwuwuwbbrbwrbuurbbwbbwggbruwruwburgrwgwuwrruuubg
+ruuwwrwwwgrrwwgwubwbuwgwubbggrgurruwgwrwugb
+urbbgggrrrrrrrrwwbrrbgggurgwwugburwbuuuwwwrurwrrbubwrrwrw
+rwbgrbbwubgbuwrrgbbguwbbrbrwbgrbuwwwwugbugwrwurwgwubg
+ruwbuggwgbuuburwburgwgurrwrggrrgurrwburgbwbgr
+bwwgwggrgrbbggbgrrwbggugwbgrgbbrbwbbrgrbbuubg
+gggbbwbwgbbuubwrbggburrbgwwruuguruuguubrwrwwuubgw
+bwwwbuwrwrwugubrwbgwrwrguubwrugurrgggubg
+grwbuwwburbwbwurguuggrruuuurwwurggbgrbuwwrgr
+wubbwuggrgwbrwgbwrgwwwwuubuguuwbgruuwgrwgbuuwrwwurubgwwgw
+bbrwbwuwgwwbwwrrruwwbwwuwrguuuuuwrwurbbbbuuugurgugw
+wggubgbuubbuurburruwurbgwbwubbgrgwgrwwbbburggbu
+buurrrwbgguuurbbbgwrgggggwuwruwwbgguggbwbrrrgrggwg
+gwbwrgbrburbguwbgrwuwgburgbrrubrubugbrugubg
+rwgrgwwubguggrwubggbrrurwbburbuwrrbuwbgrbgrruwgrrwwubg
+wbwwgwrgguguwrrgggbwwbrrgbububwwwugururrrbr
+rbgurbrbgwrbgrwuwruguubgwuwbgwguwuwrbruwbbuwubbu
+bgrgbwgbrwuruuugrrbugrburburgrbgubbrwbubwgubg
+ggruruwrrwwwrbrgbwgwbuubgugguwgbuuwggrwgbgburbgwbr
+wrgrrgrwgwbbbrgugguwbwuubbwbruuwwrbgggugwwgbbruugr
+ggwwbbwugrgbgwbbbuwwwwuggrgguuwggrrbbwbugwgug
+wrugrwwbwgbwruwuwwubugubggbuuwgbwgrurbgbuwguurrggrrbwwwguubg
+grwurrbbuuuwrubbrwrubrbbubgugbugbwrgwggurwubg
+gbggwurwgguwwurrubrgwbrbbwgbbrugburgbgrwrwguuw
+rrwbwuuuugwrbwuwgbbbwbwwwrgrwrurbgrrgwrbwugbrrbrwubgr
+uuwwbgguugrbrwgbwrrbbrwrgbubgwrggwwuurrgbwrbgwuugwruuwwbgr
+wgrurgbugwwrrwrrrgbbggrwuruuwbrrgrrgubrrubg
+uuwrruubrbbgururrrbbrwruubbwwgbwrgwrbuubgw
+urwrggbbgbgrwgwugurrrgbuuwbbwrgrwburrrbugwggbuwgbw
+urrggbwggggwrgrbgbrbbgrgbgubrggbgbrbwggwuurubg
+wwbrbwbrrgwuuugrgwbgrwwgwuwuuwggwbbwggugwrbggwgrugrbubgw
+bggggurbgugruwuggwuruububwugrbbubgrwurbbrubgw
+bbwwgguwwrggwrwbwbbuwwugugrrggurbwwrgggbwuwbuburubg
+rwgbgrubrrbuwwbbbbbggwruwubgbgguwuwwwgwggbubrr
+rurwgwbwuugwruguwbwuururgurguggbugwwuguuwrwu
+bwrbwruwubbgwguwgrwuubuwgwugwwgrbrrubgwbgbrbwugwbuwwwb
+rwgbgrugggbgubugwbbbwggbguugwggrbbbrubwbubgrbb
+rgwwrbrbrwrgrbgbwwuwwgwrbuwrgbrrurugwburrggrwuruub
+grwbbbubbuububbrrwubgugrgrwruuwrwubrruggbuguubg
+bbrrbrbrwbrgwgwuwguuuubbruwwbuuwuuwgwugbgur
+uuguwbururbggrgrugbrubgggrrwwuugwgbrubwgbgwwgurr
+rgwrgbbwbwwruggguwbrugwbrrwwbwrgwbwrgrrbuuuggbuubgw
+wbbbguwbuuugrurggwwbgbuugwwrguggurrrbbbrbgbrb
+wrbuuuwrbgwuugubguggrggbgbuguurbrrbrgbrurbrbbuugrw
+bgubwwgrbwwwwwbrrrwgbwwugbuwgwruugrgbbuwwgrr
+urrggurbwwrurbwbwrbwwwwuurugguwrggwwrrwgbwbrrruru
+rwbgwguwurrurbwuwrubbwwbubwwwwbrggugubgw
+burgrurbrugburgrbgruwggruuuwgrgwuwrgwurrrrurbwrwwwgbuwubbb
+rruwuwgrubrbubugrwbwuuugwuwubbgwrbgwwgubrurwbgwbwwgwgwbwuu
+wgrbggrrwbbgurwurwrwrggbwwrwugwrwuugwgwubrubgwbguuwbwwgbu
+guuwrrggbrrugbrguggrbubrggbwururwbrgrwrbwb
+gwgggggbgrgbbbbuurugwrruuuwrbwrggguwruggwgbbugu
+rguwrwrrubbruwruubwggbuwwgbgggguwugwwubwrgwwrubrg
+brggwbbbubbrrrwrbwrwbgubbugbbgwgwbrwbggurbbwuubbgrggrbbr
+wuuuurbbuwgubwbwrrwbbgbuugrgwgwuburubuuwbw
+ubgwrruruwbwgurwrrrrrbrrbrwuubwrwwbrwwrgww
+grgbguubrugrgbgggwgrwgrguwbubbwbugrburrugrwbwbgurubgw
+rgguwgruburwgbguggbwgrgggrubgwgrguubwubgw
+uurubgbbuubbguwrgrwwgguwgbrrwguggggwurbwubg
+uguguruuuugbgwgwbuwgbrbrwrwbubbuubugrwwbbgubg
+guuwwruugbggwubrrgrbuugbwuwggwrggwgwuurwbgbwbuwbguurbrbggu
+bbubwrgbggrwbbwguurrrwrugbugbruwruwwbugrwbugbbgrugwrwr
+guwuuwurrububbgrwugruuuguruwbrbubgrrubgggbu
+wrburuguguburrbuuwbgurbubwruubbuurgubrugrbgubub
+wurbrruurgrrruggbbrbruuugbbgggurbgbgwbwbrbugubg
+rwrwwrurrwgwgbrubrbwwrrgwurruwgwguuguubg
+uuwwwgbgwuuruwrubrbgrbruggrggbwruurgguguwgbrrbrbwwuubg
+uggugggbwrgugwrgwubwrwgrubggburgggwrbgbgbugruwugg
+uggbugwwbggrbbuggubrggwrwwurbbuwugwruuubgggbww
+rrrugrwrrrgwgbuguwgwugrbuguubwgrwgwbrgbbwguwuuubgwb
+uwwrubgrrbbugwgwbgbrgurgrbwbgrwbwrgwruuubgwrrbuu
+gwrrrwrrggwrrwgbwruwubuwwbgubgwgbwgggwuwugrgwruurwgwuubg
+grrwrbugrbubuwruububbrgbuwrubrgbugrruurgwgrrgubg
+gurbbbruuuuwwbbwgrgrwrrwuwubbbgburubwruwuuugwrgbgg
+urggrgbwbwbgrgrrbrbwguuwbuwwbggrgbbbgggwuubwbw
+ubugrubuugugwwrgwrrrbwwgbrrbruuggguugrugwrurrgrbbguwuwgrg
+bubrgbbrwguuwbbgwbbbwbrgrbbbwuwrbubgrwwgbwbrubg
+guwwurwgbwgbrurwuuruwbbbguuurbwuwubwbrrgrbwgwugrubrwrwbuu
+rrgruubrurwurwguuwbgubruwugbuwwurrbwwuwrwwrrugrubguwubgw
+ugurrrwbguggbgwggwurgggrgggrgbwuwgrgwrbugr
+uwbguwugrgbgwwbugbbugubgrrgwggrgwguwgugggbu
+rgbgwuwuwrrwbggrbuuwrwbrwurrrrrrwrgrgrburbu
+gbwurbbbuuwugbwwgubruugwubbbbwrbwrwrrwggwgwgwbuubg
+wbuggbrugrrbugbbwrbwgbbgbbgrgwwurburuurbuuuubrwgruwgrrbrubg
+wrwggwurggbuwrwbgruugguwbguuurgwuwwwbbruuu
+wwrurwrrwbrbwwbrgguugbugbuwwwwwwrurgbrgguguuuubg
+wwubbbrubgrbrrggburgwwgugbggggburwbguguwwburbwbbgwubbur
+gbubruwrwuwubbrgwuburwrgubbgbuwugruubbwrgrwubg
+ugrubrugwbgbbgurrbwuwurgwggrwuwbbbuuuwugbbuugrggbgb
+gwggwgwgrwubgubrbrrubrugwrbgrgbgwbuwrburrrurbgrrubgw
+wgrrggwwubgurwrrruuwbwrrgwwgwruugburbguuubruwuwbrggbrbb
+bbrwguwgwgwbgurbruruubrbbgrbrgburguwuwggwwurrrgu
+wrrbgrgguwugwwbgurgwgbuwbwguwbwrruwwrbugwrruuwbbwurbwrru
+uwuwurrwrbruwggrbbrrbwubugrbgrrurgrggwrwgrubbb
+ubugrbbubgwgggrurbburwbguuugwguwgwguwurrgwuwwbugrrburb
+ggrwwgrurwbrrbbbbgrbwggbwrbgurbbuurwwbbwggugww
+wbuurbbbrbgruuggburrguubgrrgurbubgwuuurubrr
+wgrwbwwwbrurgurrgbruggwwugwubgubububbbuuuuuubrgbwuwuurbw
+bbgbggrbbburgubbruuwgggwrubuuwurgrubrwgbrggubg
+rbgrbwubwurwbwwurbrruuurbrguwwwrrbugrbubrwugrwb
+wrugurgwuwurrbrwugruguggwbwwwuwwwrrrwwubg
+gbwuggbbwbbuububruburrrwggwbwbwgrbgwgwguwrubuururbwuubgwub
+gbubwwwrruwwubruugrbgbgwrwrrwruwwuggbrburbguggubuugubg
+wgbwgwrurwwurwbrububrwbrrgguwwwbwrrbruugrrru
+ubrrbrugbwuwubgbbguwrwugggbrgrruuwwuwubbgrwurubg
+uruuuuuuwggrbgggugugbwuuurwgruwgwugwrbgubbrrgwubg
+brruurbgbburbrugwuuuwbwrurbubbbubgrgrwwurgbugwgwgrugwuuwbb
+gurgwuubwrrrwbuguwuwgrbrrubrwgurrrugurbrrrrrbrwwrbugrg
+wbwubwwuugrrwrbggurrgbbuwwgrwuguggbubgrrgbrbrbbgwbrubg
+rrwubrwrrbgrruwrbbgrwrwuugggwgubgwuwbgwgbrwwgbgbgbgwbgrr
+bbwggbbwuwwgbwuwwuuguburgwbrgbrwwruurwbuwrrbuwgbrw
+rbgrbuwbuwbbrgrrurrbuwbrwrrrbruggguuuubbrbguru
+ugwwubwgwgwbbbbguwbbuggbuwuburuuwwwwbwwrggwgrruwwwwbbubu
+brrrrwugbuwwruwbwgbrgwwgwbbbrwrrrgbgwbbbgbubgwrurgrubg
+bwrwrrwwbwguwburrrrgwbbrgubrubbbwuwrbrwuwburrugwwrwwrbbruu
+gurrwuugurbuubrgbwubbgwubbbbuwruugrrbgurbggrrrguu
+gwrwuuruggwbgurwwgwrwuuwwbgggbrwbugbrrgwbgrwrruuuurwrg
+grggwgwgbrrbbwbrubgbrggubbbbgbrgbwwbwbrgubggbgbubgw
+ugbgubrbrbrggwguwwwrgbgruggurgwgrrugbbbuuubg
+gubwugguwrbuggwburrrwguwubbgrubbuwruubrgrgrugrwrrbrbbugwu
+rwgwwgubggurrbwrwrguwrrbrggrggwwgwwwruuwgburrrrbuugbg
+wwrwurwggggrrrbbbbruurgguwwrrurugurgubrbwgubgwgrbwbguubg
+rwguurwrrwwrrwbrbrugwbgrbggbbbuwbrrrgbuggwwwuubg
+wubwbgggubbbgguwurwggwbwuwbwwubwguurbwrruwwrubg
+bbuugrggbbwubgurwbwrwwuwbwbggurwguggwbwubg
+bgrugwuwbgwwrrwwuwubrwurwbuurwwgbrgwwggrwgwuwububwbbuubg
+bubrggwuugrgrwgbruugbgrwbgbbbwbwwurrrgwgwwbuggguu
+ubrbwbururbrgurgugrgurbwbbwwgrugrbubrugbbbbburbrurgrwgwgu
+wuwubuwbbugbgrrwrgbgbrbbugguwbbwwwgwugwwurwwuugbwgg
+bubwbgggwugrwgrrrrrrrrugguwwrrbwrrggbruwuurwguuwwgggwwwrgw
+wubbbuuwwbbwubgbrgurbggggurwrrbgbrwwuggwubgw
+wbubuwuuwwbuwwbwrbrggwwbbuwggbwuuwwrgrbwurguwgbrrwwubgw
+gwrwggrubwguubwuggugwrrwgbrwrrrwbubgwuwbbubww
+gguwuugugbuubrwbrrrbrrrubwburrgwgwgwbgurbgbrrwbrgr
+bbwbbgbbwwuwbrugbwruggbugwbwgurgwgggbrwgug
+ubruuuuwrggbrggbugbbwwguwguwuggbbwguuburugrugbrgruuwbbbwubg
+wuggrwgwbrgwwbbwbgwrbrwgurwwgbbwrwbgubwrugggbrgrbbrbgrrgubg
+rbwrubrgwrgrwugurwbguuugbrbbbwubbwbbguwbrrbbbwrrwg
+brubruurbwguwrrwuwrugbuwwwgbrrgubwwgrggwgbru
+rrbggwrbbwbbrwrrgrgbgubggbrwwrrbburwwbrwuwbrbbwbrgw
+wrggruwrwwwwwwugbrgwgggurubbrbbgguggrwbgugugrrruwu
+gggwurggwwgurugububrbbrurgwwrgrwwbwubwubrwgwrubg
+uwbbwgrrrbrwbrubuuwwguwguwgubbgruruguwbwubg
+bwrrgburgwguuurwggwrwgrubbbuwruwbrgwbuuwubug
+ugurrwbgbuwgbuugrbwgugwguwwbrugwbbuwurugugbuuugbu
+bgrbwbbuwbrrgggwugwgwrbbuwbugubgrruurubg
+ggbrrgubbgurwwrgrgbbuggwrgwruguggbbrrrrbbrbwurwr
+ggbgbubuubbgwgrrrbwwgbugrgrwbubburgbuuubgw
+ruugggwrbbgbbuuburrgwbwwgbwgurbrbbggbgubgw
+guwrbugwuubgubggwgwbruugrwbbwgwrwurrbggrrgwub
+bubwgbrguugrwwgbwrwbuuurwrwrgbbuguwwbgbwubg
+brubuuwgbgwgrggruruwrrubwbuuwwuubbrrrwbuurwuruuur
+grgurgggwggruwuwrgrbgguggrwrbgbugwbuuubg
+bwuuwgbrbwgwurrrwbrwwwbuwugbrrggbbgbuwgrubrugubg
+wbbbwuwububuuuwbwgwrrbuurbwbrbgwuuwuggwubrguuwggguwuubwggr
+uurgwgbgwrwwbguubuurwwrwurbuubwbwgwuurwwwwubgwrugrgru
+rgwgbbbgguuwuugugwbrurbwbbbubwurwubggwuurggrugwbgb
+gwgbwuwwgwuugruugrruwgbwwgwugbuwbrrbbgwwuwgwbgwugwbbrrguw
+grrbbuuggrugbgbbbgbrgubuwrrrwrbwwwguwwgbgwgggwug
+wwwrwgbgruubuwbrwuuuwggubwbrgrrguuuwbuwugbrgrbubrbrubg
+ruwbrwugbbrggwguurgbrugrgbruuuwugugwurruuwbrbwggubg
+uuuwuguwuwrubgbwbgurguubwwrbwrrgbrgrrbbgrrrgwgrur
+uwubuubwrggbwwrugrbwrwwruuwbrrbuubbgrruwbg
+buuwwwggwbuwwwwgwbwbguwgrwrrgbwuubwgurrguubwwwub
+gguurgrurbrgwwrwgugbgurbwguugrgwrrwbruugrrubggw
+rbuuwbwgwrrubbrbgrrrugggrrubgbbrbwgbuuurrubg
+rbburbbwbwurrrbbggwwgwbgwggbrbubwgrugurbbbrgubwwuwwu
+guwrbgbwwuwbbuwrwgurbgwrbwbwburwwggwruruburguw
+ugubbggbwbubbgrwuubruwggbbwrgwgbguubbwgwwggrrburuurwrgguuubg
+wggburwgrgrwuugrggburubrbwbbbwggrwbwuwguuwbr
+burrbuwuwwwbrrwguwggubbrbrgrrguwuwwuuuwwbgguuuwubg
+wrbbwubrrugrrbruruuubuuwbruruwburrwguwggbwwuurrgwugbruubgw
+gggwbubwwrwbugwuwwuuubgwguwbubgwrbuuwbwubbbrbrugbgbur
+wrgbruuguubgwbuwrrbubwwggrrrrbugugggbrrurrrgggbbgrguwrgwb
+gugbrwurgruwgrrwgbruuuuwburbgwwwwwubgbrgwwrrrbgubg
+wgwurwwbuwbggwgugrbwuruwuwuururbrrgwrbugugrrugubg
+wbgwgrwwuubrurwwwuwwuuwrwuwuburwuwwuubgggwuuuwubgubg
+rwgwguwuubwuwgwggrwgwrrbbggrwruuggrbubrrgbuugwuruubgrgr
+rbububguururbwrurbrubbubuuubguwbrbuugrrbgwwgww
+grubwubrgwurubbwbgwgubguguuwbgruwubwwrbuurwgurgbr
+uubwgwwuubgggbgbruwuguuwbwurguuguwbgguuwwrb
+bwwgbubrwwbugbrrwguwugruwwgbwbururbrbgrubg
+ugugggbggbgrwwugrggbwbuwggguugububuwbubbubuwgubgw
+ugrubgbbuuuwgbuurbgwbwubguggrurgwrwgbrrgrbruwrgw
+rrggurwrrwugguuwrwuruuguggrbwwbrrgwwbrgubgw
+rbrbgburgbuuruuugbrggbwgrubrugrbwruuwwwwrgrwwr
+rrggbrgrwrbgrbrrwrgwrwwwwuubrgwwggubbwgugrwrurbgrrruwrb
+rrbrwrrrruurgbwbggrrwwgubrwgggwwwugrwwubgwruguwugwbbbug
+rgbgrwgbbbguggwgwbwugbbbwgbgbrgguurgbbbugrubuwrrgwubw
+bggwwrbuurgwwwbrbggggbgbbgwwgwwrbwbbrwbgbbrrbgrgwwbbggbwuw
+rwururuuggwbugguwgwgrbubrgbrrbruguuwbbbuurg
+gbbbrbgbwrrrgwrrwgrrrbubrggrwrgrgburrrruwwurw
+guguugwbrgwugwwwbuwrrbugurbbbruubggwuuwguguwu
+uwbggwbururwuwbrggbuwrwubuurbrugrurruwurubuggbbwwgww
+rruuububwrruugrurubbbwwugrbruggbrugrrwwgwrguwbburubwwbwbrubg
+bbwrggbgrrbuwwggwgwbubwgbwugwgbrurgbwbbbbbuuuubw
+gbgbgwrrugggubgrrubwguwuuwwwwguubwggwuwgugwuuubu
+rguuubuwbrbrwwgwggbugbubwrrruggwrwuuguwwggugrrbgrbrwwuww
+rrgrggruggbgwgggbrgurggurburrurbuburbgrgbbubrwgru
+gburrbwbrbuwugwwbbrggwbwwgrbbrwwuwgubbuwbwr
+bgurwuggrwuwwwgrrgrwwgurbrbgbruggrbwbgurwbwwwg
+bgbbgrubbruggrgrguwrbbgbwguwwubwbrrwwubgw
+bgurguwrbbrrrbgrubrwrwgwggbbggbbubgrguggbwggbbugbgbwgrwuw
+urugbbrbbbwugruwrwrggbgwbwwrwgrugwugbguwubgb
+rgurrwbwwugggbgwubbwbwwwruguggwruuwrwrurbbrwwggbrrbgubbwubg
+ugrgwruuruuggwrrurwwwguwwuggrwwgbruburbggbrb
+uurgbgbgwgbwgrburrurrrruruurrubwbgurbwubguwgubwbwrbgrr
+grbrggbbbgwbbuwwrbuwuruwwrgbuguwgbgrgrgrwwbwgrbw
+wwruburuwggbrwbruwurrrgbbwwrwgguruwbrwubbr
+bbwburbbrbwubrbwuruugrrwwgbubgugggrwugrbgurgwwgubg
+ugbwwbrgubrrrurwgbgubrrbbrbggwburrwuuuuruwgurubgwgubg
+wbwubrbgbrbgugrrguggwrrgwbugrwubgwgrrgbgrurbwrbrububwwgwubg
+rrububggbrwbrubwubuuwwrbubrbuggwrbubgwwururrgwwurwr
+wbrbrgbrbgubguugwruwrrgrwgguurugbguwubbuubwggrrggubwbb
+rguuwbrururbwbubggugbwbwuwgggruubwbuubwrrrrug
+ruwwggggwruwrurwgrguwwgurbgwrgwuuwrbrrwbgbuubrwubgbg
+rugrgrwgbbrgwrggguggbwrugrrrbguwwbguwrbwwwrwugbgwwrwbr
+wwubggbwubgrubwrbrgbrbwgbrggbwggggwggggguggrbr
+bbuwgwgbbuwbuburgwgbgggugrgrrbrgurrguurugbbuurubggbg
+rruwbwwwgurbgugbubwwwuwwuwbururgwwrrwubg
+ubgbbuubwbwgrbbrbuwwuuwubrgugurbgruwurwwgu
+grbwbubbrrruuuuuwuwrwugwuwgbubwbbwrbwbbubbg
+urgrugbgbruwwburwrgrburbubrbbuwrrgwgbgrubg
+ggububgubgwgbgguwrbrubwwburugwubuuwrgubg
+brgwuugggbbuwbuuuwruwubrgguuugrggbwbwwrbugrwbguurugwgbu
+wwwggugwwbbbgwgururugbgrwubgbwrwrggrubgrgwbrbrr
+ggburgrrbrbwbrruwwwrwurgbwgrbrgguwrgubbubwwubg
+buubugggwrbwrbbbgrbbgwwwwgbrrbbugggggbgguwbruwurwbrwbrgw
+rbuurwgrwuuuwrggurbubbgbrgwrbwgrwbbuubgrrbwbwubruubg
+wgwwbrrrgwbuubwgwgubwwggurggrrwugbugurrbugwbwrubbrgurbbgw
+ugwguuugbrggggurubrbbgbrrwwbbwurrruwrugruwuwubwu
+urrbbgwwbburrbrwbwggwrbbwbgwwbruwubrbwbgubbgwrgu

src/holt59/aoc/inputs/holt59/2024/day20.txt

@@ -0,0 +1,141 @@
+#############################################################################################################################################
+#.......#.........#.....#.....#...#...###...###.....###...#...###.....#.....#.......#.......#.....#...#####.....#...#...#...#...............#
+#.#####.#.#######.#.###.#.###.#.#.#.#.###.#.###.###.###.#.#.#.###.###.#.###.#.#####.#.#####.#.###.#.#.#####.###.#.#.#.#.#.#.#.#############.#
+#...#...#.......#.#...#.#...#.#.#...#...#.#...#...#.....#.#.#...#...#.#...#.#.....#.#...#...#.#...#.#...#...#...#.#...#.#.#.#...#...........#
+###.#.#########.#.###.#.###.#.#.#######.#.###.###.#######.#.###.###.#.###.#.#####.#.###.#.###.#.###.###.#.###.###.#####.#.#.###.#.###########
+#...#.....#.....#.#...#.#...#.#.......#.#.#...###.#.......#.#...#...#.....#.......#...#.#...#.#...#.#...#...#.###.....#...#...#.#...........#
+#.#######.#.#####.#.###.#.###.#######.#.#.#.#####.#.#######.#.###.###################.#.###.#.###.#.#.#####.#.#######.#######.#.###########.#
+#...#.....#.....#.#.#...#...#...#...#.#...#...#...#.......#.#...#...........#.......#...#...#.#...#.#...#...#...#...#.#.......#.#.........#.#
+###.#.#########.#.#.#.#####.###.#.#.#.#######.#.#########.#.###.###########.#.#####.#####.###.#.###.###.#.#####.#.#.#.#.#######.#.#######.#.#
+###.#.###.....#.#.#.#.#...#.#...#.#.#...#.....#.....#.....#.#...#...###...#...#...#.#.....#...#...#.#...#...#...#.#.#.#.###...#.#.#.....#.#.#
+###.#.###.###.#.#.#.#.#.#.#.#.###.#.###.#.#########.#.#####.#.###.#.###.#.#####.#.#.#.#####.#####.#.#.#####.#.###.#.#.#.###.#.#.#.#.###.#.#.#
+#...#...#...#.#.#.#.#.#.#...#.#...#.....#...###.....#...#...#...#.#.#...#.###...#...#...###.....#.#.#.#.....#...#.#.#.#.....#...#...#...#...#
+#.#####.###.#.#.#.#.#.#.#####.#.###########.###.#######.#.#####.#.#.#.###.###.#########.#######.#.#.#.#.#######.#.#.#.###############.#######
+#.....#.....#...#.#.#.#.....#.#...........#...#.#.....#.#.....#.#.#.#.#...#...#.......#.#...###.#.#.#.#.....#...#.#...#.............#.......#
+#####.###########.#.#.#####.#.###########.###.#.#.###.#.#####.#.#.#.#.#.###.###.#####.#.#.#.###.#.#.#.#####.#.###.#####.###########.#######.#
+#...#.........#...#.#.#...#.#...#...#...#.#...#.#...#...#.....#.#.#...#.###...#.#.....#...#...#.#.#.#.....#.#.###.#...#...........#...#.....#
+#.#.#########.#.###.#.#.#.#.###.#.#.#.#.#.#.###.###.#####.#####.#.#####.#####.#.#.###########.#.#.#.#####.#.#.###.#.#.###########.###.#.#####
+#.#...........#...#.#.#.#.#...#...#.#.#.#.#.....#...#...#...#...#...#...#...#...#...#.....#...#.#...#.....#.#...#.#.#.......#...#...#.#.....#
+#.###############.#.#.#.#.###.#####.#.#.#.#######.###.#.###.#.#####.#.###.#.#######.#.###.#.###.#####.#####.###.#.#.#######.#.#.###.#.#####.#
+#...#.....#.....#...#...#...#.....#.#.#.#.#.......#...#.....#...#...#...#.#...#...#.#...#...###.....#.#...#...#.#.#.#...###.#.#.#...#.......#
+###.#.###.#.###.###########.#####.#.#.#.#.#.#######.###########.#.#####.#.###.#.#.#.###.###########.#.#.#.###.#.#.#.#.#.###.#.#.#.###########
+###...###...#...#...#...#...#...#.#.#.#.#.#...#...#.........#...#.....#.#.#...#.#...#...#...#...#...#...#.....#...#...#...#.#.#...#...#...###
+#############.###.#.#.#.#.###.#.#.#.#.#.#.###.#.#.#########.#.#######.#.#.#.###.#####.###.#.#.#.#.#######################.#.#.#####.#.#.#.###
+#.............#...#...#.#...#.#.#.#.#.#.#.#...#.#.#...###...#.#...#...#...#...#...#...#...#.#.#.#.....#.........#.........#.#.....#.#.#.#...#
+#.#############.#######.###.#.#.#.#.#.#.#.#.###.#.#.#.###.###.#.#.#.#########.###.#.###.###.#.#.#####.#.#######.#.#########.#####.#.#.#.###.#
+#.#.............###...#...#.#.#...#...#...#.....#.#.#.#...#...#.#.#...#.......#...#...#.#...#.#.#...#.#.......#.#.......###.......#.#.#.#...#
+#.#.###############.#.###.#.#.###################.#.#.#.###.###.#.###.#.#######.#####.#.#.###.#.#.#.#.#######.#.#######.###########.#.#.#.###
+#...#...#...........#.....#...#...#...#...#.......#.#.#...#...#.#.#...#.#.....#.....#.#.#...#.#.#.#...#.......#...#...#.......#.....#...#...#
+#####.#.#.#####################.#.#.#.#.#.#.#######.#.###.###.#.#.#.###.#.###.#####.#.#.###.#.#.#.#####.#########.#.#.#######.#.###########.#
+#...#.#.#.........#.......#.....#...#...#.#.#...###.#.#...#...#.#.#...#...#...#.....#.#...#.#.#.#.#...#...###...#...#.........#...#.....#...#
+#.#.#.#.#########.#.#####.#.#############.#.#.#.###.#.#.###.###.#.###.#####.###.#####.###.#.#.#.#.#.#.###.###.#.#################.#.###.#.###
+#.#...#.......#...#.#.....#...#...#...#...#...#.#...#.#...#...#.#...#.#...#...#.....#...#.#...#.#...#.#...#...#.......###...#...#.#...#.#...#
+#.###########.#.###.#.#######.#.#.#.#.#.#######.#.###.###.###.#.###.#.#.#.###.#####.###.#.#####.#####.#.###.#########.###.#.#.#.#.###.#.###.#
+#.........#...#.....#.........#.#...#.#.#.......#...#.###.#...#.#...#...#.#...#...#.#...#.#.....#...#.#.###.#.......#.#...#...#.#.#...#.....#
+#########.#.###################.#####.#.#.#########.#.###.#.###.#.#######.#.###.#.#.#.###.#.#####.#.#.#.###.#.#####.#.#.#######.#.#.#########
+###...###.#.#...#...#.........#.....#...#...#.....#.#.#...#.#...#...#...#.#.....#.#.#.#...#...#...#...#.....#.....#.#.#...#.....#.#.....#...#
+###.#.###.#.#.#.#.#.#.#######.#####.#######.#.###.#.#.#.###.#.#####.#.#.#.#######.#.#.#.#####.#.#################.#.#.###.#.#####.#####.#.#.#
+#...#.....#...#.#.#.#.....#...#...#.......#.#.#...#.#.#...#.#.....#.#.#.#.....###.#.#.#.#.....#.....###.........#.#...###.#.......#...#...#.#
+#.#############.#.#.#####.#.###.#.#######.#.#.#.###.#.###.#.#####.#.#.#.#####.###.#.#.#.#.#########.###.#######.#.#######.#########.#.#####.#
+#.#...........#...#.......#.#...#.#.......#.#.#...#.#.#...#.#.....#.#.#.#...#.#...#.#.#.#...#.....#...#.......#...#.......#.........#.....#.#
+#.#.#########.#############.#.###.#.#######.#.###.#.#.#.###.#.#####.#.#.#.#.#.#.###.#.#.###.#.###.###.#######.#####.#######.#############.#.#
+#...#.....###.............#.#...#...#.....#...###.#.#.#.#...#...#...#.#.#.#.#.#...#.#...#...#.###.#...#.....#...#...#...#...#...#...#...#...#
+#####.###.###############.#.###.#####.###.#######.#.#.#.#.#####.#.###.#.#.#.#.###.#.#####.###.###.#.###.###.###.#.###.#.#.###.#.#.#.#.#.#####
+#...#...#.....#...........#.....#...#.#...#.....#...#...#...#...#...#.#.#.#.#S###.#.....#...#...#...###...#...#...#...#.#.....#.#.#...#...###
+#.#.###.#####.#.#################.#.#.#.###.###.###########.#.#####.#.#.#.#.#####.#####.###.###.#########.###.#####.###.#######.#.#######.###
+#.#.###.....#...#...#.....#.......#...#...#.#...#...#.......#.#...#...#...#...###.#.....#...#...#...#...#...#.#...#...#.........#.......#...#
+#.#.#######.#####.#.#.###.#.#############.#.#.###.#.#.#######.#.#.###########.###.#.#####.###.###.#.#.#.###.#.#.#.###.#################.###.#
+#.#.#...#...#...#.#.#.###.#.###.........#...#.....#.#.#.....#...#.......#.....###.#...#...#...###.#...#.....#...#.....#.....#...#.......#...#
+#.#.#.#.#.###.#.#.#.#.###.#.###.#######.###########.#.#.###.###########.#.#######.###.#.###.#####.#####################.###.#.#.#.#######.###
+#.#.#.#.#...#.#...#...#...#.#...#.....#.#...#...#...#.#.#...#.....#...#.#.#...###.#...#...#.....#...#...........###...#...#.#.#.#.#.......###
+#.#.#.#.###.#.#########.###.#.###.###.#.#.#.#.#.#.###.#.#.###.###.#.#.#.#.#.#.###.#.#####.#####.###.#.#########.###.#.###.#.#.#.#.#.#########
+#.#...#...#...###...###...#.#.....#...#.#.#...#...###...#...#...#.#.#...#...#.###.#.#.....#...#.#...#.#.........#...#...#.#...#...#...#...###
+#.#######.#######.#.#####.#.#######.###.#.#################.###.#.#.#########.###.#.#.#####.#.#.#.###.#.#########.#####.#.###########.#.#.###
+#.......#.....#...#.#.....#.#.......###...#.........#.......#...#...###...#...###...#...#...#...#.....#...........#...#.#.#...........#.#...#
+#######.#####.#.###.#.#####.#.#############.#######.#.#######.#########.#.#.###########.#.#########################.#.#.#.#.###########.###.#
+#...###.#.....#...#...#...#.#...#...#.....#.#.......#.....#...###...#...#.#...#######...#.###.................#...#.#...#.#...#...#.....#...#
+#.#.###.#.#######.#####.#.#.###.#.#.#.###.#.#.###########.#.#####.#.#.###.###.#######.###.###.###############.#.#.#.#####.###.#.#.#.#####.###
+#.#.....#.....###...#...#...###...#...#...#.#.....###...#.#...#...#.#...#.....#######...#.#...#.......#.....#.#.#...#...#.#...#.#...#...#...#
+#.###########.#####.#.#################.###.#####.###.#.#.###.#.###.###.###############.#.#.###.#####.#.###.#.#.#####.#.#.#.###.#####.#.###.#
+#...#.......#.#...#...###...#...#.......###.#.....#...#.#.....#...#.#...#.....#######...#.#...#.#.....#.#...#...#.....#...#.....#.....#.....#
+###.#.#####.#.#.#.#######.#.#.#.#.#########.#.#####.###.#########.#.#.###.###.#######.###.###.#.#.#####.#.#######.###############.###########
+#...#.#...#.#.#.#.........#.#.#.#.......#...#.....#...#.#...#...#.#...#...#...#######...#.###...#.......#.........#.......#.....#...........#
+#.###.#.#.#.#.#.###########.#.#.#######.#.#######.###.#.#.#.#.#.#.#####.###.###########.#.#########################.#####.#.###.###########.#
+#.#...#.#...#...#.........#...#.........#.#.....#...#.#.#.#.#.#.#.#...#...#...#...###E#...#...###...........#.....#.....#.#...#.#.....#.....#
+#.#.###.#########.#######.###############.#.###.###.#.#.#.#.#.#.#.#.#.###.###.#.#.###.#####.#.###.#########.#.###.#####.#.###.#.#.###.#.#####
+#...###.....#...#.#...###.................#.###.....#.#...#.#.#.#...#.#...#...#.#.#...#.....#.#...#...#...#...###.......#.#...#.#...#.#.....#
+###########.#.#.#.#.#.#####################.#########.#####.#.#.#####.#.###.###.#.#.###.#####.#.###.#.#.#.###############.#.###.###.#.#####.#
+#...###...#...#...#.#.#...#...#...#...#...#...#.......#...#...#.....#...###...#.#...###.....#.#...#.#...#.......#.......#.#...#...#.#...#...#
+#.#.###.#.#########.#.#.#.#.#.#.#.#.#.#.#.###.#.#######.#.#########.#########.#.###########.#.###.#.###########.#.#####.#.###.###.#.###.#.###
+#.#.#...#...#...#...#...#...#...#...#...#...#...#.....#.#.........#.#.....###...#.....#...#.#.###...#...........#.#.....#.....#...#...#...###
+#.#.#.#####.#.#.#.#########################.#####.###.#.#########.#.#.###.#######.###.#.#.#.#.#######.###########.#.###########.#####.#######
+#.#.#.....#.#.#.#.......................###.#.....###.#.........#...#...#.......#...#.#.#...#.#...###.............#.....###...#...#...#...###
+#.#.#####.#.#.#.#######################.###.#.#######.#########.#######.#######.###.#.#.#####.#.#.#####################.###.#.###.#.###.#.###
+#.#.#...#.#...#.......................#...#...#.....#...........#...#...#.......#...#.#.....#.#.#.#...###.....#.......#.....#...#...#...#...#
+#.#.#.#.#.###########################.###.#####.###.#############.#.#.###.#######.###.#####.#.#.#.#.#.###.###.#.#####.#########.#####.#####.#
+#.#...#...#...#.......#.....#...#...#.....#...#.#...###...#...###.#.#...#.....###...#.###...#...#...#.....###.#.....#...#...#...#...#...#...#
+#.#########.#.#.#####.#.###.#.#.#.#.#######.#.#.#.#####.#.#.#.###.#.###.#####.#####.#.###.###################.#####.###.#.#.#.###.#.###.#.###
+#...#.....#.#.#.#.....#.#...#.#...#.....###.#.#.#.......#.#.#.#...#...#.#.....#...#.#.....#.....#...#.......#.#...#.###...#...#...#.....#...#
+###.#.###.#.#.#.#.#####.#.###.#########.###.#.#.#########.#.#.#.#####.#.#.#####.#.#.#######.###.#.#.#.#####.#.#.#.#.###########.###########.#
+#...#...#.#.#.#.#...#...#...#.#.........#...#...#...#.....#.#.#.....#.#.#.#...#.#.#.......#...#...#.#.#.....#...#.#.#...#...#...#...#.......#
+#.#####.#.#.#.#.###.#.#####.#.#.#########.#######.#.#.#####.#.#####.#.#.#.#.#.#.#.#######.###.#####.#.#.#########.#.#.#.#.#.#.###.#.#.#######
+#.......#...#...###...#####...#...........#...#...#...###...#...###.#.#.#.#.#...#...#.....#...#...#...#...#...###.#...#...#...#...#.#.......#
+###########################################.#.#.#########.#####.###.#.#.#.#.#######.#.#####.###.#.#######.#.#.###.#############.###.#######.#
+#.........#.....###.....#.......#.......#...#.#.#...#...#.....#.....#.#.#.#.#.......#.......###.#...#...#...#...#...............###.#.......#
+#.#######.#.###.###.###.#.#####.#.#####.#.###.#.#.#.#.#.#####.#######.#.#.#.#.#################.###.#.#.#######.###################.#.#######
+#.......#.#...#.....#...#.....#.#.....#.#...#...#.#.#.#.#...#.......#.#.#.#.#.....#.....#.....#...#.#.#.......#...................#...###...#
+#######.#.###.#######.#######.#.#####.#.###.#####.#.#.#.#.#.#######.#.#.#.#.#####.#.###.#.###.###.#.#.#######.###################.#######.#.#
+#.......#.###.......#.#...#...#.......#.....#...#.#.#.#.#.#...#.....#...#.#.#.....#...#.#...#.###.#.#.......#.#...............#...###...#.#.#
+#.#######.#########.#.#.#.#.#################.#.#.#.#.#.#.###.#.#########.#.#.#######.#.###.#.###.#.#######.#.#.#############.#.#####.#.#.#.#
+#.......#.#...#.....#...#...#.............###.#...#...#.#...#.#.........#.#.#.....#...#.#...#.....#.....#...#...#.......#...#...#...#.#...#.#
+#######.#.#.#.#.#############.###########.###.#########.###.#.#########.#.#.#####.#.###.#.#############.#.#######.#####.#.#.#####.#.#.#####.#
+#...#...#...#...#.............#...........#...#.......#.#...#.#...#...#.#.#.#.....#...#...#.....#.....#...###.....#.....#.#...#...#.#.#.....#
+#.#.#.###########.#############.###########.###.#####.#.#.###.#.#.#.#.#.#.#.#.#######.#####.###.#.###.#######.#####.#####.###.#.###.#.#.#####
+#.#...#.......#...###...........#...#...###...#.....#.#.#...#.#.#.#.#...#...#...#...#...#...###...#...#.......#.....#.....#...#.#...#.#.#...#
+#.#####.#####.#.#####.###########.#.#.#.#####.#####.#.#.###.#.#.#.#.###########.#.#.###.#.#########.###.#######.#####.#####.###.#.###.#.#.#.#
+#...#...#.....#.#...#...........#.#.#.#.....#.#.....#...###.#.#.#.#...#...#...#.#.#...#...#.......#.....#...#...#...#.#.....#...#.....#...#.#
+###.#.###.#####.#.#.###########.#.#.#.#####.#.#.###########.#.#.#.###.#.#.#.#.#.#.###.#####.#####.#######.#.#.###.#.#.#.#####.#############.#
+#...#.#...#...#.#.#.#.........#...#...#.....#.#...#...###...#.#.#...#...#.#.#...#.#...#...#.....#.........#...###.#...#.......#...#...#...#.#
+#.###.#.###.#.#.#.#.#.#######.#########.#####.###.#.#.###.###.#.###.#####.#.#####.#.###.#.#####.#################.#############.#.#.#.#.#.#.#
+#...#.#...#.#.#.#.#...#.....#...#.......#...#.#...#.#.#...#...#.#...#.....#...#...#...#.#.#...#...#.............#...#...........#.#.#.#.#.#.#
+###.#.###.#.#.#.#.#####.###.###.#.#######.#.#.#.###.#.#.###.###.#.###.#######.#.#####.#.#.#.#.###.#.###########.###.#.###########.#.#.#.#.#.#
+###...#...#.#.#.#.#...#...#...#.#.........#.#.#...#.#.#...#...#.#...#.......#.#.....#.#.#.#.#.###...###.........#...#...........#...#.#.#...#
+#######.###.#.#.#.#.#.###.###.#.###########.#.###.#.#.###.###.#.###.#######.#.#####.#.#.#.#.#.#########.#########.#############.#####.#.#####
+###...#.....#...#...#.....#...#.............#.#...#.#.###.#...#...#.###...#.#.#...#.#.#.#.#.#.#...#...#...........#.......#...#...###.#.....#
+###.#.#####################.#################.#.###.#.###.#.#####.#.###.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#############.#####.#.#.###.###.#####.#
+#...#.......###.......#...#.........#.......#.#.#...#...#.#...#...#...#.#.#.#.#.#.#.#.#.#.#.#.#.#...#.#.....#.......#...#...#...#...#.......#
+#.#########.###.#####.#.#.#########.#.#####.#.#.#.#####.#.###.#.#####.#.#.#.#.#.#.#.#.#.#.#.#.#.#####.#.###.#.#######.#.#######.###.#########
+#.........#.....#...#...#.........#.#...###.#.#...#...#.#...#.#.#.....#.#...#.#.#...#.#.#...#.#.###...#.#...#.........#.......#...#.#.......#
+#########.#######.#.#############.#.###.###.#.#####.#.#.###.#.#.#.#####.#####.#.#####.#.#####.#.###.###.#.###################.###.#.#.#####.#
+###.....#.......#.#.............#...#...#...#.......#.#...#.#...#...#...#.....#.#.....#.#.....#...#...#.#...#...#...........#.#...#...#.....#
+###.###.#######.#.#############.#####.###.###########.###.#.#######.#.###.#####.#.#####.#.#######.###.#.###.#.#.#.#########.#.#.#######.#####
+#...#...#.....#...###...........#.....#...#.....#.....###.#.....###.#.###...#...#.#...#.#...#.....#...#...#.#.#.#.....#...#...#.......#.....#
+#.###.###.###.#######.###########.#####.###.###.#.#######.#####.###.#.#####.#.###.#.#.#.###.#.#####.#####.#.#.#.#####.#.#.###########.#####.#
+#...#...#...#.#.......#.....#...#.#.....#...###.#.......#...#...#...#.....#.#...#.#.#...###.#...###...#...#...#.#...#...#...........#...#...#
+###.###.###.#.#.#######.###.#.#.#.#.#####.#####.#######.###.#.###.#######.#.###.#.#.#######.###.#####.#.#######.#.#.###############.###.#.###
+#...#...#...#...#...#...#...#.#.#.#.....#.....#...#.....###...###.#.....#.#...#.#.#.......#...#...#...#.#...###...#...#.....#.......#...#...#
+#.###.###.#######.#.#.###.###.#.#.#####.#####.###.#.#############.#.###.#.###.#.#.#######.###.###.#.###.#.#.#########.#.###.#.#######.#####.#
+#...#.....#...#...#.#.###...#.#...#...#.#...#.#...#.......#.......#...#.#.#...#.#.#.....#...#.#...#...#...#.....#.....#...#.#.......#...#...#
+###.#######.#.#.###.#.#####.#.#####.#.#.#.#.#.#.#########.#.#########.#.#.#.###.#.#.###.###.#.#.#####.#########.#.#######.#.#######.###.#.###
+###...#...#.#.#.###...#.....#...#...#...#.#...#...#...#...#...#...#...#.#.#...#.#...###...#.#...#...#...#.......#.#.......#.#.......#...#...#
+#####.#.#.#.#.#.#######.#######.#.#######.#######.#.#.#.#####.#.#.#.###.#.###.#.#########.#.#####.#.###.#.#######.#.#######.#.#######.#####.#
+#.....#.#.#.#.#.#.....#.....#...#...#...#.....###...#.#.....#.#.#.#.###...#...#.....#.....#...#...#.....#.......#.#.....#...#.....###.......#
+#.#####.#.#.#.#.#.###.#####.#.#####.#.#.#####.#######.#####.#.#.#.#.#######.#######.#.#######.#.###############.#.#####.#.#######.###########
+#...#...#.#.#...#...#.#.....#.#####...#.#...#.....###.#.....#...#.#...#.....#.......#.......#.#.#...#...#.......#...#...#.........#.........#
+###.#.###.#.#######.#.#.#####.#########.#.#.#####.###.#.#########.###.#.#####.#############.#.#.#.#.#.#.#.#########.#.#############.#######.#
+###.#...#.#.#.......#...#...#...#.......#.#.#.....#...#...#.......#...#.....#.....#.........#.#.#.#.#.#.#.......#...#.........###...#...#...#
+###.###.#.#.#.###########.#.###.#.#######.#.#.#####.#####.#.#######.#######.#####.#.#########.#.#.#.#.#.#######.#.###########.###.###.#.#.###
+#...#...#...#.....#...#...#...#.#...#...#.#.#.....#.#...#.#.........#...###.#...#.#.#.......#.#...#.#.#.#.......#.....#.....#.....#...#.#...#
+#.###.###########.#.#.#.#####.#.###.#.#.#.#.#####.#.#.#.#.###########.#.###.#.#.#.#.#.#####.#.#####.#.#.#.###########.#.###.#######.###.###.#
+#...#.....#####...#.#.#.....#.#.#...#.#.#.#...#...#...#.#.....#.......#.....#.#.#.#...#.....#...#...#.#.#...........#.#...#.#...#...#...#...#
+###.#####.#####.###.#.#####.#.#.#.###.#.#.###.#.#######.#####.#.#############.#.#.#####.#######.#.###.#.###########.#.###.#.#.#.#.###.###.###
+#...#...#...#...#...#.....#.#...#...#.#.#.###.#.......#...#...#.....#...#...#.#.#.....#.#...#...#...#.#.#.....#...#.#.#...#...#...###.#...###
+#.###.#.###.#.###.#######.#.#######.#.#.#.###.#######.###.#.#######.#.#.#.#.#.#.#####.#.#.#.#.#####.#.#.#.###.#.#.#.#.#.#############.#.#####
+#.....#.....#...#.......#.#.#.......#.#...#...#...#...###.#...#.....#.#...#.#.#.#.....#...#.#.#...#...#.#...#.#.#.#.#.#.............#...#...#
+###############.#######.#.#.#.#######.#####.###.#.#.#####.###.#.#####.#####.#.#.#.#########.#.#.#.#####.###.#.#.#.#.#.#############.#####.#.#
+###...#.........#...#...#...#.....#...###...#...#...###...#...#.#...#...#...#.#.#...#.......#...#.###...#...#.#.#.#.#.#...#...#...#.....#.#.#
+###.#.#.#########.#.#.###########.#.#####.###.#########.###.###.#.#.###.#.###.#.###.#.###########.###.###.###.#.#.#.#.#.#.#.#.#.#.#####.#.#.#
+#...#...#.....#...#.#...#.........#.....#...#.........#...#...#.#.#...#.#...#.#...#.#.#.....#...#.#...#...#...#.#.#.#.#.#.#.#.#.#.#...#...#.#
+#.#######.###.#.###.###.#.#############.###.#########.###.###.#.#.###.#.###.#.###.#.#.#.###.#.#.#.#.###.###.###.#.#.#.#.#.#.#.#.#.#.#.#####.#
+#.........###...###.....#...............###...........###.....#...###...###...###...#...###...#...#.....###.....#...#...#...#...#...#.......#
+#############################################################################################################################################

src/holt59/aoc/inputs/holt59/2024/day21.txt

@@ -0,0 +1,5 @@
+129A
+540A
+789A
+596A
+582A

src/holt59/aoc/inputs/tests/2024/day18.txt

@@ -0,0 +1,25 @@
+5,4
+4,2
+4,5
+3,0
+2,1
+6,3
+2,4
+1,5
+0,6
+3,3
+2,6
+5,1
+1,2
+5,5
+2,5
+6,5
+1,4
+0,4
+6,4
+1,1
+6,1
+1,0
+0,5
+1,6
+2,0

src/holt59/aoc/inputs/tests/2024/day19.txt

@@ -0,0 +1,10 @@
+r, wr, b, g, bwu, rb, gb, br
+
+brwrr
+bggr
+gbbr
+rrbgbr
+ubwu
+bwurrg
+brgr
+bbrgwb

src/holt59/aoc/inputs/tests/2024/day20.txt

@@ -0,0 +1,15 @@
+###############
+#...#...#.....#
+#.#.#.#.#.###.#
+#S#...#.#.#...#
+#######.#.#.###
+#######.#.#...#
+#######.#.###.#
+###..E#...#...#
+###.#######.###
+#...###...#...#
+#.#####.#.###.#
+#.#...#.#.#...#
+#.#.#.#.#.#.###
+#...#...#...###
+###############

src/holt59/aoc/inputs/tests/2024/day21.txt

@@ -0,0 +1,5 @@
+029A
+980A
+179A
+456A
+379A

src/holt59/aoc/inputs/tests/2024/day22.txt

@@ -0,0 +1,4 @@
+1
+10
+100
+2024

src/holt59/aoc/inputs/tests/2024/day22_p2.txt

@@ -0,0 +1,4 @@
+1
+2
+3
+2024

src/holt59/aoc/inputs/tests/2024/day23.txt

@@ -0,0 +1,32 @@
+kh-tc
+qp-kh
+de-cg
+ka-co
+yn-aq
+qp-ub
+cg-tb
+vc-aq
+tb-ka
+wh-tc
+yn-cg
+kh-ub
+ta-co
+de-co
+tc-td
+tb-wq
+wh-td
+ta-ka
+td-qp
+aq-cg
+wq-ub
+ub-vc
+de-ta
+wq-aq
+wq-vc
+wh-yn
+ka-de
+kh-ta
+co-tc
+wh-qp
+tb-vc
+td-yn

src/holt59/aoc/tools/graphs.py

@@ -0,0 +1,186 @@
+import heapq
+from typing import (
+    Callable,
+    Iterable,
+    Iterator,
+    Mapping,
+    TypeVar,
+    cast,
+    overload,
+)
+
+_Node = TypeVar("_Node")
+
+
+def make_neighbors_grid_fn(
+    rows: int | Iterable[int],
+    cols: int | Iterable[int],
+    excluded: Iterable[tuple[int, int]] = set(),
+    diagonals: bool = False,
+):
+    """
+    Create a neighbors function suitable for graph function for a simple grid.
+
+    Args:
+        rows: Rows of the grid. If an int is specified, the rows are assumed to be
+            numbered from 0 to rows - 1, otherwise the iterable should contain the list
+            of valid rows.
+        cols: Columns of the grid. If an int is specified, the columns are assumed to be
+            numbered from 0 to cols - 1, otherwise the iterable should contain the list
+            of valid columns.
+        excluded: Cells of the grid that cannot be used as valid nodes for the graph.
+        diagonals: If True, neighbors will include diagonal cells, otherwise, only
+            horizontal and vertical neighbors will be included.
+
+    """
+    ds = ((-1, 0), (0, 1), (1, 0), (0, -1))
+    if diagonals:
+        ds = ds + ((-1, -1), (-1, 1), (1, -1), (1, 1))
+
+    if isinstance(rows, int):
+        rows = range(rows)
+    elif not isinstance(rows, range):
+        rows = set(rows)
+
+    if isinstance(cols, int):
+        cols = range(cols)
+    elif not isinstance(cols, range):
+        cols = set(cols)
+
+    excluded = set(excluded)
+
+    def _fn(node: tuple[int, int]):
+        return (
+            ((row_n, col_n), 1)
+            for dr, dc in ds
+            if (row_n := node[0] + dr) in rows
+            and (col_n := node[1] + dc) in cols
+            and (row_n, col_n) not in excluded
+        )
+
+    return _fn
+
+
+@overload
+def dijkstra(
+    start: _Node,
+    target: None,
+    neighbors: Callable[[_Node], Iterable[tuple[_Node, float]]],
+) -> dict[_Node, tuple[tuple[_Node, ...], float]]: ...
+
+
+@overload
+def dijkstra(
+    start: _Node,
+    target: _Node,
+    neighbors: Callable[[_Node], Iterable[tuple[_Node, float]]],
+) -> tuple[tuple[_Node, ...], float] | None: ...
+
+
+def dijkstra(
+    start: _Node,
+    target: _Node | None,
+    neighbors: Callable[[_Node], Iterable[tuple[_Node, float]]],
+) -> (
+    dict[_Node, tuple[tuple[_Node, ...], float]]
+    | tuple[tuple[_Node, ...], float]
+    | None
+):
+    """
+    Solve shortest-path problem using simple Dijkstra algorithm from start to target,
+    using the given neighbors function.
+
+    Args:
+        start: Starting node of the path.
+        target: Target node for the path.
+        neighbors: Function that should return, for a given node, the list of
+            its neighbors with the cost to go from the node to the neighbor.
+
+    Returns:
+        One of the shortest-path from start to target with its associated cost, if one
+        is found, otherwise None.
+    """
+    queue: list[tuple[float, _Node, tuple[_Node, ...]]] = [(0, start, (start,))]
+    preds: dict[_Node, tuple[tuple[_Node, ...], float]] = {}
+
+    while queue:
+        dis, node, path = heapq.heappop(queue)
+
+        if node in preds:
+            continue
+
+        preds[node] = (path, dis)
+
+        if node == target:
+            break
+
+        for neighbor, cost in neighbors(node):
+            if neighbor in preds:
+                continue
+
+            heapq.heappush(queue, (dis + cost, neighbor, path + (neighbor,)))
+
+    if target is None:
+        return preds
+
+    return preds.get(target, None)
+
+
+def iter_max_cliques(
+    neighbors: Mapping[_Node, Iterable[_Node]], nodes: Iterable[_Node] | None = None
+) -> Iterator[list[_Node]]:
+    """
+    Find max cliques from the given set of neighbors containing the given set of nodes.
+
+    This is simply the networkx implementation with typing (and using a simple mapping
+    to avoid requiring networkx).
+    """
+    if len(neighbors) == 0:
+        return
+
+    # remove the node itself from the neighbors
+    adj = {u: {v for v in neighbors[u] if v != u} for u in neighbors}
+
+    # Initialize Q with the given nodes and subg, cand with their nbrs
+    Q: list[_Node | None] = list(nodes or [])
+    cand = set(neighbors)
+    for node in Q:
+        if node not in cand:
+            raise ValueError(f"The given `nodes` {nodes} do not form a clique")
+        cand &= adj[node]
+
+    if not cand:
+        yield cast(list[_Node], Q[:])
+        return
+
+    subg = cand.copy()
+    stack: list[tuple[set[_Node], set[_Node], set[_Node]]] = []
+    Q.append(None)
+
+    u = max(subg, key=lambda u: len(cand & adj[u]))
+    ext_u = cand - adj[u]
+
+    try:
+        while True:
+            if ext_u:
+                q = ext_u.pop()
+                cand.remove(q)
+                Q[-1] = q
+                adj_q = adj[q]
+                subg_q = subg & adj_q
+                if not subg_q:
+                    yield cast(list[_Node], Q[:])
+                else:
+                    cand_q = cand & adj_q
+                    if cand_q:
+                        stack.append((subg, cand, ext_u))
+                        Q.append(None)
+                        subg = subg_q
+                        cand = cand_q
+                        u = max(subg, key=lambda u: len(cand & adj[u]))
+                        ext_u = cand - adj[u]
+            else:
+                Q.pop()
+                subg, cand, ext_u = stack.pop()
+    except IndexError:
+        pass