From 126a628b171e2a7d2490290185ab21990b0d9698 Mon Sep 17 00:00:00 2001 From: Tom van der Lee Date: Mon, 12 Dec 2022 10:49:04 +0100 Subject: Day12 [Wip] --- day12/__init__.py | 137 +++++++++++++++++++++++++++++++++++++++++++++++++++++ day12/example.txt | 5 ++ day12/input.txt | 41 ++++++++++++++++ day12/test_init.py | 27 +++++++++++ 4 files changed, 210 insertions(+) create mode 100644 day12/__init__.py create mode 100644 day12/example.txt create mode 100644 day12/input.txt create mode 100644 day12/test_init.py (limited to 'day12') 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), + (1, 2), + (2, 1), + } -- cgit v1.2.3