4 files changed, 285 insertions, 0 deletions

diff --git a/day15/__init__.py b/day15/__init__.py
new file mode 100644
index 0000000..38126fc
--- /dev/null
+++ b/day15/__init__.py
@@ -0,0 +1,138 @@
+import math
+from abc import ABC
+from dataclasses import dataclass
+from typing import List, Tuple, Iterator, TypedDict, Dict
+
+from aoc import BaseAssignment
+from aoc.utils import bold
+
+Coordinate = Tuple[int, int]
+Map = List[List[int]]
+
+@dataclass
+class Score:
+    g_score: float
+    h_score: float
+
+    @property
+    def f_score(self):
+        return self.g_score + self.h_score
+
+class Assignment(BaseAssignment, ABC):
+    def parse_item(self, item: str) -> List[int]:
+        return [int(i) for i in item]
+
+    def read_input(self, example = False) -> Map:
+        return list(super().read_input(example))
+
+    @classmethod
+    def neighbours(cls, field: Map, x: int, y: int) -> Iterator[Coordinate]:
+        for ny in list(range(max(0, y - 1), min(len(field) - 1, y + 1) + 1)):
+            if ny == y:
+                continue
+            yield (x, ny)
+
+        for nx in list(range(max(0, x - 1), min(len(field[0]) - 1, x + 1) + 1)):
+            if nx == x:
+                continue
+            yield (nx, y)
+
+    @classmethod
+    def distance(cls, start: Coordinate, end: Coordinate) -> float:
+        start_x, start_y = start
+        end_x, end_y = end
+
+        dx = end_x - start_x
+        dy = end_y - start_y
+
+        return math.sqrt((dx ** 2) + (dy ** 2))
+
+    @classmethod
+    def gen_path(cls, current: Coordinate, came_from: Dict[Coordinate, Coordinate]) -> List[Coordinate]:
+        path = [current]
+        while current in came_from:
+            current = came_from[current]
+            path.append(current)
+        return list(reversed(path))
+
+    @classmethod
+    def a_star(self, field: Map, start: Coordinate, end: Coordinate) -> List[Coordinate]:
+        open = {start}
+        came_from: Dict[Coordinate, Coordinate] = {}
+
+        scores: Dict[Coordinate, Score] = {
+            start: Score(
+                g_score=0,
+                h_score = self.distance(start, end),
+            )
+        }
+
+        while len(open) > 0:
+            current = sorted(open, key=lambda c: scores[c].f_score)[0]
+            if current == end:
+                return self.gen_path(current, came_from)
+
+            open.remove(current)
+            for neighbour in self.neighbours(field, current[0], current[1]):
+                g_score = scores[current].g_score + field[neighbour[1]][neighbour[0]]
+                neighbour_scores = scores.get(neighbour)
+
+                if neighbour_scores is None or g_score < neighbour_scores.g_score:
+                    came_from[neighbour] = current
+                    neighbour_scores = Score(
+                        g_score=g_score,
+                        h_score=self.distance(neighbour, end)
+                    )
+                    scores[neighbour] = neighbour_scores
+
+                    if neighbour not in open:
+                        open.add(neighbour)
+
+        raise Exception('No Path')
+
+    @classmethod
+    def print_field(cls, field: Map, path: List[Coordinate]):
+        print('', flush=False)
+        for y, row in enumerate(field):
+            print(''.join([ bold(str(i), lambda: (x, y) in path) for x, i in enumerate(row) ]), flush=False)
+        print('', flush=True)
+
+    def run(self, input: Map) -> int:
+        start = (0, 0)
+        end = (len(input[0]) - 1, len(input) - 1)
+
+        path = self.a_star(input, start, end)
+
+        self.print_field(input, path)
+
+        path.remove(start)
+        return sum([
+            input[y][x]
+            for x, y
+            in path
+        ])
+
+class AssignmentOne(Assignment):
+    example_result = 40
+
+class AssignmentTwo(Assignment):
+    example_result =  315
+
+    @classmethod
+    def overflow(self, item):
+        return item - 9 if item > 9 else item
+
+    @classmethod
+    def increase_map(cls, map) -> Map:
+        return [
+            [
+                cls.overflow(item + dx + dy)
+                for dx in range(5)
+                for item in row
+            ]
+            for dy in range(5)
+            for row in map
+        ]
+
+    def read_input(self, example = False) -> Map:
+        return self.increase_map(super().read_input(example))
diff --git a/day15/example.txt b/day15/example.txt
new file mode 100644
index 0000000..ab80887
--- /dev/null
+++ b/day15/example.txt
@@ -0,0 +1,10 @@
+1163751742
+1381373672
+2136511328
+3694931569
+7463417111
+1319128137
+1359912421
+3125421639
+1293138521
+2311944581
diff --git a/day15/input.txt b/day15/input.txt
new file mode 100644
index 0000000..3431e9f
--- /dev/null
+++ b/day15/input.txt
@@ -0,0 +1,100 @@
+7123177913871491389589264788547148381988811673752241637816163827448692499239515115894381588375396471
+9738878597866183278612514475755598861117949965829826949819696599841511616198177483157219211238226665
+2728314738118818417596585299898141515484167717378811771172771455459817575879182681543225671796579564
+3698237941798921857499612323641798179312519816114669628793538557419995793394792976116175183983211218
+8931299558895122919849817111991912299694619511272212888417418196496976619283339474157935296969177921
+4876399196561616888211818411392552865916811686918294139639998168582233818894993882378164973177419292
+1292826913925292993394627812472966298114458928424398988196171891981314199973375171711499591999295722
+2612819791685974812429441111697818261281422279834379563115293558312533728942295586148171358952659947
+6638822314594315236886818282759119972499915998333742951291758918511191291981139924297194471198819992
+3212921351399439782291441141194213794861268171719226573929478185198972881798292879922296597111267985
+9694955531925421216621667171387812673256762869119116982546712788121611188865459428311479913923252812
+8993899649958218893492947198596622311414594129991613199694121881963973616778199437361417251114898896
+2932137594986313811563891831516429822264187117794718732832322275923584989344938612756788851319215445
+9923942842169247311971329991517267154685897333913756132933889376946781927392178755261819729642288132
+9142173591893199149829423314381331583328694313941266171113924219211681916313986812131311533142191693
+5848192685188599944816146242793127138949121256118119414186816441591293151999119971396296221276131241
+3495527991317138191168853316591298662515462388318695459314259431427199827112814475291998894533661719
+6815167261798913879534189564249399392672145779914816489949341922439166128967131283857229364832939232
+9715263568753956232885237118388651333374435831664275153715817339997179993814287431396622272616271133
+1812949719568129216833815893498895318898151127318887918774267731151122617626267391916721894187735879
+6194936292994131619884424828772115321296933111248146743138951133525259921388132674296978191595215421
+8977231295463954488743917723843199269161928319992799113233196719627994185231913636481128347191888993
+7191387136716153811135921391495919122211583111131242512186177359857642411281598176173477158148461742
+8748994183994891161849125494181651122719172611112829351936539911981374881952184859949776981967135889
+4818995199799799317796797181385776752888232638392141897612916871898458673919399565456391616359619722
+2324149221529527952295121615332529396955513926313268682677391936267663467637119911666968839741927288
+9387191819291784198317392415819191724129835871495311699431299514299912942877459422153796598154195936
+3187152295157488239629224167299278792979374188163598271919325679669943944631641114319613632913941867
+4187553758199893917166292177621116363872642297713977519579918916911132498628192671316693138923217738
+7896983716218397299912126791897926852272193176651193815853749813676172192991933991241531915358592943
+2348247919145847514999915288812971366894736367322416127123839211819819893938238144595466824813581688
+6911579174885666196116496835334513924129158549472491355911727571419193999691849595418142654987162596
+8233311258291312123922594216362361184417111671134933993719988681111993994811784424145912713728546148
+1162139841389997711783335749151324349829189455223249558153435151167312198161429992286971283355217762
+9499631991542729216797153991489111797686945155575494822971821485199834897292889255296899325832659372
+9919722366494721121916812991347712311123354812314431341835584535911911183475929155451117133113518354
+3299321782846455776178299242914282826128713775681296642569791332836884518333197171822922357552638257
+4614911396711984669911199281145369229899421149212339819959928831788384791918432316191251591691214353
+4369289134597955589999495348592539727279475199412997118117152888153787932811981712348789921597223884
+1921278987992168289199159228511681682851987138959823165149863424871954671997219162181639788134671239
+8539367723644163113958998812319181651829319522919271727372655732991298341353642799614887987116119991
+9819237823912311318512271116896112568693473129616312762194271883382198451421259591659131149739567431
+3913629226255984248923677172369227529268378689129311591493392989499398541156998151934538421544988198
+9874118273932233256784989122831831438444699999969125597386734339278292411842292935966924611973117536
+3297942819139177814771683635499686478938123535294382195953689425918122743452127119188392213214162719
+6428369731511597131697241921814427613712519849617997822241919837334471918169985497447845215111571111
+4717882166389311599121985911815127671481262152181961791322981241713128381283932879815396748715326116
+9446657145378538332649933726924339585982712752416989637831889841999171924591539949915281695348616119
+1542914874298812536216998196883784913621263443517371816311128619246117922299562938819614239587919693
+1445469798118719191614518343323122521442292174917967445253456563977662989479257751894581593719739991
+7772142417741935423174485817123889139399291273428692734431984124117191994123498115727598161392677699
+6988945923714311219114921397868498885113257552168928846919896189191694261437512499791222278916169288
+7851211433643663591554743152113696322971779195631762592311915771859233266466849696548914971193499364
+4919396661388921921994122948951598619526848887659791912391223398827566916838432249598749774916496711
+1196599655895393416289389977637236641318279616416994991439226589111757355629849933169854118249997919
+5114211499998844843174919884423467219162277687929161558775139511929631962658267678221272328914953732
+8216171512426485781351969231952198433381329983288317413326512138574464114453937223541765367971856788
+2213177288792193388519618281868911182281428936911325912397967192287711833111797518143218673821192899
+2784153192416189911216612291791983219622166389621996117219781639919612667199999129821528411964639199
+4187898219537683365988849129793392557283572786889441274612197286178112735995692535456157587812218711
+3289961986387137451576181267292891928699191488241997579896141161217814198431161774438724446513817347
+1579149591461935819116247565121622891413133538179461264778198149199793117163932219237419521332475723
+8511871311713679914269882644473751984369996191729198493285714245762879942883717594273668937984612859
+1299519281323389918993242297332143893749252414799491177636152119414457637112995194255822953441323767
+5956297531138129799432717521922827212567131222732852611291511239992997934392819583522981699162914417
+9941713968132521114282728119911171371767252117572477196141318371891319144171114944838884899991129662
+3289334178322912999218672177961313951181389283788115263914991671385991338168197891735411426621896437
+3517399198911891116419161659893219997361251111462415147245636698911119144122948941611999537914127921
+7391621997684963324417791261394821117179111599877845791691691999758491717192891377392662426922381649
+9539641387391158465314288999171521516996119112739729425799782424458612492799866313395268329813142998
+7159761151187488213272297981256985319892792222143284319128613282931987743335641992228248391313519531