Day 9

diff --git a/day09/example.txt b/day09/example.txt
new file mode 100644 (file)
index 0000000..6dee4a4
--- /dev/null
+++ b/day09/example.txt
@@ -0,0 +1,5 @@
+2199943210
+3987894921
+9856789892
+8767896789
+9899965678

diff --git a/day09/input-twitter.txt b/day09/input-twitter.txt
new file mode 100644 (file)
index 0000000..474bd4f
--- /dev/null
+++ b/day09/input-twitter.txt
@@ -0,0 +1,100 @@
+7654345689435693459878789998765434578897598965987654567987654532367891034984323456898764323467899987
+9987466795424989998765678999994323456789997894598943678998543101456789129865212567999765434589989976
+9876578976512976899654569899889437597999876783439895789987654212347999939874101459789899545679878964
+6988989987109865698743456789679545989998965432129789998698795345789979896543212345678998957989567893
+4699798998998754987654568894578959876987896549098659897549987456898856799654323656789987898997678932
+3489657899876543298778679933489798765976989698987545789932196567987645678975834569899986789998799321
+2678999912998432109888789212345679654865678987658734896893987689875436789987765699949875678999895434
+1249878943986554236999899101234598743254568896543210345789298999876648995899876789439764567899996595
+0198767894997669345678998432545696432123656799655321234689109998987756894799987899998643446789989989
+2398758989899798956989996548756987632012345678967434545678919897898767953688998999876532334678979875
+3987649876789987899899987667867975432123456789978945656789998776429879542567899678987710124589569954
+4698659765567896458789998778978986943245667999989976789899897683212989653456894599799899295697698743
+5798798654478987324567899889989998754356778978999987999998796543101298764567895789521998989789987656
+7899996432379998999689999995798999865467889566679898999897689956242349985698999896432987978999898787
+8943987621068989878999998764567899878688993454598769098754567894369467899989998976564996767898789898
+9432197543459878567899876543457976999789432123459853129843456789498998998978987897679765456987653939
+6543987654598767378799987895569765799897693344598764598932458899987899997565476989798654348995462124
+7654698767987656235689599987678934677998989495689895987643567949876789986455365678999985459976321035
+9865679878996543124679445698989323456789878989789986798769679129865699875321234567894976567997532123
+4987897989987674234569326579993212967898767878990298909998989234984789765410165678943998778989644365
+3498976899999865675678912456789909898987657567892349212397698949875679879643276789999879899678955466
+2349875678989876789789109578999898799878546458999998993986566799998789998784356999989964934567966567
+3498764889976987899899298989439765698767423349998876789975435689109994349899867899978943423979897779
+4989986798765498945978987896598674987656101238987564998654320457929893234999878998767952019898799989
+9878998999896329234567896989986543198743234567896432349765932345998789123997989876545694199767659899
+8767899899985410123459945678998432019654455698998543559898743456789678999876693997987789987754546789
+9658998789876522934568934567899543198765568899789654678987654767894589989995432398998899876543235678
+8436789678987699895678923456987654569878779912698765789498765688923478966987621239549987987532123467
+7545679552398989789789501568898765678989889103589899895379978799212367954399543567932495398971012346
+8658795431239975678995413456789878789999993214678965921267989894324456891298654698921249219864124587
+9767896532399864567895324567898989899898765329999954310347999999936967910129765989910198996543234679
+9878976543987653456789435689987791999799976998787895498656898998897898923239899867891397987654356789
+1989988659875472369898956789976510197688989867646979999777987987789999439356987656789986798765577899
+0997699767964321288997897898765439298567997654434569899989876545679986548498999845679765649986788928
+9896549899875432467986899999878998975459877843212345799993988766889999867567987635678984334987999647
+6679432987989876578965789999989987894355965432101234678932399877897891997679996424569832126898999656
+4598949876895987689874677988991096543234986543212345699993999998966890989798987534998721034679898767
+2456798965684598799863456677893497864565799987654586789989898999245699976987899549876543545889659898
+3567987754323459896542107556794998965676798998767678999977767891027988545276989656987954656789543959
+4679876543213456987654212346789899976787997899898789109866456789129876432165678967898766897899932345
+8789765432104587899765423487996768987899976789949899398654345695434975321013459878999977898999891567
+9899876543312345678986567899545656799999875345932998999765236789549875434324578999899988939998789789
+9999998754323478989999878976632445921098763267893976989872123497678987896455689987689999924996579999
+9998959766434567899899989654321235892129654346999895678964334569799698989996789876568976899876468999
+8786549877576778978789997654210126789239765656898764389895445678989549876789899965479765398765347898
+7665433989699989355678999765331234895397978967999865456789578989678939765689999874366972129986656987
+6543212399998994244598899865473346976986989879888976768897699594567998754578899983245983456998968976
+7432101298787893123456789876654957989765492989767597899998895423479899532356789654159899869899899765
+8653232399656799254667999987765798999854301997654398943219974310298764310134798969299789998789789654
+9654343987545978965788998999876899899943219876543129894398765421349899743234567898987678977678699776
+9965556895438767897899877698987998789854345987654436789999886543757987654359678987677549765434578988
+9878667954324556898998766567898987698765456998766545689899998765698998769878989976565439854523456899
+9989899843212346799998843456789875439896567899898659789789899878789439878989998765432129953212367899
+8898987642101237899987642368999654323987678956959767893579788989899323989997899876643298763101234989
+7657898653212345789876543599998875404598799545349878932498656999998939999996853987854789965312345678
+7545679767435656898987665789987654212689895431234989321987645789987898989875432398765679876423656789
+6436569976545787957898976789398786323789996732345795439998534598765997678954321289876789987565767892
+4325467987656798946989987895259865434699987876556789598765423699989876567895410178989898798679878921
+5212345998787899234976599964345986545699898997798899989986534789999987679976551269899987689989989630
+7434459879998910129895498765456987656789649098999999978987649899988998895987643456789893567899997541
+6545669867899432398789329987667998767898932129890198867698756789976899993198759567898762498999876432
+7656779756789546987677934598899879878967943235791987656569987899765656689019998998987651349899998543
+8987998645878959876546899679976567989456899999899876743456798987654334568999876789876540256789798656
+9899875434868998765435678998765459894345798878998765332367899876543223456789125679865431247895679787
+8789994323245999865324789987654398743234987656999873210178978987674105689891013789976562348934567998
+7679986710139899874312398998543219654345697745898765421234568998765216789932123893297678467923456789
+4549875421239789965423987897652109865456986435679989432346879987654347898543434895398799578901969894
+3234987542398679896749876996543323976789875424598998543456896999878657897654545697569987679999898943
+4845986543987545789898965989654435987898764312357897654568945798988789998765756789679899789989787891
+5657987654597634899987654879776846798929976457478998875679034597699891239879867898798776999875676789
+6789098765698745679876543467987957909101987868999899989989129986578994345989978959898665698654345789
+7892139978789856789987832378998969219223798979498787698999998775457989656994989545998543987543259891
+8943234989899867999984321267899878998954689989599678567899899653376878979873293236997632399654348932
+9654545799987978999876546345976989987898796799987543456998798732124567898764139099889321098766567893
+8766656898976799789989658466795699996789895898765432349997654321034678987653298987678992129897678989
+9878789957895434679898769577894569865699996799986651298989765432123799899764987843567789234998799978
+5989992346789523898789989989923498654568989987999879987878998643334896789999876532345678945679894667
+4597641256897654679678999893212987643479678986899998876569897654545945998789976521234589896789923458
+3696532368998999798989898789309865432123569865789987642456789875776799897679985430145698798899765679
+1987893567899878997898765679998979545844598754899999431368899976987898654456976321256798689949876789
+2998954688999767986789654569867498956755987643459876420235789987898998543339865452345897578939997893
+9879767799678955675696543398754356969896798732198765431236798998969987652123986566456976489998989912
+9769899896599843434989432109969197897987899841019876578387897899659896543235697677867895357987878923
+8754957989987651029878953299897989986498998843123998999498956976545798654345698989998943238996467899
+9843245678998743198969954986775878975349987654367899889999549897434899765679789598899652129994359998
+9990156789129858987657899975764567893234999776458998769893236789323999876789892456789543298783234987
+9983245693012967989545798754523456789349877976567987656789945678939889999897941378997665987672135695
+8765456892149879878434598743212377897598765987879876745787896789997767567976532399998987998531046794
+9878967893234998767323569654323458998989854398989985436456789899986643456989544589989898987632397985
+3989878954346789853214598766535567899878969129799999321367899989875432347898765678976789998784459876
+2394989765457899868325799899678678998767998945679898990258999876997655456789876789875789999765678989
+1923499986598999879876892998789899987654567896998767889346789964349876567995987897654567899876789198
+9894678997699998989997921469999999876723456789876656778956799878459998678964398959865978999997894236
+8789789598789987898999892391018899865212347899765544567897892986578969799973129949877899987698976545
+5678994329899876757899789989127789954324456987654323798998910299989359899995439899989912976559987656
+4567893210998765645998678978935699875434597899766214789989321998993234989876599798999101965445999767
+3456789321987653239876545456896789986575689959874325678978949887892123578989987687898929876323799898
+1078896434596542198765432345789894987676793234965456789568999756789012689999876576787898765417678919
+2186989549985421049985321236893913498989890123496567893478987645678923478921987324896799954324589101
+3245678998765434239876434345932101679999954334987678912456798726799434567892393212345789875435678923

