1 files changed, 79 insertions, 0 deletions
diff --git a/17.py b/17.py
new file mode 100644
index 0000000..2b463f8
--- /dev/null
+++ b/17.py
@@ -0,0 +1,79 @@
+from collections.abc import Callable, Iterator
+from dataclasses import dataclass
+from functools import total_ordering
+from sys import stdin
+from typing import Self
+
+from utils import Dir, a_star
+
+
+@total_ordering
+@dataclass
+class Pos:
+    x: int
+    y: int
+    direction: Dir | None = None
+
+    def __eq__(self, other: object) -> bool:
+        if isinstance(other, Pos):
+            return (self.x, self.y) == (other.x, other.y)
+        return NotImplemented
+
+    def __lt__(self, other: object) -> bool:
+        if isinstance(other, Pos):
+            return (self.x, self.y) < (other.x, other.y)
+        return NotImplemented
+
+    def __hash__(self) -> int:
+        return hash((self.x, self.y, self.direction))
+
+    def manhattan(self, other: Self) -> int:
+        return abs(self.x - other.x) + abs(self.y - other.y)
+
+
+def make_neighbours(
+    width: int, height: int, min_dist: int, max_dist: int
+) -> Callable[[Pos], Iterator[Pos]]:
+    def neighbours(p: Pos) -> Iterator[Pos]:
+        if p.direction not in {Dir.NORTH, Dir.SOUTH}:
+            for dy in range(min_dist, max_dist + 1):
+                if p.y - dy < height and p.y - dy >= 0:
+                    yield Pos(p.x, p.y - dy, Dir.NORTH)
+                if p.y + dy < height and p.y + dy >= 0:
+                    yield Pos(p.x, p.y + dy, Dir.SOUTH)
+        if p.direction not in {Dir.EAST, Dir.WEST}:
+            for dx in range(min_dist, max_dist + 1):
+                if p.x + dx < width and p.x + dx >= 0:
+                    yield Pos(p.x + dx, p.y, Dir.EAST)
+                if p.x - dx < width and p.x - dx >= 0:
+                    yield Pos(p.x - dx, p.y, Dir.WEST)
+
+    return neighbours
+
+
+inp = [line.rstrip("\n") for line in stdin]
+
+
+def normalize(n: int) -> int:
+    return min(1, max(-1, n))
+
+
+def d(a: Pos, b: Pos) -> int:
+    ndx = normalize(b.x - a.x)
+    ndy = normalize(b.y - a.y)
+    total = 0
+    if ndx != 0:
+        for x in range(a.x + ndx, b.x + ndx, ndx):
+            total += int(inp[a.y][x])
+    elif ndy != 0:
+        for y in range(a.y + ndy, b.y + ndy, ndy):
+            total += int(inp[y][a.x])
+    return total
+
+
+goal = Pos(len(inp[0]) - 1, len(inp) - 1)
+
+p1neighbours = make_neighbours(len(inp[0]), len(inp), 1, 3)
+print(a_star(Pos(0, 0), goal, p1neighbours, goal.manhattan, d))
+p2neighbours = make_neighbours(len(inp[0]), len(inp), 4, 10)
+print(a_star(Pos(0, 0), goal, p2neighbours, goal.manhattan, d))