summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTomasz Kramkowski <tk@the-tk.com>2021-12-15 22:27:25 +0000
committerTomasz Kramkowski <tk@the-tk.com>2021-12-16 01:33:43 +0000
commite22d2d2e3e1d1427caeeb3f106680bc3edceb39f (patch)
treeb1b977a2178d11c35cf4125648476bdbbee7c14b
parent1d03c102f813f819697ea95f96eee6dbe0464be1 (diff)
downloadaoc2021-e22d2d2e3e1d1427caeeb3f106680bc3edceb39f.tar.gz
aoc2021-e22d2d2e3e1d1427caeeb3f106680bc3edceb39f.tar.xz
aoc2021-e22d2d2e3e1d1427caeeb3f106680bc3edceb39f.zip
utils: Point2D and related functions
-rw-r--r--15.py54
-rw-r--r--5.py6
-rw-r--r--9.py44
-rw-r--r--utils.py60
4 files changed, 109 insertions, 55 deletions
diff --git a/15.py b/15.py
index ab369f5..231f5e8 100644
--- a/15.py
+++ b/15.py
@@ -1,21 +1,34 @@
from collections import defaultdict
-from utils import open_day
+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, 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:
- f, current = open_heapq[0]
+ while True:
+ f, current = heappop(open_heapq)
+ current = itov[current]
+ if current in open_set: break
if current == goal:
return f
- heappop(open_heapq)
open_set.remove(current)
for neighbour in neighbours(current):
tentative_g = g_score[current] + d(current, neighbour)
@@ -23,31 +36,22 @@ def a_star(start, goal, neighbours, h, d):
came_from[neighbour] = current
g_score[neighbour] = tentative_g
f_score[neighbour] = tentative_g + h(neighbour)
- if neighbour not in open_set:
- open_set.add(neighbour)
- heappush(open_heapq, (f_score[neighbour], neighbour))
+ open_set.add(neighbour)
+ heappush(open_heapq, (f_score[neighbour], intern(neighbour)))
return None
with open_day(15) as f:
inp = [[int(c) for c in l.rstrip()] for l in f]
-def neighbours(p, dim):
- for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
- px, py = p[0] + dx, p[1] + dy
- if px < 0 or py < 0 or px >= dim[0] or py >= dim[1]: continue
- yield px, py
-
-def manhattan(a, b): return abs(a[0] - b[0]) + abs(a[1] - b[1])
def d(a, b):
- x, y = b
- add = x // len(inp[0]) + y // len(inp)
- x, y = x % len(inp[0]), y % len(inp)
+ add = b.x // len(inp[0]) + b.y // len(inp)
+ x, y = b.x % len(inp[0]), b.y % len(inp)
return (inp[y][x] + add - 1) % 9 + 1
-start = (0, 0)
-goal1 = (len(inp[0]) - 1, len(inp) - 1)
-neighbours1 = lambda p: neighbours(p, (len(inp[0]), len(inp)))
-print(a_star(start, goal1, neighbours1, lambda p: manhattan(p, goal1), d))
-goal2 = (len(inp[0]) * 5 - 1, len(inp) * 5 - 1)
-neighbours2 = lambda p: neighbours(p, (len(inp[0]) * 5, len(inp) * 5))
-print(a_star(start, goal2, neighbours2, lambda p: manhattan(p, goal2), d))
+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))
+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))
diff --git a/5.py b/5.py
index 1e61efb..802ccc7 100644
--- a/5.py
+++ b/5.py
@@ -1,11 +1,9 @@
from collections import defaultdict, namedtuple
-from utils import open_day
-
-Pos = namedtuple('Pos', ['x', 'y'])
+from utils import open_day, Point2D
vents = [
tuple(
- Pos(*map(int, h.split(',')))
+ Point2D(*map(int, h.split(',')))
for h in l.rstrip().split(' -> ')
)
for l in open_day(5).read().rstrip().split('\n')
diff --git a/9.py b/9.py
index d1a63b9..0db75b1 100644
--- a/9.py
+++ b/9.py
@@ -1,45 +1,43 @@
from functools import reduce
-from utils import open_day
+from utils import open_day, Point2D, adjacent_bounded
from collections import deque
heatmap = [[int(c) for c in l.rstrip()] for l in open_day(9)]
+bounds = Point2D(len(heatmap[0]), len(heatmap))
adj = [(1, 0), (0, 1), (-1, 0), (0, -1)]
-def is_low(x, y):
- risk = heatmap[y][x]
- for dx, dy in adj:
- nx = x + dx
- ny = y + dy
- if nx >= 0 and nx < len(heatmap[0]) and ny >= 0 and ny < len(heatmap):
- if heatmap[y+dy][x+dx] <= risk:
- return False
+def is_low(p):
+ risk = heatmap[p.y][p.x]
+ for n in adjacent_bounded(p, bounds, False):
+ if heatmap[n.y][n.x] <= risk:
+ return False
return True
-def basin_size(x, y):
+def basin_size(p):
seen = set()
- queue = deque(((x, y),))
+ queue = deque((p,))
size = 0
while queue:
- x, y = queue.popleft()
- if (x, y) in seen:
+ p = queue.popleft()
+ if p in seen:
continue
- if x < 0 or x >= len(heatmap[0]) or y < 0 or y >= len(heatmap):
- continue
- seen.add((x, y))
- if heatmap[y][x] == 9:
+ seen.add(p)
+ if heatmap[p.y][p.x] == 9:
continue
size += 1
- for dx, dy in adj:
- queue.append((x + dx, y + dy))
+ for n in adjacent_bounded(p, bounds, False):
+ # print(p, n)
+ queue.append(n)
return size
totrisk = 0
lows = []
-for y in range(len(heatmap)):
- for x in range(len(heatmap[y])):
- if is_low(x, y):
+for y in range(bounds.y):
+ for x in range(bounds.x):
+ p = Point2D(x, y)
+ if is_low(p):
totrisk += 1 + heatmap[y][x]
- lows.append(basin_size(x, y))
+ lows.append(basin_size(p))
print(totrisk)
lows.sort()
print(reduce(lambda x, y: x * y, lows[-3:], 1))
diff --git a/utils.py b/utils.py
index 91b90ff..00d0d60 100644
--- a/utils.py
+++ b/utils.py
@@ -1,11 +1,65 @@
+from __future__ import annotations
from collections import deque
-from collections.abc import Iterable, Iterator, Generator
+from collections.abc import Iterable, Iterator
+from dataclasses import dataclass
from itertools import islice
+from math import sqrt
from sys import argv
-from typing import TypeVar
+from typing import TypeVar, Generic, Union, Optional, cast
+
+NumT = TypeVar('NumT', float, int)
+
+@dataclass(frozen=True)
+class Point2D(Generic[NumT]):
+ x: NumT
+ y: NumT
+
+ def __str__(self) -> str:
+ return f'({self.x}, {self.y})'
+
+ def __add__(self, other: Point2D[NumT]) -> Union[Point2D[NumT], bool]:
+ if isinstance(other, Point2D):
+ return Point2D(self.x + other.x, self.y + other.y)
+ return NotImplemented
+
+ def __sub__(self, other: Point2D[NumT]) -> Union[Point2D[NumT], bool]:
+ if isinstance(other, Point2D):
+ return Point2D(self.x - other.x, self.y - other.y)
+ return NotImplemented
+
+ def __abs__(self) -> Point2D[NumT]:
+ return Point2D(cast(NumT, abs(self.x)), cast(NumT, abs(self.y)))
+
+def norm_1(p: Point2D[NumT]) -> NumT:
+ return cast(NumT, abs(p.x) + abs(p.y))
+
+def norm_2(p: Point2D) -> float:
+ return sqrt(p.x ** 2 + p.y ** 2)
+
+def norm_inf(p: Point2D[NumT]) -> NumT:
+ return cast(NumT, max(abs(p.x), abs(p.y)))
+
+def inbounds(p: Point2D[NumT], a: Point2D[NumT], _b: Optional[Point2D[NumT]] = None) -> bool:
+ if isinstance(_b, Point2D):
+ b = _b
+ else:
+ b = a
+ a = cast(Point2D[NumT], Point2D(0, 0) if isinstance(a.x, int) else Point2D(0.0, 0.0))
+ return p.x >= a.x and p.y >= a.y and p.x < b.x and p.y < b.y
+
+def adjacent(p: Point2D[int], diagonal: bool = True) -> Iterator[Point2D[int]]:
+ for dx in range(-1, 2):
+ for dy in range(-1, 2):
+ if dx == 0 and dy == 0: continue
+ if dx != 0 and dy != 0 and not adjacent: continue
+ yield Point2D(p.x + dx, p.y + dy)
+
+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))
T = TypeVar('T')
-def sliding_window(iterable: Iterable[T], n: int) -> Generator[tuple[T, ...], None, None]:
+def sliding_window(iterable: Iterable[T], n: int) -> Iterator[tuple[T, ...]]:
# sliding_window('ABCDEFG', 4) -> ABCD BCDE CDEF DEFG
it: Iterator[T] = iter(iterable)
window: deque[T] = deque(islice(it, n), maxlen=n)