5 files changed, 196 insertions, 55 deletions

diff --git a/aoc/mixins.py b/aoc/mixins.py
new file mode 100644
index 0000000..faeb3eb
--- /dev/null
+++ b/aoc/mixins.py
@@ -0,0 +1,57 @@
+# -*- coding: utf-8 -*-
+from math import floor, inf
+from typing import Tuple, TypeVar, Generic, Callable, Iterator, List, Dict
+
+Node = TypeVar("Node")
+
+
+class AStarMixin(Generic[Node]):
+    def _gen_path(self, current: Node, came_from: Dict[Node, Node]) -> List[Node]:
+        print("GENPATH")
+        path = [current]
+
+        while current in came_from:
+            current = came_from[current]
+            path = [current, *path]
+
+        return path
+
+    def a_star(
+        self,
+        start: Node,
+        end: Callable[[Node, Callable[[], List[Node]]], bool],
+        neighbours: Callable[[Node], Iterator[Node]],
+        distance: Callable[[Node, Node], int] = lambda a, b: 1,
+        heuristic: Callable[[Node], int] = lambda a: 0,
+    ) -> List[Node]:
+        open_nodes = {start}
+        came_from = {}
+
+        g_scores = {start: 0}
+
+        f_scores = {start: heuristic(start)}
+
+        while True:
+            try:
+                current = sorted(
+                    [item for item in open_nodes],
+                    key=lambda item: f_scores.get(item, inf),
+                )[0]
+            except IndexError:
+                raise RuntimeError("No path found")
+
+            if end(current, lambda: self._gen_path(current, came_from)):
+                return self._gen_path(current, came_from)
+
+            open_nodes.remove(current)
+
+            for neighbour in neighbours(current):
+                g_score = g_scores.get(current, inf) + distance(current, neighbour)
+
+                if g_score < g_scores.get(neighbour, inf):
+                    came_from[neighbour] = current
+                    g_scores[neighbour] = g_score
+                    f_scores[neighbour] = g_score + heuristic(neighbour)
+
+                    if neighbour not in open_nodes:
+                        open_nodes.add(neighbour)
diff --git a/day12/__init__.py b/day12/__init__.py
index 69f9458..ef03ee0 100644
--- a/day12/__init__.py
+++ b/day12/__init__.py
@@ -5,6 +5,7 @@ from math import inf, sqrt, floor
 from typing import List, Tuple, Iterator, Callable, Any
 
 from aoc import BaseAssignment
+from aoc.mixins import AStarMixin
 
 
 class Map:
@@ -57,7 +58,7 @@ class Map:
         return elevation - 96
 
 
-class Assignment(BaseAssignment, ABC):
+class Assignment(BaseAssignment, AStarMixin[Tuple[int, int]], ABC):
     def distance(self, map: Map, a: Tuple[int, int], b: Tuple[int, int]):
         distance = map.elevation(*b) - map.elevation(*a)
 
@@ -66,67 +67,22 @@ class Assignment(BaseAssignment, ABC):
 
         return 1
 
+
+class AssignmentOne(Assignment):
+    example_result = 31
+
     def heuristic(self, map: Map, a: Tuple[int, int]):
         dx = abs(map.start[0] - a[0])
         dy = abs(map.start[1] - a[1])
         return floor(sqrt(dx**2 + dy**2))
 
-    def a_star(
-        self,
-        map: Map,
-        start: Tuple[int, int],
-        end: Callable[[int, int], bool],
-        distance: Callable[[Tuple[int, int], Tuple[int, int]], int],
-        heuristic: Callable[[Tuple[int, int]], int],
-    ) -> List[Tuple[int, int]]:
-        open = {start}
-        came_from = {}
-
-        g_scores = {start: 0}
-
-        f_scores = {start: heuristic(start)}
-
-        while True:
-            try:
-                current = sorted(
-                    [item for item in open], key=lambda item: f_scores.get(item, inf)
-                )[0]
-            except IndexError:
-                raise RuntimeError("No path found")
-
-            if end(*current):
-                path = [current]
-
-                while current in came_from:
-                    current = came_from[current]
-                    path = [current, *path]
-
-                return path
-
-            open.remove(current)
-
-            for neighbour in map.neighbours(*current):
-                g_score = g_scores.get(current, inf) + distance(current, neighbour)
-
-                if g_score < g_scores.get(neighbour, inf):
-                    came_from[neighbour] = current
-                    g_scores[neighbour] = g_score
-                    f_scores[neighbour] = g_score + heuristic(neighbour)
-
-                    if neighbour not in open:
-                        open.add(neighbour)
-
-
-class AssignmentOne(Assignment):
-    example_result = 31
-
     def run(self, input: Iterator) -> Any:
         map = Map(map=list(input))
 
         path = self.a_star(
-            map,
             map.start,
-            lambda x, y: (x, y) == map.end,
+            lambda coordinate, _: coordinate == map.end,
+            neighbours=lambda a: map.neighbours(*a),
             distance=lambda a, b: self.distance(map, a, b),
             heuristic=lambda a: self.heuristic(map, a),
         )
@@ -141,11 +97,10 @@ class AssignmentTwo(Assignment):
         map = Map(list(input))
 
         path = self.a_star(
-            map,
             map.end,
-            lambda x, y: map.elevation(x, y) == 1,
+            lambda coordinate, _: map.elevation(*coordinate) == 1,
+            neighbours=lambda a: map.neighbours(*a),
             distance=lambda a, b: self.distance(map, b, a),
-            heuristic=lambda a: 1,
         )
 
         return len(path) - 1
diff --git a/day16/__init__.py b/day16/__init__.py
new file mode 100644
index 0000000..ecf33c5
--- /dev/null
+++ b/day16/__init__.py
@@ -0,0 +1,60 @@
+# -*- coding: utf-8 -*-
+import re
+from abc import ABC
+from dataclasses import dataclass
+from typing import List, Iterator, Dict
+
+from aoc import BaseAssignment
+from aoc.mixins import AStarMixin
+
+
+@dataclass
+class Valve:
+    name: str
+    flow_rate: int
+    tunnels_to: List[str]
+
+    def __hash__(self):
+        return hash(self.name)
+
+
+valve_pattern = re.compile(
+    "Valve (\w+) has flow rate=(\d+); tunnels? leads? to valves? (.*)"
+)
+
+
+class Assignment(BaseAssignment[int, Valve], AStarMixin[Valve], ABC):
+    def parse_item(self, item: str) -> Valve:
+        match = valve_pattern.match(item)
+        name, flow_rate, tunnels_to = match.groups()
+
+        return Valve(
+            name=name,
+            tunnels_to=tunnels_to.split(", "),
+            flow_rate=int(flow_rate),
+        )
+
+    @staticmethod
+    def valve_map(input: Iterator[Valve]) -> Dict[str, Valve]:
+        return {valve.name: valve for valve in input}
+
+
+class AssignmentOne(Assignment):
+    example_result = 1651
+
+    def run(self, input: Iterator[Valve]) -> int:
+        valves = self.valve_map(input)
+
+        queue = [valves["AA"]]
+        open = {}
+        minutes = 30
+
+        while len(queue) > 0 or minutes > 0:
+            valve = queue.pop(0)
+
+            for v in valve.tunnels_to:
+                pass
+
+
+class AssignmentTwo(Assignment):
+    pass