Day 9

3 files changed, 184 insertions, 0 deletions

diff --git a/day9/__init__.py b/day9/__init__.py
new file mode 100644
index 0000000..696a6dc
--- /dev/null
+++ b/day9/__init__.py
@@ -0,0 +1,79 @@
+from abc import ABC
+from collections import Counter
+from copy import copy
+from functools import reduce
+from operator import mul
+from typing import List, Tuple, Dict, FrozenSet, Iterator, Set, Callable
+
+from aoc import BaseAssignment
+
+Coordinate = Tuple[int, int]
+Field = List[List[int]]
+
+
+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) -> Field:
+        return list(super().read_input(example))
+
+    @classmethod
+    def neighbours(cls, field: Field, 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 lowest_points(cls, field: Field) -> Iterator[Coordinate]:
+        for y, row in enumerate(field):
+            for x, item in enumerate(row):
+                if all(field[ny][nx] > item for nx, ny in cls.neighbours(field, x, y)):
+                    yield x, y
+
+
+class AssignmentOne(Assignment):
+    example_result = 15
+
+    def run(self, input: Field) -> int:
+        lows = list(input[y][x] for x, y in self.lowest_points(input))
+        return sum(lows) + len(lows)
+
+
+def flatten(l: List[Set[Coordinate]]) -> List:
+    flat_list = []
+    for _ in l:
+        flat_list += _
+
+    return flat_list
+
+
+class AssignmentTwo(Assignment):
+    example_result = 1134
+
+    @classmethod
+    def find_basin_members(cls, field: Field, x: int, y: int) -> Set[Coordinate]:
+        return {
+            (x, y),
+            *flatten([
+                cls.find_basin_members(field, nx, ny)
+                for nx, ny in cls.neighbours(field, x, y)
+                if field[y][x] < field[ny][nx] < 9
+            ])
+        }
+
+    def run(self, input: Field) -> int:
+        return reduce(
+            mul,
+            sorted([
+                len(self.find_basin_members(input, x, y))
+                for x, y in self.lowest_points(input)
+            ], reverse=True)[:3],
+            1
+        )
diff --git a/day9/example.txt b/day9/example.txt
new file mode 100644
index 0000000..6dee4a4
--- /dev/null
+++ b/day9/example.txt
@@ -0,0 +1,5 @@
+2199943210
+3987894921
+9856789892
+8767896789
+9899965678
diff --git a/day9/input.txt b/day9/input.txt
new file mode 100644
index 0000000..1c16e86
--- /dev/null
+++ b/day9/input.txt
@@ -0,0 +1,100 @@
+5432345678989998934579789765459876765467892399767954567893212987898410456789329876710145678998765432
+6754656789879987899698678954398765452356953989654543456789329876987321345697634965431236989239879321
+9865769898767656798979567893249876321257899878653432568996499865696534456789549876542345892125998945
+5976778999656545987665456799345985432348989965432101457897989879987876567998756987656456789234987899
+4987889998945439876567344678969876543489879876543212345689878998998997688959987998966567897649876798
+3298998987832123965432123499999989865678967989654346896893567897899989789543998999878689998799965457
+9989867896543239876321014989989595978789656998767567998932456956912978997659899987989789459987654346
+8678456789656798765432199878879434989892546799987678979321767899899767998798789876699892398996543212
+6532349898767899878543987654568923996921234789898889765433479998765656899987698765459921987987652101
+6431239929898910989654598743478919875210145698789999876764989999854345678965439999568939875498778212
+5310128939969899699875689654569101964321234989654321997875678979865234569654323987679198764398765323
+6542337898656798569989798765678999875432349876543210398876799569954358978943212398789098963239765434
+7653456789545987458999899898789989876565489988974341239987965498765467899954101459894987656145978565
+9874567897639876567899999979899876987676679999765632545698954349876978979876532345993496541034797678
+8765678999545987978978998765989765698989998999876784678999983242987989765989673456789987632123698789
+9896789998956798989769876564678954569999887899989875789998772101298997654398784567893298749234569898
+7949899987897999193458989423567893678998766789993987891987653232359876543219895978989109898945678977
+6433949876789891012567898734678954889999855898932299910998754543679987652109999899878919987896989565
+9921234965686789123678987646789967999985543367940198899879987654568998543398898789767898765679995434
+7894349874245878934999998987897898999874321256791987678965498765679659964987657678954987654569874320
+6789498992134568949878999798956999998765432345989436578954349876789789895976543567895698943478965431
+5678986789347679998767987659345899989896543469876523488943234997899898789765432456789989992589996542
+4568995458957898999659876541236789876987675698765414567892123989989998697654321238999878989695987656
+3467954357898967899643988632345898765698876799876203456789349869878976589765799959998765979964598769
+2756953236989998998732199545456789654569987898943212347899998756767897478986987898999874867893239898
+1234892125678999987643298756568999943978999987654433456999876545658789569999896556987653456932199987
+2346789234789998798974369899879879891389989899875544587899987632345678978998765439876542347893989896
+3457895345678987649965459965989765789498965632987655678988998543456799899899887545994321456789876745
+4767896567899895439876598764599954599987654321298967989876987655667898798789998976987450167896565434
+5678998678998794321987699853698863468996543210129878999765499876878987689678979989876571278999432123
+8789109799987679910198985432987654567898756321238989988654345987989976563569965698997692489998945245
+9899239987986567899239974321098765878969895432347899876545234598999876432457894347898786599987656356
+9978998896562433978998765452349878989954996543756789965432125679101989641238989656789998789098767467
+8765487789421012569899878543456989099892987654567897899541016789232998750345678967896549892129879678
+5654346678932123456798987654567899198791998769698946788952125698949879821657899878999656954998998789
+4323234579543544567987898769878998989679899978789434567893434987898765434568954989998767899887679893
+3210123678954656779876789878989987676576799989892123456794545696789876945878963598999878999764569954
+4321234899767787898785698989999876532345678999943035677895676987898989876789012467987989998993298765
+5632345678978998987654567899987654321236899459754129889976789998987697987898943569876590987789109879
+6789767899989659298789698968898965632345995398765234999987898989998545299987897699965421986678999998
+7898989995796542129898789456789876789496789219976545678998987878999432109656789987895439434569989987
+8987599989989953235979892345678987898989898999987656789899996567896563298545698976789598921459878876
+9987679878977894346965921297889599987678936789598767896798987458897785397434767895699987892368965965
+2398798765666989457893932989993498986569545894349978945997854367798996986323656997789876789459954324
+3569899654545678967999899878932987897479678932123499439876543235689129765412345789898965679567895434
+9678998543434589878998789567899876789678989321029567921995432145789099877101256899987654568989998545
+8989987632123478989987678456798765499789895432198979899876543234892987654312345678998963487898987656
+7899964321034569999876573345689876988998789543987898799987869395901298769543659789899872346987898767
+6789875432145678999854321234599989876987689659876797679299998989992989898754578996799965459876789878
+5678986593856789998765410195678998765456598998765636569123987678989876929765678925679876599865678989
+4389997989767895989875431989789987654323457899854323478939876567678954319878989434789998987654577999
+3239899878978934976986549878990198996412368967965434567897654376589978909989299645679899876543456899
+2198788569989129875697698767891239987625459659876567679976543212368899898792198767789799998732345678
+4986676459891098764569987856792345999976569845987678899987987643456789768679019878895678984321234567
+9975434345789197653456976745689559876987778934599789978998998754567897657578999989944569876532345688
+8764323238995987652399875436789698765498899895989894567899439865789976545489789992233456987654556899
+9943210127894598743987664323899989434329956789875923456789329989898765432395699921012345898985678997
+9874321236789987654976543212999878921012345678954212375678998795989897321234999892323456799876789986
+8765432345692198767987432101899867892124589789843201234679877654678989432349899789434567987997899765
+9876744657789029898999843456789456789435678998743212345799865863789678943498788678976679876598988979
+9987855678899999999898754567992345678948789987654323567898754322345567895987654569897798765439567998
+8998976789998789998789865778921256789656894398765634878998763210123498939876543458789899984323467897
+7839987892197678987699876899434347998767893219878765989019854321294989321985432347678999876412359976
+6323498999984569876567987998765456899878992101999878992123965439989878939876521014569899998563458965
+5213459998975698765455698999878567958989989213456989219239876698768767897998762523456789987654767894
+4323467897896789987344569799989879767899878994569894398949987989856456896549654434567894398779898985
+5674598956989898873212897678799998979997656789698765987898999876543267896539765565978999219899989876
+6785679449876987654323679545679997898976545678999876976567976987675378955429876676789878923998978987
+7896789234965598785654568934569876987895434567789989895456895498986489543212989989894767899836569898
+8997893149874429876765678925698775876789212455678998789877912359987599432101296799923458998725456789
+9598954298743212989876789212987654345694301234789989678988909498898678943232345698534569987612345899
+3449765987652101599989899323498765468965412345899864569899998987649789959543456987645989896501246789
+1239876798969292349897978944569976789998543456789753758789897698739899898954567998786798765432357899
+0997989899898989498766567895678987894987654589897542345698789549899998767895998999897899876754456789
+9876591998767678987654456789789998923498765678954321456789678934999877656789899899999932987896578998
+9987410987658569876543345899899989534579876789765432345894567895698965345898788789998921298987689787
+8999329876543456984321256987959876545679987897989876567903456789797893234987675678997899349999897676
+7996534985432367895432397896543998696798998986799987678912369899986932129876554789976798956910998545
+6989549876553456789545679987692129989997899565678999789425458999895891013985432479995487999891986532
+5879956987687677897656789998989239879896789434569349896436567898784692129876321567989256789789897910
+4768899998798788998987899899878998768765698945679234987587899987643989298765410179878145897659799891
+3456798999899899329998947698767569854234567896789154987699998765432478999876321259765236976648645789
+2369987889932998919879434569953498963123456797891023498932987656321367899987433349874358985432125698
+3498965678901987898754323459832987654345567898932934569321298543210458999998944856985767896985334567
+4987654569899876798654218598721098765457678999549895698990987654431567898999659769876878987976455698
+9876353456789954987654327987543179876569989297659789987989998765545678967899879878987989098987866789
+8765232345899893298785436987674567987678997398798678976979999877656789456789989989998992129998979892
+7654101236789789109896545698789678998789876469987567995468899998967894345678995497899764398989989910
+8763212347897678912987656789998989329893989598765456789345678979878965456989764346789875987678999329
+9874323456789567893999767899987798912992198999876567894234789565989876587899953235678989876545678998
+9765654567893457999888998999876587893989987989989878965656895434599998799999892124567898765436799987
+9878765678912346898767889998765466789878876778999989879867896125678989890198789234678959976525689976
+8989878789323456789657678999854345678967465767989899989878989296789976989997678999789545987634569865
+7599989995435767893234569998743234569654343459878789993989879989899875679876567788997656798875698764
+5459899987546789954345679987642157878943212399767678921299768679998764598785454567898987899986789652
+4399799998987898966656789998656788989754103988656567892998656588976543987654323456789599998797898741
+5987678979598967898967897898768899998763219876543456789877543487799432398743212345695421987698999432
+9878589765439456899878965439889978999865434965432345698766432345678943997432101236789439876559876543
+8765478954321366789989874321994567895986549874321236789854321334567899876543232348896598765432987656
+9987569765542345794396543210123458934987656983210123498763210125878910987654643456789987654321098967