diff --git a/day09/input.txt b/day09/input.txt
new file mode 100644 (file)
index 0000000..10120f9
--- /dev/null
+++ b/day09/input.txt
@@ -0,0 +1,100 @@
+9876543234679310943456798433456798998764321357921025689921987899896498799923491297654545679876212347
+6987675036678939874567987012567897899975532467892334567890996789789989679895989398743236789865101456
+5598983124589598765689765423678956789876543568943565678999765395679876598789678987654345998764313689
+4349994235695329976789998634678946789987987679757678989398653234598767459654567998767499899875424568
+3298987656795419899896459745989134568998998789968789699219772123987654398753456899989989689986576789
+2126598787896998788902349897991013457899999997989994567909765244598875697542346789798764593987897897
+1012349898999887567893956999543234967967988656799323459898954355699876989331238996659875691298998956
+4123467999598765456789897987654347899659876545678912398767896466789987979210349965545996789399659235
+3234598985439878567896789198795456789898765434189329987546789998994699867991467894534987899985432123
+4347899876567989678965994349987897899909996521034998675323597899123989659889578943023498999875321014
+5456987997689299989254789498798998999919989992129876543213456789239877545678989432145999998989432345
+6567896798792109892123569987679999998898767889234997854324597994399765434689996565236789987698544456
+7898945689899998763012458976597989987784345678949998985434989219987654323456899854345699996597655678
+8949239796958899954124567895435678996543234567897889876599878998698765435678998765496978989498966899
+9932198965346789867258789932124567987655123458976778987988769876569876646889019887989869979329987957
+9893987896234568954345898743245798998766234567894567899875457987421987756799934999876649868912398946
+8789876789195689875457999655466799679879845678913348987654346987630298867897895988965432946794459435
+7653245678989799876767899867578954568989658799101234999869234598541349998976789876894321987895568910
+9654134789678986988979989878989243456799767895312349898998945987676556789345698765789210398996678999
+8765245696567895399898979999599012367899898986423498776566899999887687990296987984694331239989989888
+9954346897379964219787767893478943479901999597434569653465678999998798921989896593789452398978998767
+0976557898298965398656456794569894998919589439765698542324599689929899439976789432599543987767999656
+2998678999997897987642347895698769867898478929876987321015689599845996598765678953498959876656897545
+9859789899886789998756468998789655456797569999989996432326796498656789987654567894997899965545998968
+7643996798654567949898979659897643245698979989994987543689895329868999998765678949876778964234899879
+5432345697543458957999989545998732124569998967943198964599943210979098969876899129875467996446789989
+8584557987654569767899993123989841034979987654599979989679985341989197854987989039654346789677899899
+7675678998765699898988932034976432149898998863278954393989876832698986543298968998765956799898998789
+8776789439897789909977794255987543298787899985369893212399989764567997432129456789979899989949987699
+9899899524989896429865689356898655398656799876456789105679899895678987521012359891398797778932397569
+9987978939878987898754578967898786499545892998968994323456789989989498432154467910987676567891986478
+9876568998767898999743679879969897987656901239879895544678999879897599543265998934977567456789765399
+7765459876546999898654798989456998998767893446989796665678998768789987654399899949765432345996996989
+6984345995437898759995987892399999439978998669995689776889997656667998969989789899986645567895789878
+5493234989425789647889876891987899321989998778934578987999876543459549998875569789998786688934899767
+4321049875414678936979965789976678910198989989323469998967987652368932987654414579989887999023987656
+5493959954323469324767894679864567891987878993212378999545698710456891099843203458976998942125998543
+7989898965434568913456893589653456789876567992105567894434789322567992129874212367895459993349879432
+8979767996576679102378921098732345898676456789213458943226798763456789298765673456789345989659765310
+9865656889677889293467892129641237899545345698924567899012999654567899349876654597891299978978987821
+8654345679898999989679953498432356789321234567897698978929898765678998956987875698910987567899398932
+7543234578929898878989769976544578996532356878998789567998769888789987897898986789321297478921239543
+5432143456919657667899898989757689987653479989019893478987847999898796789949997996548396567890198656
+8961012367898943456789987698768789998954568998929989569876435445989654678929898987657987678954239967
+7642123456976432367893297569899898769765679456998678978987321334678965799898769598767998999876349879
+8843234568965321245892195479901989859887894367899568989765410123457896893799654329878999899987456989
+9754545678976432496789989567899876543998999578965467999876923245569987932679954212989898789998567894
+9898758789876545789897678998967989862369998679754345699989874356998898921569896102398767678999978943
+9998767894988656896935569549459898973456899789643234987998765459876789932499789213988654589989899432
+8789978943299767965423478921298767895569964996532146986799878598765999893987689929876542679878798921
+9689989652129878987314567890989856789678953987844299875989989679754666789986567898986321299767687899
+6567897541012989796205679999976545679999654598765987654678998798673245678965438957895410987954576778
+4489995432123497654317895798765432459898767679876798763567899899542134589875312346689929996543134567
+3235789543235698785456954349876721248789878789989899874698999998753234696543201234567898987654235678
+2124678965346789896787893212987210187678989892198942976789998769876545987654415345698976798966547899
+1014589878456893987899954301297321234589899999977893988894987456998668998765623466989765429987858943
+2123578989569902398978975212976542475789789998756789199953986568989889679876734569879954312398969652
+3234567897698943469869865323987643567898699999547894349992197689679995566987655698767893202459878943
+4345978998997899598756998764598764678987569898769976998989999796598754324499878999859994312378989965
+5656899569866968965431279879689985789998498769878989876865778965469843212347989898948975459459999876
+6787932499754357896542456998789699899886329856989999765954567894345954353456798797837988678969878997
+7898953987643239919757567899897543998765498745899886644212678901234969754668997655126898789998868998
+8999654996544128929898978934998631349877899635789765432103789212349898975678986543235679892987657899
+9998969875431017999939989325698752356989998523489876643214897423598787896999697655356799921098545989
+9997978996652126789129893216799763467899896412678999765625996545987676569896598766587898943985432877
+9886899429863245679399789109999878978998765324569769889436789679876543456789439898698987899874321466
+8765678910964376899987698998784989989549995445678945996547899798965432387696429999789556789766440355
+7654569899875487999896587899543494399929987678799434987667934977994321234597998998995445678954321234
+6543456789989568998785476998932359239898998989893223699788999866789410165789896987654324479765535445
+5432567899987678997665365767899498998767999699932104567999987654789421256899765698985212356986787568
+4321256789999789886543214456798997987656789569543213469765498765678933345998754109876323567897898679
+5434345678998998765432102349987856798545993498994999578954329878989654658987653212987434878998929989
+6565656799567899876545214498986534987656789597789878989865912989498768767899864324598546789989939999
+7676768923456999987756725987995423898967896986678767993999894994239989878998975435987659896765798989
+8787879734567898998998999876789545789989954965483458912987789892129796989787896745898789975454447678
+9898989656789987889999987494899656789195899754312379909876556789097645692546999856789897654322334589
+8969398797996545978899976323678967991024789876106567899985434567998732101235678969897998854310123459
+7654249899975323456789985214567898942195678998217879999876524567986544212346989989976799965924265678
+8652135987976896568999953107998929769989899999356989998765213456987656434587896492455678999895696799
+9543299876989987689659864315789319898878989876467999989874301345699786547998954321234589987689989892
+7654987664698998796549874323498901997659878987578997779765432456789987856899967432355678996578678921
+9965799543567899987856975434567892987543656898989986569876753697897598767977898645698789975457568910
+9899898632356792198977896565678969876532345689995987432987884789966449878956789876899899764325457891
+6678997653458999299989979876799349865431334678953294321098765789654323989345999988967998955212345789
+4599298964578998988998968987891234986210123689964498753129877897654312993234789999654987742101234699
+3989129765679997667987899998910129876433234589876569876534988998973209894365678919869876543232348789
+2878939876799896543566999879321236997645345679987893997699999529994698765489799201978997654343469892
+3467899987986789432355698765432345698987456789298932398988965410989989876569895412399989765499598921
+5679979999895678921234569989543456789998987891019643599877896329879879999678976523989878979988987932
+6789568987784569990146678998656567899969898989998754988756899499764768998789897949876767989877656893
+9893499976543478989236789239767898998756789878899869876645798987653456799898789498765456799765346789
+6912987665421299879345678949879989976545698765789979865434687898432567895965689398754345678974235699
+5439876543210987769967899999989567895431987543695491984323456989943458954397899999665265667895127678
+6545997654521976458899910989996468986532398654599392395664677979894568965989959876543123456789024568
+7666798766439894346778929878987347897747498765678989987775899866789789999878943997651016567892123456
+8789899876598789234567898969876456798856569876789778998986798754989899989766959898764323456789236768
+9898999987697655139879987655987898949987899987894566989987986543478999876745898759877467897897345679
+8967998799798743016791098943498929956798999898913455678999876542359998765636789542976578949985498789
+7649876549899752145892987632349547897899498769101234589212987656767899443323498931987989539876569893
+8432987632999863236789876545678956789902349854213455678903498987898954321014567890198994321987689912

