From 2d1263453d26cd2c6a64a3b6141ee0a12ddc0b11 Mon Sep 17 00:00:00 2001 From: Tom van der Lee Date: Sat, 17 Dec 2022 16:35:17 +0100 Subject: Day 16 [WIP] --- aoc/mixins.py | 57 ++++++++++++++++++++++++++++++++++++++++++++++++ day12/__init__.py | 65 +++++++++---------------------------------------------- day16/__init__.py | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++ day16/example.txt | 10 +++++++++ day16/input.txt | 59 ++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 196 insertions(+), 55 deletions(-) create mode 100644 aoc/mixins.py create mode 100644 day16/__init__.py create mode 100644 day16/example.txt create mode 100644 day16/input.txt 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 diff --git a/day16/example.txt b/day16/example.txt new file mode 100644 index 0000000..9f30acc --- /dev/null +++ b/day16/example.txt @@ -0,0 +1,10 @@ +Valve AA has flow rate=0; tunnels lead to valves DD, II, BB +Valve BB has flow rate=13; tunnels lead to valves CC, AA +Valve CC has flow rate=2; tunnels lead to valves DD, BB +Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE +Valve EE has flow rate=3; tunnels lead to valves FF, DD +Valve FF has flow rate=0; tunnels lead to valves EE, GG +Valve GG has flow rate=0; tunnels lead to valves FF, HH +Valve HH has flow rate=22; tunnel leads to valve GG +Valve II has flow rate=0; tunnels lead to valves AA, JJ +Valve JJ has flow rate=21; tunnel leads to valve II diff --git a/day16/input.txt b/day16/input.txt new file mode 100644 index 0000000..89e7cac --- /dev/null +++ b/day16/input.txt @@ -0,0 +1,59 @@ +Valve ZT has flow rate=0; tunnels lead to valves QQ, DS +Valve JX has flow rate=22; tunnels lead to valves CI, ZH, UR +Valve EM has flow rate=0; tunnels lead to valves WH, IT +Valve AA has flow rate=0; tunnels lead to valves EQ, QD, NP, ZP, KX +Valve HW has flow rate=0; tunnels lead to valves CI, BV +Valve IK has flow rate=8; tunnels lead to valves ET, NU, ZO, XL, QD +Valve HA has flow rate=0; tunnels lead to valves WQ, LB +Valve WH has flow rate=12; tunnels lead to valves EM, LW +Valve KU has flow rate=0; tunnels lead to valves BV, CF +Valve QD has flow rate=0; tunnels lead to valves AA, IK +Valve CF has flow rate=18; tunnels lead to valves KU, JT, CM +Valve VC has flow rate=0; tunnels lead to valves AD, UY +Valve JT has flow rate=0; tunnels lead to valves CF, ZH +Valve QQ has flow rate=11; tunnel leads to valve ZT +Valve ZP has flow rate=0; tunnels lead to valves EZ, AA +Valve LI has flow rate=0; tunnels lead to valves LB, CM +Valve CI has flow rate=0; tunnels lead to valves HW, JX +Valve VK has flow rate=6; tunnels lead to valves YM, LC, HE, NU, TI +Valve WL has flow rate=20; tunnels lead to valves LW, TO +Valve TI has flow rate=0; tunnels lead to valves VK, YW +Valve NU has flow rate=0; tunnels lead to valves VK, IK +Valve DS has flow rate=9; tunnels lead to valves NP, MV, FR, ZT, YW +Valve HE has flow rate=0; tunnels lead to valves VK, EQ +Valve ZH has flow rate=0; tunnels lead to valves JT, JX +Valve TO has flow rate=0; tunnels lead to valves MT, WL +Valve CM has flow rate=0; tunnels lead to valves LI, CF +Valve WM has flow rate=14; tunnels lead to valves MO, WQ, EC, RN +Valve EZ has flow rate=16; tunnels lead to valves RT, RZ, ZP +Valve PB has flow rate=0; tunnels lead to valves YM, UY +Valve XL has flow rate=0; tunnels lead to valves IK, MS +Valve LB has flow rate=17; tunnels lead to valves LI, HA, ON, UR, AD +Valve WQ has flow rate=0; tunnels lead to valves WM, HA +Valve BV has flow rate=13; tunnels lead to valves KU, RT, HW, MO, EH +Valve RN has flow rate=0; tunnels lead to valves WM, RZ +Valve LW has flow rate=0; tunnels lead to valves WH, WL +Valve NP has flow rate=0; tunnels lead to valves AA, DS +Valve MT has flow rate=0; tunnels lead to valves TO, HG +Valve ET has flow rate=0; tunnels lead to valves IK, EC +Valve HG has flow rate=19; tunnel leads to valve MT +Valve MV has flow rate=0; tunnels lead to valves UY, DS +Valve RT has flow rate=0; tunnels lead to valves BV, EZ +Valve ON has flow rate=0; tunnels lead to valves LB, EH +Valve MO has flow rate=0; tunnels lead to valves BV, WM +Valve UY has flow rate=5; tunnels lead to valves PB, BR, MS, VC, MV +Valve UR has flow rate=0; tunnels lead to valves JX, LB +Valve YM has flow rate=0; tunnels lead to valves PB, VK +Valve RZ has flow rate=0; tunnels lead to valves RN, EZ +Valve AD has flow rate=0; tunnels lead to valves VC, LB +Valve EH has flow rate=0; tunnels lead to valves ON, BV +Valve EQ has flow rate=0; tunnels lead to valves AA, HE +Valve KX has flow rate=0; tunnels lead to valves AA, BR +Valve BR has flow rate=0; tunnels lead to valves UY, KX +Valve LC has flow rate=0; tunnels lead to valves VK, IT +Valve YW has flow rate=0; tunnels lead to valves TI, DS +Valve EC has flow rate=0; tunnels lead to valves ET, WM +Valve IT has flow rate=10; tunnels lead to valves LC, EM +Valve MS has flow rate=0; tunnels lead to valves UY, XL +Valve FR has flow rate=0; tunnels lead to valves DS, ZO +Valve ZO has flow rate=0; tunnels lead to valves FR, IK -- cgit v1.2.3