I feel like it’s almost everyday that I can say something like: “Oooh, I thought it was going to be easy, but then it’s not!” Well… That’s certainly the case for today.
Part 1
Show challenge - day 9, part 1
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?
Here’s the provided input. It’s quite long so don’t try to scroll through:
Show input - day 9
7857679876545987643256789767894592129875432345678987543234598754567892349964345943210127899434954345
6746567987796997664146789656953989349754321234799998999109989843467993498895659854322345678949893233
5434458998989876543234599545899878998654320123678999878998975432358789987789798765563456899998789102
4523347999978989854845678938798767999865431334567898965987654321345678965678969887678567943987678913
3210156899866698766789789325679656799876565457678967994398775210123889323589943998789689659876568995
6521238789654569977899999734569545689987897568989356789219885424344994214567892129899898798765456789
7434345699943456998988997645698734567899998689396467896323965435656789105878964298901949899876569893
6575656897899569879567998787987645678954349891296598985434597545669993216789995987912934978987679932
7689787896798979967467899898998776789763212989987679876545698756778954323899989876899899867899889321
8799898965987898652379997999319887898765343679998993997677789767889997434568979785679759878998995432
9890969754346789743498985689929998969876954567899612398798999878997986545679765654349643989876799546
6921349943235997655697674579898789456989895678996543459989989989876597876789654321238952099865688957
5432677890196898766987543498766564349998789989989965569878979998765498997899766610177893198764567898
6563456789989929877999432349654323298987678996569896698767767898754349898949877532456789299853466789
9874569899878912988998921234965210197656588923456789987654356789895456789234998743767899985432345789
5986798998767893499987990159874343299743486794578994596543246899976567890126789654879998976545456789
4987987979878989598896889346989554987632375689689753987854345678997688921347899767989987987698578899
3299876768989569987675679956987665696521234678999762598985457899998789435489965988999875698987679998
2198765656795498795454567897898796985432345989689653459876578999989899876567894599998764529498789767
4987654345694349654323479989999989876568656796577994967989789789865956989978953456989843213359895456
5698963236589298765474589767898767987899978965466789878999896678954545792989432349876543101234976569
7987892123478929898765678945698656898923989654245699989865934569532234891094310123998753219759897678
9876431012567912999876789234987745769944598765656899992994325378931046979195465255999654398998789989
2998542123878901987987892129876434657895679876787998901989101289542123468987654349898765987899699997
0129656939989212396598943012965421347896890987898987899879312348953235779899799998769879895446599876
1298789898994324987439984329876532456797951298989896798768993567894345698799987859897998654323478965
2349898767965739876519876545997544587898942349876645987656789978999456998688976545976569785434567894
6556987657899846987326987656789665688939993498965535698545678989898969887567997437895459876745678912
7679876546798957899634898787899878999123989987854324987435789898767898765434589546942345998858989923
9798765435677998998546799898999989932019876796543219876566796649656987654323578967921959219967895894
9899985324576789987656789969789999893998765987632102989678895432347976543413489978949898939879976789
5999764412345789999978898658679899789897544598543212398789976541239897632101257899998677899989999992
4998743101789899999989999543498798676789432987654353459899987982349798543212345945989556789999987890
9899654313599999898798998764987676565878941299765478967999999864598689955323969899876435678999876789
9798774323458998789657869879996543454567890129876567898998999765987577896539898788987548789498765412
7659885457667897697546556998999652123678921236987678999857899879875476789798767687898959892349974301
8969986569789934589432345987898843016789432345698989999645989998764325678999654576789767921298765213
9878997679899845678921239896987652145689543456789495878999879999875434789998793434599898932349654324
7989898989998756789210198765698653235678964567994324567989767878996545898987672125678999654598765455
6796789997569879898431259874789864356789986788965212789877653456789656997698543234799998765999986776
4345679986456998987652349989899975456789998899976523499765442346678968989549765745678999879895697987
3239798765345987899767898991998996767899899976595434598654321245567899679939876967989999998754569998
4998998743229876788979977892987987979998789987989545679865410123456954567899987899798789439865678999
9867897651013954567898765679896798989887679999878956798754321236569432978999899999657678913976789588
8756789543129876779999976798795459998756568898767898899895435345678999899987652198745459904698893467
7545679956789997889999989989689979876545459799956799989876546789989989799876543987832345799799942343
4234567897893498999989898976567899987434345678945678978987678893299875678987959876421234678989431012
3123499998912989568976797985498998654321236789136789357899899932129654567999899987210124569878942134
4534589999109875477895986543387998767410147991045995212999978994298943478998799995341234678967899245
6645679989212954356954397432136799878924756789127894329889765789987912345789678998532399989456898956
8767789878999864167891298543245678989865667993236789498765634698976793456896567997543987894345987897
9878896569989873298999987659656789899976798954345678999654323567895689597925457987659876789239976789
9989956469878999349898798798767895789989899765766989998765212678954578989012349999769985679198765678
8797643359767898956789659899889954578999999879878999979975323467953468978923498999898654568999654356
7659451298656987999896543945999876899998799989989679865986654578921234569654987899987643247899875268
8943210987649876789987969324567987899979569894394597654987785679210456678969976789999532126799994345
9874349876436545899999898901234598998767498765213986543499898789431567899798765678998673035698765567
8765456985321434578999767892345679987656349954323997432345999896542398927679876789987662129999898689
9876567984310123678998756789459789897543234965549876541069899987665489312568999899876543298789959799
6998779876321234789987545678998999789732179878699987432198789998796569103459878944998654397699649899
5329899965435345679876434589237998698943467989989997543987678899898678923999965432139865987578932978
9212999876547656989864323489456987567894588999878998659876545799959989549889876744014979876467894567
8901987987956787998765434569569765456799679998767898767965434689345497698778989865923989989878975678
7899876598767899899896545678998764345678989987656799979854324593212398987656197979894597694999989799
6798765439878998789987756989998653234567893299549893298768435689323459987643236898789789543212399897
5689876323989987698999897897987643123456999398767989349976566795434567899765345797678997659865459976
4768993212398634567897998976698431014597898999878978956987789999595978949876459986567798767986598785
3656789325987545678976579654569542198789967899989657898999891298989899234987898875435699878997999654
2345679434597656989865457993498674599895456789994345999997910987678789199898987654323989999109897743
9456898995679878999974325689598788789944345699875467899876329876545698989769398543219878889298765432
8967997889799999999989434578959999895321234589976799923995498768434567979653239876498956778999876321
7898986678989319988996546989732012943210165678997891014986987654321345767992123987987434567899987210
6569975454878998767897999997653223959323456989898989123987898773210123459989344899876123456789974323
5498764343568989856989878989885439898965567899769678934598959765621245768979956798985012345678965434
4329873212345678934976965678976599767896898997654569945679349878854359879567897987654126787789878545
5497983101296789129865134569988987656799999898763456797895219989976567993456899698643245698999989967
6986543212989993298754245678999876545678996789432345898994398999987678912345798549954356999578998798
7897765329979894359765657989798765434799874896544578919989497989999789923456796539865677899989987689
8959875498767799459878768995679877321898763789655789329878976878999899894667987621979788989999876598
9245986997658678967989899434899943210989654678966898999867864567897998789779998710989899878999988987
9967899876546567898992990123799994332378969989878967789956323456795498678989899931296999769889999876
9898902995423488959101989235698989944569998799989555698743212345899987567896789892345987658778999975
8789899875212679543219878946987869895878997689995434987652101596998795456965679793459876543567898764
7678789984343789954398767899876556789989876578976720198763212678987654357894565689567987652489999753
6565678995458997895987656678997435678997535459987631679874343489398965457893434578979876543459998764
6434569998767896789895434567954323459789421299876543567989654799569896767952123456893998654598989978
5323456789878945998754323459873212355694320678987654689998765678998789899543234567892198766987778999
4212378999989239876543212398765101234589431489998765999999896789987678978954345678963019879876567889
2103569129894345998632101239954323445678932378929879899889987899876589667895656789954198998767452878
3414678998795456896549543398765654756789965469434998768779998953987334556996778999865987869654321267
4925789987689987987698994999878965678999876589546987654667899932993212346889899432978986759769834346
9896789764567898998997789899989876789897987678959896543558999899854301235678989543989975345998765756
6789897643476799109976678788997987896796599789998765432445898798765472345789678959899894234599879877
5678975432125689398765567677896498965989434999987654321234789679876567887896567899798753145689989988
4567996645054578987654323456954329254578923459876543210123689543987879998987378965699432015678998999
3456789752123567898765104569543210123469212369987656521234597652398989879998567894987653123789567789
2127897654345878949874325678998323345578903578998867432345689321239998969999678943499868944695465698
4578998765456789234965456789976534559679214678959998553456789875347897657898789452349979855894324567
5689439877677890125987767894987865698789325889546799767868895987656789545689894321348998766893212398
6789521998889921236799878923598978999895456789634569878978934599867996534899943210767999987964323569
Here’s the solution to part 1:
using Pipe: @pipe
hmap = @pipe input |> strip |> split(_, "\n")
hmap = @pipe string.(hmap) .|> collect .|> parse.(Int, _) |> hcat(_...) |> transpose
v, h = size(hmap)
hmap[
hmap .< [repeat([10], h)'; hmap[1:(v-1),:]] .&&
hmap .< [hmap[2:v, :] ; repeat([10], h)'] .&&
hmap .< [repeat([10], v) ;; hmap[:,1:(h-1)]] .&&
hmap .< [hmap[:,2:h] ;; repeat([10], v)]
] .+ 1 |> sum |> print
Part 2
Show challenge - day 9, part 2
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?
Here’s the solution to part 2:
using Pipe: @pipe
hmap = @pipe input |> strip |> split(_, "\n")
hmap = @pipe string.(hmap) .|> collect .|> parse.(Int, _) |> hcat(_...) |> transpose
v, h = size(hmap)
function lowest_points(trace_map)
trace_map .<= [repeat([15], h)' ; trace_map[1:(v-1),:]] .&&
trace_map .<= [trace_map[2:v, :] ; repeat([15], h)'] .&&
trace_map .<= [repeat([15], v) ;; trace_map[:,1:(h-1)]] .&&
trace_map .<= [trace_map[:,2:h] ;; repeat([15], v)] .&&
trace_map .!= 9
end
function basin_size(basin)
mark_value = 15 # Any high number is fine
trace_map = copy(hmap)
trace_map[basin] = mark_value
while true
trace = lowest_points(trace_map) .&& .!lowest_points(hmap) .&& trace_map .!= mark_value
if !any(trace)
break
end
trace_map[trace] .= mark_value
end
return count(==(mark_value), trace_map)
end
basins = findall(==(true), lowest_points(hmap))
@pipe basin_size.(basins) |> sort |> _[end-2:end] |> *(_...) |> print