diff --git a/day09/smoke_basin.sh b/day09/smoke_basin.sh
new file mode 100755 (executable)
index 0000000..30af6fc
--- /dev/null
+++ b/day09/smoke_basin.sh
@@ -0,0 +1,176 @@
+#!/bin/bash
+
+set -u
+
+filename="${1:-example.txt}"
+
+exec 3<"$filename"
+
+width=0
+height=0
+declare -a map
+
+while read -u 3 row; do
+    for (( a=0; a<${#row}; a++ )); do
+        map+=("${row:$a:1}")
+    done
+    ((height+=1))
+    ((width=${#row}))
+done
+
+display_map() {
+    for (( a=0; a<$height; a++ )); do
+        for (( b=0; b<$width; b++ )); do
+            offset=$((($a*$width)+$b))
+            if [ ${low_spots[$offset]+abc} ]; then
+                tput bold
+            fi
+            echo -n "${map[$offset]}"
+            if [ ${low_spots[$offset]+abc} ]; then
+                tput sgr0
+            fi
+        done
+        echo
+    done
+}
+
+declare -A low_spots
+
+get_low_spots() {
+    # we entirely cheat, and just store the index positions
+    # in the array low_spots
+    low_spots=()
+
+    for (( y=0; y<$height; y++ )); do
+        for (( x=0; x<$width; x++ )); do
+            offset=$((($y*width)+$x))
+            is_lowest=$(check_adjacents $offset)
+            if [ $is_lowest -eq 0 ]; then
+                low_spots[$offset]=$((${map[$offset]}+1))
+            fi
+        done
+    done
+}
+
+declare -a basins
+
+check_adjacents() {
+    local offset=$1
+    # we'll get y by dividing offset by width
+    local y=$((offset/$width))
+    # and x by taking the remainder of that
+    local x=$((offset%width))
+    local lower_count=0
+
+    if [ $y -gt 0 ]; then
+        # check spot above us
+        above_offset=$(((($y-1)*$width)+$x))
+        if [ ${map[$above_offset]} -le ${map[$offset]} ]; then
+            ((lower_count+=1))
+        fi
+    fi
+    if [ $y -lt $((height - 1)) ]; then
+        # check spot below us
+        below_offset=$(((($y+1)*$width)+$x))
+        if [ ${map[$below_offset]} -le ${map[$offset]} ]; then
+            ((lower_count+=1))
+        fi
+    fi
+    if [ $x -gt 0 ]; then
+        # check to our left
+        left_offset=$((offset-1))
+        if [ ${map[$left_offset]} -le ${map[$offset]} ]; then
+            ((lower_count+=1))
+        fi
+    fi
+    if [ $x -lt $((width - 1)) ]; then
+        # check to our right
+        right_offset=$((offset+1))
+        if [ ${map[$right_offset]} -le ${map[$offset]} ]; then
+            ((lower_count+=1))
+        fi
+    fi
+
+    echo "$lower_count"
+}
+
+get_surrounding() {
+    local offset=$1
+    local -n __been_checked="$2"
+    local -n __to_check="$3"
+    local x=$((offset % $width))
+    local y=$((offset / $width))
+
+    __offset=$((($y*$width)+$x))
+
+    if [ $x -gt 0 ]; then
+        check_offset=$((($y*$width)+($x-1)))
+        if [ ! ${__been_checked[$check_offset]+abc} ] && [ ${map[$check_offset]} -ne 9 ]; then
+            __to_check[$check_offset]=1
+        fi
+    fi
+    if [ $y -gt 0 ]; then
+        check_offset=$(((($y-1)*$width)+$x))
+        if [ ! ${__been_checked[$check_offset]+abc} ] && [ ${map[$check_offset]} -ne 9 ]; then
+            __to_check[$check_offset]=1
+        fi
+    fi
+    if [ $x -lt $(($width-1)) ]; then
+        check_offset=$((($y*$width)+$x+1))
+        if [ ! ${__been_checked[$check_offset]+abc} ] && [ ${map[$check_offset]} -ne 9 ]; then
+            __to_check[$check_offset]=1
+        fi
+    fi
+    if [ $y -lt $(($height-1)) ]; then
+        check_offset=$(((($y+1)*$width)+$x))
+        if [ ! ${__been_checked[$check_offset]+abc} ] && [ ${map[$check_offset]} -ne 9 ]; then
+            __to_check[$check_offset]=1
+        fi
+    fi
+    __been_checked[$__offset]=1
+    unset __to_check[$__offset]
+}
+
+find_basins() {
+    # we find the basin by using the low_spots.
+    for basin_mid in "${!low_spots[@]}"; do
+        basin_x=$(($basin_mid % $width))
+        basin_y=$(($basin_mid / $width))
+        declare -A checked
+        declare -A to_check
+
+        # add surrounding blocks to the to_check list
+        to_check[$basin_mid]=1
+        while [ ${#to_check[@]} -gt 0 ]; do
+            for offset in "${!to_check[@]}"; do
+                get_surrounding $offset checked to_check
+            done
+        done
+        # this *should* have avoided all 9s and got anything else in the area that we wanted, so the checked array
+        # at this point should contain the number of elements we care about
+        basins+=("${#checked[@]}")
+        checked=()
+    done
+}
+
+sum_risk() {
+    sum=0
+    for lowpoint in "${low_spots[@]}"; do
+        ((sum+=$lowpoint))
+    done
+    echo "$sum"
+}
+
+get_low_spots
+display_map
+
+echo
+echo "The risk is: $(sum_risk)"
+find_basins
+
+OLDIFS="$IFS"
+IFS=$'\n'
+sorted=($(sort -n <<<"${basins[*]}" | tail -n 3))
+
+echo "The largest 3 basin sizes are: ${sorted[@]}"
+echo "Multiplied together they are: $((${sorted[0]} * ${sorted[1]} * ${sorted[2]}))"

diff --git a/day09/task.txt b/day09/task.txt
new file mode 100644 (file)
index 0000000..4ac0c28
--- /dev/null
+++ b/day09/task.txt
@@ -0,0 +1,72 @@
+--- Day 9: Smoke Basin ---
+These caves seem to be lava tubes. Parts are even still volcanically active; small hydrothermal vents release smoke into the caves that slowly settles like rain.
+
+If you can model how the smoke flows through the caves, you might be able to avoid it and be that much safer. The submarine generates a heightmap of the floor of the nearby caves for you (your puzzle input).
+
+Smoke flows to the lowest point of the area it's in. For example, consider the following heightmap:
+
+2199943210
+3987894921
+9856789892
+8767896789
+9899965678
+Each number corresponds to the height of a particular location, where 9 is the highest and 0 is the lowest a location can be.
+
+Your first goal is to find the low points - the locations that are lower than any of its adjacent locations. Most locations have four adjacent locations (up, down, left, and right); locations on the edge or corner of the map have three or two adjacent locations, respectively. (Diagonal locations do not count as adjacent.)
+
+In the above example, there are four low points, all highlighted: two are in the first row (a 1 and a 0), one is in the third row (a 5), and one is in the bottom row (also a 5). All other locations on the heightmap have some lower adjacent location, and so are not low points.
+
+The risk level of a low point is 1 plus its height. In the above example, the risk levels of the low points are 2, 1, 6, and 6. The sum of the risk levels of all low points in the heightmap is therefore 15.
+
+Find all of the low points on your heightmap. What is the sum of the risk levels of all low points on your heightmap?
+
+Your puzzle answer was 541.
+
+--- Part Two ---
+Next, you need to find the largest basins so you know what areas are most important to avoid.
+
+A basin is all locations that eventually flow downward to a single low point. Therefore, every low point has a basin, although some basins are very small. Locations of height 9 do not count as being in any basin, and all other locations will always be part of exactly one basin.
+
+The size of a basin is the number of locations within the basin, including the low point. The example above has four basins.
+
+The top-left basin, size 3:
+
+2199943210
+3987894921
+9856789892
+8767896789
+9899965678
+The top-right basin, size 9:
+
+2199943210
+3987894921
+9856789892
+8767896789
+9899965678
+The middle basin, size 14:
+
+2199943210
+3987894921
+9856789892
+8767896789
+9899965678
+The bottom-right basin, size 9:
+
+2199943210
+3987894921
+9856789892
+8767896789
+9899965678
+Find the three largest basins and multiply their sizes together. In the above example, this is 9 * 14 * 9 = 1134.
+
+What do you get if you multiply together the sizes of the three largest basins?
+
+Your puzzle answer was 847504.
+
+Both parts of this puzzle are complete! They provide two gold stars: **
+
+At this point, you should return to your Advent calendar and try another puzzle.
+
+If you still want to see it, you can get your puzzle input.
+
+You can also [Share] this puzzle.