summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTomasz Kramkowski <tk@the-tk.com>2021-12-24 08:48:27 +0000
committerTomasz Kramkowski <tk@the-tk.com>2021-12-24 08:48:27 +0000
commite96806627d6dc4d1e439196b337e083a95d40bcd (patch)
tree9b0f7b3eda77aaff2011d78c27ea4dcc26c66669
parent68bc22ce3139786fc6b39dab95dbe83d5cc486ef (diff)
downloadaoc2021-e96806627d6dc4d1e439196b337e083a95d40bcd.tar.gz
aoc2021-e96806627d6dc4d1e439196b337e083a95d40bcd.tar.xz
aoc2021-e96806627d6dc4d1e439196b337e083a95d40bcd.zip
move a_star from 15 to utils
-rw-r--r--15.py48
-rw-r--r--utils.py41
2 files changed, 45 insertions, 44 deletions
diff --git a/15.py b/15.py
index 231f5e8..f3dd57c 100644
--- a/15.py
+++ b/15.py
@@ -1,48 +1,10 @@
-from collections import defaultdict
-from utils import open_day, Point2D, adjacent_bounded
-from heapq import heappop, heappush
-
-def a_star(start, goal, neighbours, h, d):
- vtoi = dict()
- itov = dict()
- i = 0
- def intern(v):
- nonlocal i
- ret = vtoi.get(v)
- if ret is None:
- ret = i
- vtoi[v] = i
- itov[i] = v
- i += 1
- return ret
- open_set = {start}
- open_heapq = [(0, intern(start))]
- came_from = dict()
- g_score = defaultdict(lambda: float('inf'))
- g_score[start] = 0
- f_score = defaultdict(lambda: float('inf'))
- f_score[start] = h(start)
- while open_set:
- while True:
- f, current = heappop(open_heapq)
- current = itov[current]
- if current in open_set: break
- if current == goal:
- return f
- open_set.remove(current)
- for neighbour in neighbours(current):
- tentative_g = g_score[current] + d(current, neighbour)
- if tentative_g < g_score[neighbour]:
- came_from[neighbour] = current
- g_score[neighbour] = tentative_g
- f_score[neighbour] = tentative_g + h(neighbour)
- open_set.add(neighbour)
- heappush(open_heapq, (f_score[neighbour], intern(neighbour)))
- return None
+from utils import open_day, Point2D, adjacent_bounded, a_star
with open_day(15) as f:
inp = [[int(c) for c in l.rstrip()] for l in f]
+def h(p): return 0
+
def d(a, b):
add = b.x // len(inp[0]) + b.y // len(inp)
x, y = b.x % len(inp[0]), b.y % len(inp)
@@ -51,7 +13,7 @@ def d(a, b):
start = Point2D(0, 0)
goal1 = Point2D(len(inp[0]) - 1, len(inp) - 1)
neighbours1 = lambda p: adjacent_bounded(p, Point2D(len(inp[0]), len(inp)), False)
-print(a_star(start, goal1, neighbours1, lambda p: 0, d))
+print(a_star(start, goal1, neighbours1, h, d))
goal2 = Point2D(len(inp[0]) * 5 - 1, len(inp) * 5 - 1)
neighbours2 = lambda p: adjacent_bounded(p, Point2D(len(inp[0]) * 5, len(inp) * 5), False)
-print(a_star(start, goal2, neighbours2, lambda p: 0, d))
+print(a_star(start, goal2, neighbours2, h, d))
diff --git a/utils.py b/utils.py
index 44fd07a..c7ab871 100644
--- a/utils.py
+++ b/utils.py
@@ -1,7 +1,8 @@
from __future__ import annotations
-from collections import deque
+from collections import deque, defaultdict
from collections.abc import Iterable, Iterator
from dataclasses import dataclass
+from heapq import heappop, heappush
from itertools import islice
from math import sqrt
from re import match as re_match
@@ -59,6 +60,44 @@ def adjacent_bounded(p: Point2D[int], bound: Point2D[int], diagonal: bool = True
-> Iterator[Point2D[int]]:
return filter(lambda p: inbounds(p, bound), adjacent(p, diagonal))
+def a_star(start, goal, neighbours, h, d):
+ vtoi = dict()
+ itov = dict()
+ i = 0
+ def intern(v):
+ nonlocal i
+ ret = vtoi.get(v)
+ if ret is None:
+ ret = i
+ vtoi[v] = i
+ itov[i] = v
+ i += 1
+ return ret
+ open_set = {start}
+ open_heapq = [(0, intern(start))]
+ came_from = dict()
+ g_score = defaultdict(lambda: float('inf'))
+ g_score[start] = 0
+ f_score = {}
+ f_score[start] = h(start)
+ while open_set:
+ while True:
+ f, current = heappop(open_heapq)
+ current = itov[current]
+ if current in open_set: break
+ if current == goal:
+ return f
+ open_set.remove(current)
+ for neighbour in neighbours(current):
+ tentative_g = g_score[current] + d(current, neighbour)
+ if tentative_g < g_score[neighbour]:
+ came_from[neighbour] = current
+ g_score[neighbour] = tentative_g
+ f_score[neighbour] = tentative_g + h(neighbour)
+ open_set.add(neighbour)
+ heappush(open_heapq, (f_score[neighbour], intern(neighbour)))
+ return None
+
T = TypeVar('T')
def sliding_window(iterable: Iterable[T], n: int) -> Iterator[tuple[T, ...]]:
# sliding_window('ABCDEFG', 4) -> ABCD BCDE CDEF DEFG