Aoc2021_Day15.scala

package aoc2021

import scala.annotation.tailrec
import scala.collection.mutable

object Day15:
  type InputType = Seq[Seq[Int]]

  @main def runDay15: Unit =
    val testData = time("testReady", () => ready(testInput))
    time("testPart1", () => part1(testData)) // should be 40
    time("testPart2", () => part2(testData)) // should be 315

    val data = time("ready", () => ready(input))
    time("part1", () => part1(data))
    time("part2", () => part2(data))

  def ready(input: String): InputType =
    input
      .linesIterator
      .map(_.map(_.toInt - '0').toIndexedSeq)
      .toIndexedSeq


  def part1(data: InputType): Int =
    val cavern: mutable.Map[(Int, Int), Int] = mutable.HashMap()
    cavern.put((0, 0), 0)
    move(data, cavern, 0, 1, 0)
    move(data, cavern, 1, 0, 0)
    cavern.getOrElse((data.size - 1, data.head.size -1), 0)

  def move(data: InputType, cavern: mutable.Map[(Int, Int), Int], x: Int, y: Int, accRisk: Int): Unit =
    if (x < 0 || y < 0 || x >= data.size || y >= data.head.size ||
      accRisk > (x + y) * 5) {
      return
    }
    val currMin = cavern.getOrElse((x, y), Int.MaxValue)
    val additionalRisk = data(x)(y)
    val calcRisk = accRisk + additionalRisk
    if (currMin > calcRisk) {
      cavern.put((x, y), calcRisk)
      move(data, cavern, x, y - 1, calcRisk)
      move(data, cavern, x - 1, y, calcRisk)
      move(data, cavern, x, y + 1, calcRisk)
      move(data, cavern, x + 1, y, calcRisk)
    }

  def part2(data: InputType): Int =
    part1(expend(data))

  def expend(data: InputType) =
    (0 to 4).flatMap(i =>
      data.map(_.map(r => if (r + i > 9) r + i - 9 else r + i))
    ).map(line =>
      (0 to 4).flatMap(i => line.map(r => if (r + i > 9) r + i - 9 else r + i))
    )

  val testInput =
    """1163751742
      |1381373672
      |2136511328
      |3694931569
      |7463417111
      |1319128137
      |1359912421
      |3125421639
      |1293138521
      |2311944581""".stripMargin

  val input =
    """2522414939711849132228579816748823728379124311418111161529639822623219297197656312386831265718721211
      |7119125991574111336131978938112955121422183362398517132564814661292561181421134141499624511692694112
      |3127235291311117732711221595212461287834821864268181236173834391241692536216841911355119911169521283
      |1181155152189111774111156796369418892573474529449114243368393188187466226115613499124591912775811129
      |4511586224241188433132151131912322433627252532818342691614969559425683161447111791121549111146484532
      |5413831212391138911819213166957149213922161137291919117113531382416132121124858321148398497135261112
      |3141189114547157882263926111828665483177711211394322187226895913495654276512911298585113827786152821
      |8139154185512648535373192171842522111781272122639619926142743623114419711811419181134834173248346866
      |6131817237181957336623411991444413536213224516221697817415389416311235139732243655118584442412599145
      |1718527358218195924512318645311122933297111329286687374945374614773121499269961183811521727398185311
      |3481151521221189311126811235832569921337354392175131599321326783387163848295333231182825314233581171
      |5171429946536911171547532412699913195693631981517211295814192796223191999671726151521111228699694495
      |5731624261487716916211124279184347912542257442518826222117821961594127731715739323835513111141439813
      |1369513736556212936295111719858412198182886373247978725451813524111444118681111124821121862374272185
      |3312732241492183466791771757118623969963121992111428649113794614499532441441141428121976111121223453
      |1323512461571182817929939121211713121331191618931184488921591924371235949236168615391825511262223251
      |1844736754225215827118148196139158162168679832813293479114597571111121411671116786889524639436242557
      |4129283884611621139311619918595314638141219118197141982129117931591223136764173918143299992113253194
      |6671213763912343811231319922512514312369111929282929165115129559956116288484182461615162311121211148
      |2181433993113222146117211167911285371166791149379422215815118977498295214751775791959491311282321124
      |1893917971839118469544291628117512951141192191241581996647811817614684113124339455132319119114111833
      |3194199213412152114124178931454213517429615776219211422169278113182121444219111131179993118914924997
      |8219157811341224982161348148111137699341495216731165567471616617941931189972413946971741111281539372
      |3152991117932991922251181118416182931569516111612171922275213185896565291135832617881969216831717171
      |8121312176196962611113271281983885941434758534152637122112688674391761284711462212621329281482136967
      |8912131712629191413717199581682992241791258247943427519627115113181185118893474742221612199416241114
      |2221161716133212262324458823185719629698212514616894944235615445525451113712232992549892442332219993
      |6911428166248291364296657112178221953148681417139715698913134796992291191172362729179523142135611926
      |9193236341295518167899946545124351411258968629291352811613236111815329611335145489738414432321321432
      |6499112739337254948563116237193161125349119739111891452711618219882237913445111154917766361994516299
      |4229111836211397937422211492241292322326927188315516321228751111732223381939852566191913828113619658
      |4833174199812161182295513144544918898488232695919771112444311825381832117171263412399721619352658112
      |7345157387254272529181221134266152214182213139812959885519442556151428591127252113184465879292314161
      |4121465311125417865689227119793711491911121482117238853817572153785844421215789241437331227838558423
      |7523449997166932491931658961611531315911811164945424124681119911514197115371331269117411119195916939
      |9128356914695294253146521193138399121128911413417518232932311581117299227259128821183119275215162333
      |8227711221398832121511812135311996274919173171129616622917349424125661165191393153231221123245228595
      |4661116386124142435676668639172615623882971851132123111533289551472765422233434392326129112321811177
      |1114217118682227172769681833229791919152755377579244542792389334115282624447734191114139324262441812
      |6333952614971166184221548154711268114116731892434448374621261433111364575261971518211189121489159114
      |2643196276215391358127393286244464171242921198641798351383314226421425913793645897272129967531283212
      |5221131154713291512567291442563229223436517211423727422223922197775199547432692311674116717814141189
      |1819812131622311541323862952123752381291168856181384249979548263219194576715373571921367953197516599
      |2698391452599945182154313714292112611651861235644938114519912171341121343514175192421245367422118845
      |1611517822616311553312232428414211183613187966271813393742419936965141554638677392552594157325161112
      |2616289141825669321758111712577299113571118732335179737221439878266941941412314591611896381134423452
      |1527518133297694711977121278995238611939331141152651419529812614622461553336429953291144879147151561
      |6213921184159959912652486789753618112941772164917131997527427312889291111154689437932652465371922993
      |1589621196261511215112194551558331982928756286156353223919126143241698114592611956762736234771235113
      |8165134892151911811992165572238498525759113712471968163566177711133512677122986191491333635131511791
      |5121221111325162242111121122831421669143125569751141468542973371346331562315313969174126843799229968
      |9311826253374818154286131873371269258326126213915219114431182511695131248953693559426228911488261322
      |6591912229221199191129116241691328113778565819111151417179291232116973821215214994781183977822113919
      |2655733341912396361634999147955152969525556354836191314176963932513419228391962945211314943311783881
      |3118513322278916893854417223419174791345313746443425946927242923322912213948211723553112339311144122
      |5393914115613713593912123214127131162129218517429461299451985249947485233933233921659915294223287391
      |1136191983199344171731412199186927561119191219449214216992974151651232175255264491687372483691287841
      |9979467192332442137813919617268197123213515265393883398799246483166214491885851268864128943317146789
      |5137813992711119791889189943164114839536152943452515191991159113143114778121351814419428981641345112
      |1139549732431283823889222929962191941833515674999331261216489474223871213121931162521316251539111719
      |9648979341691798386938175539169825511368121122518621349181719251191923915224299327193775463296152619
      |2311686178629622129357219123853166497242116415121621253426142621912642623299254411219291611241129171
      |7121116711145236394141163917421425189867111859681243149523155243991912931714194994881892515611113358
      |1818136725482517518915422141595131218142168351111612261359827276317281438261183179221111193792271938
      |1139232197366129111613197151415986632374322119127213743117112134123523163898634321495279921127151221
      |1455314773112765478191612311924292793128399375128619158595924411116981162347622141987917914911132244
      |8251232313319753992222152996483791494285141669117359623333132226419358827367424225513193954688331113
      |6111234734513789142262268362695121242113336193619579246538959597918449963359798412951815198197838189
      |1578813352693398121218392393228426881375119641573137139414326439413217641415223545191618221945511142
      |1911342279476333131545622131253816127514398158171126197453819142121921259134342249152113279914226717
      |1181629961152116111141119143162937219335744191534119193429336859258124131916718881314941225494635341
      |3222424734834755922262268951935198255226535129825126496551953155492124112112211175279241996463213119
      |1593211411152338281162891684932212324129938521214175966519115616258481414912622151114391841157816911
      |9141742471551231591911521557311235228349158433361181732488334569224298416181419199789621481599971133
      |6431198331792522412624936255227425156144247631813877119181883195211392367931313972411512151112618967
      |2267991391137261324361516124912921857412152165751315973914128819334272982513357434496931189261186356
      |9731813991313183129492113339525281972169411596682712297561568989281898122432796821932939271461411118
      |9527134412189191252414927113351112113969912114126318294265393127727772965192682248351121436671131949
      |2934611311112198347953125482617172423953569149249533769821945569113994113763296118552242729222291678
      |1119821798911229468135239194762377711532847158111932619121161511191149211189681391816252112113662712
      |6214121139114981831641312844617298831755199745993362226745938625473922122411831659139316811819252196
      |3924199495311615731298928326511113989189152121371528721212116121162831153589349432417428485259451119
      |5671887941514276146115224125348154943341717912911297112361317998423125793133517712118312219932327921
      |3441237411174773198815869762621122911338922117263951832219575348184521221829897832142581331278543895
      |2211991891331676514418141258839222191162231674139112521311364936142331963939355929771951341931514622
      |3747831369635231342124231137812472365447171343913391192962128751842928364413553211815321439116297947
      |3831431319439189562841352632121129765521147556153119234918143471929436282139114141121119611153125122
      |2139868123226218473119733131211449463783356211861164441899319364198832981181141122831449381518499837
      |4838641963928213442551872111262529681463281171145974513318477114933139791111182125546543252119792122
      |1959561559542891384239921218331871441193122413948521139911152336487323225262262552411443442912132194
      |4314213327111115624539372751956191844329316172123933514157637524332315229214279183693125891951974216
      |4121185311217111892962855325351544592933191142755325176455121327454442754548131832152935917115212312
      |1154235973614813121713111278736277174981611157831121152921813123844315723944435135596869139295122111
      |1191164343178491732236111338376338452883881999141122152922792155423112322571421418882716619274477923
      |2942191994588631294975973591371724121221115633251176816331419716599528162253122115638991142695511897
      |1515552919629173654117969541842691298189369498352573484463845716711425113318121951513141136111791614
      |2338151152352731719473221793641322611375192411551164617517155997347919611627517828225538711524251539
      |9161345711264179182921881491169952213815926531391622324113233224122432611247811369169532962163481152
      |1396729196339538914672129619583981562917642411114972418153771391277221143911393951111126922719818115
      |8795124512286141121694662341622161368222432113312766132151575916676412414382618623933742751114159519""".stripMargin