Day12 [Wip]

4 files changed, 210 insertions, 0 deletions

diff --git a/day12/__init__.py b/day12/__init__.py
new file mode 100644
index 0000000..52fa2e7
--- /dev/null
+++ b/day12/__init__.py
@@ -0,0 +1,137 @@
+# -*- coding: utf-8 -*-
+import sys
+from abc import ABC
+from math import inf, sqrt, floor
+from typing import List, Tuple, Iterator, Callable, Any
+
+from aoc import BaseAssignment
+
+
+class Map:
+    def __init__(self, map: List[str]):
+        self.map = map
+
+        self.height = len(map)
+        self.width = len(map[0])
+
+        self.start = self.find_unique_position("S")
+        self.end = self.find_unique_position("E")
+
+    def find_unique_position(self, value: str) -> Tuple[int, int]:
+        for y in range(self.height):
+            for x in range(self.width):
+                if self.map[y][x] == value:
+                    return x, y
+
+    def neighbours(self, x: int, y: int) -> Iterator[Tuple[int, int]]:
+        for dy in range(max(0, y - 1), min(self.height, y + 2)):
+            for dx in range(max(0, x - 1), min(self.width, x + 2)):
+                current_elevation = self.elevation(x, y)
+                neigbour_elevation = self.elevation(dx, dy)
+
+                if (
+                    (dy == y and dx == x)
+                    or (dy == y - 1 and dx == x - 1)
+                    or (dy == y - 1 and dx == x + 1)
+                    or (dy == y + 1 and dx == x - 1)
+                    or (dy == y + 1 and dx == x + 1)
+                    or (abs(neigbour_elevation - current_elevation) > 1)
+                ):
+                    continue
+                yield dx, dy
+
+    def elevation(self, x: int, y: int):
+        character = self.map[y][x]
+
+        match character:
+            case "S":
+                elevation = ord("a")
+            case "E":
+                elevation = ord("z")
+            case _:
+                elevation = ord(character)
+
+        return elevation - 96
+
+
+class Assignment(BaseAssignment, ABC):
+    def distance(self, map: Map, a: Tuple[int, int], b: Tuple[int, int]):
+        distance = abs(map.elevation(*a) - map.elevation(*b))
+
+        if distance > 1:
+            return inf
+
+        return distance
+
+    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: Tuple[int, int],
+        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 current == end:
+                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))
+
+        print(map.start, map.end)
+
+        path = self.a_star(
+            map,
+            map.start,
+            map.end,
+            distance=lambda a, b: self.distance(map, a, b),
+            heuristic=lambda a: self.heuristic(map, a),
+        )
+
+        return len(path) - 1
+
+
+class AssignmentTwo(Assignment):
+    pass
diff --git a/day12/example.txt b/day12/example.txt
new file mode 100644
index 0000000..86e9cac
--- /dev/null
+++ b/day12/example.txt
@@ -0,0 +1,5 @@
+Sabqponm
+abcryxxl
+accszExk
+acctuvwj
+abdefghi
diff --git a/day12/input.txt b/day12/input.txt
new file mode 100644
index 0000000..7fc8957
--- /dev/null
+++ b/day12/input.txt
@@ -0,0 +1,41 @@
+abcccccccccccccccccccccccccccccccccccccccccccccccccccaaaaacccccccccccccaaaaaaaccccccccccccccccaaaaaaccccccccccccccccccccccccccaaaaacccaaaccccccccccccccccccccccccccccccaaaaa
+abcccccccccaaaccccccccccccaaaccccccccccccccccccccccccaaaaaacccccccccccccaaaaaaaaaaaccaaaaccccaaaaaaacccccccccccccccccccccccccccaaaaaacaaaaccccccccccccccccccccccccccccccaaaa
+abcccccccccaaaaaacccccccccaaaacccccccccccccccccccccccaaaaaaccccccccccccaaaaaaaaaaaccaaaaacccaaaaaacccccccccaaacccccccccccccccaaaaaaaacaaaaccccccccccccccccacccccccccccccaaaa
+abcccccccccaaaaaacccccccccaaaaccccaacccccccccccccccccaaaaaaccccccccccaaaaaaaaaaaaaacaaaaaaccaacaaaccaacccaaaaaaccccccccccccccaaaaaaaacaaaccccccccccaccccaaaccccccccccccaaaaa
+abcccccccaaaaaaaccccccccccaaaacccaaaaccccccccccccaaccccaaacccccccaaacaaaaaaaaaccccccaaaaaacccccaaaccaacccaaaaaacccccccccccccccccaaccccccccccccccccaaacccaaaccccccccccccaaaca
+abcccccccaaaaaaacccccccaaacccccccaaaacccccccaaccaaaccccccccccccaaaaacaaaaaaaaaccccccaaaaaccccccccaaaaaaaacaaaaaccaacaaccccccccccaaccccccccccccccccaaaaaaaaaccccccccccccccccc
+abcccccccccaaaaaaccaaccaaacccccccaaaacccccccaaaaaaaccccccccccccaaaaaaccccaaaaaacccccccaaaccccccccaaaaaaaaaaaaacccaaaaacccccccaaaccccccccccccccccccaaaaaaaackcccccccccccccccc
+abcccccccccaaaaaaccaaaaaaaccccccccccccccccccaaaaaacccccccccccccaaaaaaccccaaaaaaccccccccccccccccccccaaaaccaaaaaccccaaaaaccccccaaaaaccccaaaaaccccccccaaaajjkkkkkccccccaacccccc
+abcccccccccaaccccccaaaaaaccccccccccccccccccccaaaaaaaaccccccccccaaaaacccaaaacaaccccccccccccccccccccaaaaaccccccccccaaaaaacccccaaaaaaccccaaaaaccciijjjjjjjjjkkkkkkccaaaaaaccccc
+abcaaaccccccccccccccaaaaaaaaccccccccccccccccaaaaaaaaacccccccccccaaaacccaaaccaaccccccccccccccccccccaacaaacccccccccaaaacccccccaaaaaacccaaaaaaciiiijjjjjjjjjoopkkkkcaaaaacccccc
+abaaaacccccccccccccaaaaaaaaaccccccccccccccccaaaaaaaacccccccccccccccccccaaaaaaaccccaccaccccccccccccacccaacccccccccccaaccccccccaaaaacccaaaaaaiiiiiijjjjjjoooppppkkcaaaaaaacccc
+abaaaaaccccccccccccaaaaaaaaccccccccccccccccaaaaaaaccccccccccccccccccccccaaaaaaccccaaaacccccccccccccccccccccccccccccccccccccccaaaaccccaaaaaiiiinnnoooooooooppppkkkaaaaaaacccc
+abaaaaacccccccccccaaaaaaaccccccccccccccccccccccaaacccccccccccccccccccaaaaaaaacccccaaaaccccccccccccaaccaacccccaccccacccccccccccccccccccaaaciiinnnnoooooooouupppkkkaaaaaaacccc
+abaaaaccccccccccccccccaaaccccccccccccccccccccccaaacccccccaaccccccccccaaaaaaaaacccaaaaaacccccccccccaaaaaaccccaaaaaaaacccccccccccccaaccccccciiinnnntttooouuuuupppiiacaaacccccc
+abaaaacccccccccccccccccaaccccccccccccccccccccccccccccccaaaacacccccccccaaaaaaaacccaaaaaacccccccccccaaaaaccccccaaaaaacccccccccccaaaaaacccccciinnnttttuuuuuuuuuuppiiccaaacccccc
+abcccccccccccccccccccccccccccccccccccccccccccccccccccccaaaaaacccccccccccaaaaaaaccccaacccccaaccccccaaaaaacccccaaaaaacccccccccccaaaaaccccccciinnntttttuuuuxyuuuppiiicccccccccc
+abccccccccccccccccccccccccccccccccccccaaacccccccaaccccccaaaaccccccccccccaaccccccccccccccccaacaaacaaaaaaaacccaaaaaaaaccccccccccaaaaaaaccccchinnnttxxxxuuxyyyuuppiiiiccccccccc
+abccccccccccccccccccccccccccccccccccccaaaaaaccccaaacccccaaaaccccccccccccaaccccccccccccccccaaaaaccaaaaaaaaccaaaaaaaaaaccccccccaaaaaaaaccccchhhnnttxxxxxxxyyuvppppiiiccccccccc
+abccccccccccccccccccccccccccccccccccaaaaaaaaaaccaaaaaaacacaacccccccccccccccccaaaccccccccaaaaaaccccccaacccccaaaaaaaaaaccccccccaaaaaaaaccccchhhnntttxxxxxxyyvvvppqqiiicccccccc
+abccccccccccccccccccccccccccccaacaccaaaaaaaaaaaaaaaaaaacccccccccccccccccccccaaaaaaccccccaaaaaaacccccaacccccaccaaaaacacccccccccacaaaccccccchhhnnnttxxxxxyyyvvvvqqqqiiiccccccc
+SbccccccccccccccccccccccccccccaaaaccaaaaaaacaaaaaaaaaaccccccccccccccccccccccaaaaaaccccccccaaaaaaccccccccccccccaaaaccccccccccccccaaacccccchhhmmmtttxxxEzzyyyyvvvqqqqiiccccccc
+abcccccccccccccccccccccccccccaaaaaccccaaaaaccaaaaaaaaacccccccccccccccaaaaaccaaaaaaccccccccaaccaacccccccccccccccaacccccccaaaaccccccccccccchhhmmmtttxxxyyyyyyyyvvvqqqjjjcccccc
+abcccaaacccccccccccccccccccccaaaaaacccaacaaaaaaaaaaaaacccccccccccccccaaaaacccaaaaaccccccccaacccccccccccccccccccccccccccaaaaacccccccccccchhhmmmttsxxyyyyyyyyvvvvvqqqjjjcccccc
+abcccaaaaaacccaacaaccccccccccacaaaacccaacccaaaaaaaaaaaacccccccccccccaaaaaacccaacaaccccccccccccccccccccccccccccccccaacccaaaaaaccccccccccchhhmmmssxxwwwwyyywvvvvvqqqjjjjcccccc
+abccaaaaaaacccaaaaaccccccccccccaaccccccccccaaaaaaaccaaccccccccccccccaaaaaacccccccccccccccccccccccccccccccccccaaccaaacccaaaaaacccccccaaachhhmmssswwwwwwyyywvvqqqqqqjjjccccccc
+abcaaaaaaacccccaaaaacccccccccccccccccccccccccccaaaccccccccccccccccccaaaaaacccccccccccaaccccaaccccccccccccccccaaacaaacccaaaaaacccccccaaacgggmmsssswwwswwyywwrrqqqjjjjcccccccc
+abcaaaaaaaccccaaaaaacccccccccccccccccccccccaaccaaaccccccccccccccccccccaaccccccccccccaaccccaaaacccccccccccccccaaaaaaccccccaacccccccaacaaagggmmmssssssswwwwwwrrqjjjjjddccccccc
+abcccaaaaaacccaaaacccccccccccccccccccccccccaaacaaccccccccccccccccccccccccccccccccaaaaacaacaaaaccccccccccccccccaaaaaaaaccccccccccccaaaaaagggmmmmssssssswwwwrrrkjjjjddddcccccc
+abcccaaaaaacccccaaccccccccccccccccccccccccccaaaaaccccccccccccccccccccccccccccccccaaaaaaaacaaaacaaccccccaaccaaaaaaaaaaacccccccccccccaaaaaggggmmmmllllsrrwwwrrkkkjdddddaaacccc
+abcccaaaccccccccccccaacccccccccccccccccccccaaaaaaccccccccccccccccccccccccccccccccccaaaaacccccccaaaaaaccaaaaaaaaaaaaaacccccccccccccccaaaaaggggmmllllllrrrrrrrkkkdddddaaaccccc
+abccccaaaaaaccccccccaacaaaccccccccacccaaccaaaaaaaaccccccccccaaaccccccaacccccccccccaaaaaccccccccaaaaacccaaaaaaaaaaaaccccccccccccccccaaacaacggggggflllllrrrrrrkkddddaaaaaccccc
+abccccaaaaacccccccccaaaaacccccccccaaaaaaccaaaaaaaaccccccccccaaacacccaaaaccccccccccaacaaacccccaaaaaaccccaaaaaaaccaaacccccccccccccccccaacccccggggffffllllrrrrkkkdddaaaaaaacccc
+abccaaaaaaacccccccaaaaaaccccccccccaaaaaccccccaacccccaaccccaacaaaaaccaaaacccccccaaccccaaccccccaaaaaaaccaaaaaaaaccaaaccccccccccccccccccaaaccccccgffffflllkkkkkkeedaaaaaaaacccc
+abccaaaaaaacccccccaaaaaaacccccccccaaaaaacccccaacccccaaacccaaaaaaaaccaaaacccaaaaacccccccccccccccaaaaaacaaaaaaaacccccccccccccccccccccccaaaacaacccccffffllkkkkkeeedccaaaaaacccc
+abccccaaaaaaccccccccaaaaaacccccccaaaaaaaacccccaaccccaaaaaaaaaaaaccccccccccaaaaaaaacccccccccccccaaccaaccccaaaccccccaacccccccccccccccccaaaaaaaccccccfffffkkkkeeeecccaacccccccc
+abccccaaccaaccccccccaaccaacccccccaaaaaaaacccccaaccaaaaaaaaccaaaaacccccccccaaaaaaaaccccccccccaacaaccccccccaaccccaacaaaccccaacccccccccccaaaaaaccccccaafffeeeeeeecccccccccccccc
+abccccaaccccccccccccaaccccccccccccccaacccccaaaaaaaaaaaaaaacaaacaaaaaaacaccaaaaaaacccccccaaacaacccccccccccccccccaaaaaccccaaaacccccccaaaaaaaaccccccaaaaffeeeeeeeccccccccccccca
+abacccccccccccccaaacccccccccccccccccaacccccaaaaaaaaaaaaaacccaaccaaaaaaaaaaaaaccaaacccccccaaaaaccccccccccccccccccaaaaaaccaaaacccccccaaaaaaaaaccccccaaacceeeeeccccccccccccccaa
+abaaccccccccccaaaaaacccccccccccccccccccccccccaaaacccaaaaaaccccccaaaaaaaaaaaaaaaaaaaccccccaaaaaaacccaaaccccccccaaaaaaaaccaaaaccccccccaaaaaaaaccccccccccccaaacccccccccccaaacaa
+abaaccccccccccaaaaaacccccccccccccccccccccccccaaaaacaaaaaaaccccccaaaaaaaaaaaaaaaaaaccccccaaaaaaaaccccaaaaccccccaaaaacaaccccccccccccccccaaaaaaacccccccccccacacccccccccccaaaaaa
+abacccccccccccaaaaaaccccccccccccccccccccccccaaaaaacaaaccaaccccccaaaaaaccaaaaaaaaccccccccaaaaaaaaccaaaaaacccccccccaaaccccccccccccccccccaacccccccccccccccccccccccccccccccaaaaa
diff --git a/day12/test_init.py b/day12/test_init.py
new file mode 100644
index 0000000..f721d56
--- /dev/null
+++ b/day12/test_init.py
@@ -0,0 +1,27 @@
+# -*- coding: utf-8 -*-
+from day12 import Map
+
+
+class TestMap:
+    def test_neighbours(self):
+
+        map_input = ["".join([str(i) for i in range(8)]) for _ in range(5)]
+
+        map = Map(map=map_input)
+
+        assert set(map.neighbours(0, 0)) == {
+            (0, 1),
+            (1, 0),
+        }
+
+        assert set(map.neighbours(0, 4)) == {
+            (0, 3),
+            (1, 4),
+        }
+
+        assert set(map.neighbours(1, 1)) == {
+            (0, 1),
+            (1, 0),