Aoc2021_Day09.scala

package aoc2021

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

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

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

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

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

  def part1(data: InputType): Int =
    data.zipWithIndex
      .flatMap((row, x) =>
        row.zipWithIndex.filter((col, y) =>
          !near(data, x, y).exists(n => n <= col)))
      .map(_._1 + 1).sum

  def near(data: InputType, x: Int, y:Int): Seq[Int] =
    Seq.empty[Int]
      :+ (if (x > 0) data(x - 1)(y) else Int.MaxValue)
      :+ (if (y > 0) data(x)(y - 1) else Int.MaxValue)
      :+ (if (x < data.size - 1) data(x + 1)(y) else Int.MaxValue)
      :+ (if (y < data.head.size - 1) data(x)(y + 1) else Int.MaxValue)

  case class Point(x: Int, y: Int)

  def part2(data: InputType): Int =
    val basins: mutable.Set[mutable.Set[Point]] = mutable.Set.empty
    data.indices
      .flatMap(x =>
        data.head.indices
          .map(y => findBasins(data, basins, x, y))
      )
    basins.toList.map(_.size).sorted(Ordering.Int.reverse)
      .zipWithIndex
      .filter((n, i) => i < 3)
      .map(_._1)
      .reduce(_ * _)

  def findBasins(data: InputType, basins: mutable.Set[mutable.Set[Point]], x: Int, y: Int): Unit =
    val point = Point(x, y)
    if (basins.exists(set => set.contains(point))) return
    if (data(x)(y) == 9) return
    val sets =
      basins.filter(set => nearPoints(data, point).exists(np => set.contains(np)))
    basins --= sets
    val union: mutable.Set[Point] = sets.foldLeft(mutable.Set.empty)(_ ++ _)
    union.add(point)
    basins.add(union)

  def nearPoints(data: InputType, p: Point): Set[Point] =
    Set.empty[Point]
      + (if (p.x > 0) Point(p.x - 1, p.y) else null)
      + (if (p.y > 0) Point(p.x, p.y - 1) else null)
      + (if (p.x < data.size - 1) Point(p.x + 1, p.y) else null)
      + (if (p.y < data.head.size - 1) Point(p.x, p.y + 1) else null)

  val testInput =
    """2199943210
      |3987894921
      |9856789892
      |8767896789
      |9899965678""".stripMargin

  val input =
    """1012349767989212989898755567989899469867895798763210134789998765323234567898999876899994334996876898
      |2343498754979939876789643459876678998656679987654341945679989994210123499987898965678989129885565797
      |3456987643467898765698912399765569997543578999965459896789876789422236988976997654555678998764303556
      |4568998892348999654987929976543457976432347899876598789999865689934545976865889543434589999654212347
      |5679999989459998799876898765432546987643456964988798679878454567898659895434678932123459899769323467
      |8798989878967899989765789876641234798658767893299976589965323458989798789323459321012398788998934699
      |9987779767898969876543899989210145699767879954398765499854212345678989698912568943123999676797898789
      |9876568956789656987674989998321237989878989769987644298764343456899776567893679543239897565456789895
      |8987879545897649898775678987534459876999797998765432139865454567896562478989789767398796454345689934
      |7998989656965434679876789698545698765435646799987521019876565678964321234578999878989655333238789123
      |6899998787896567989987896569756899876321234798797543125987776789943210123467898989876543210129893234
      |5789989898987678992399943457968998986430345697698654234599889899875421234678967893989754621345689499
      |4569876979999899321987632349878987654321456789598766545999999967965432348989444954599965632346793987
      |3359765567899986439876545467989598769432387893459897656789197659879765467999323495989876543457892976
      |1298954456789976567997676578992349898953498954567939768991019543989897567898934989677987674569979765
      |0987543345698987678998789699321234987899999765678923979432198632193987678997949878456798765678965563
      |1295432223467898989329898965432349875687891978789914989594987641012398899756898767397999877899654321
      |9976521012589999994310997897643498754576990989899895699989986532123459987645789656235798999949776210
      |8765432193499998989429976798767697663445789993998789789769876543236567998436789543129987898932997321
      |9876599989567987679598865889879988532234899892197698993456987754757679876545896543098655467899798542
      |6997988678979876589987664578999876710123456789989587902567998765678896987666965432139832348978598767
      |5398976597989996457896543567899985432548567999878376899978989898789955699877998743298753467965439989
      |2109865456899954356789212488999996654567898989763234578999876959893234567998999654987654678977846795
      |3298754347698743234995423567898999765878999879954345679987654545954345678949999765698765789498656934
      |4987643234569532109896534589987899878989998767895656789899963439765479989321987999899886894398767895
      |5999732125797643998789665690235678989597987656789897898787892129879567899430976878932987942109998989
      |9899654236898659878679978921398789995346798745679998989686989247987678987699865767991098993297549567
      |9798764357999799764559899634989899876459978434567999878595678956798789298989954356789129989398732349
      |8679876567899987652545689545978954987898764323689598764443589767899990139878943125678939878998549998
      |7567999878999875431234597699767893298999875444595497653212699878967689998767892014568997567897698767
      |4349743999998989545345789987656892109989987655689298764443478989543569875456992123467893456998987656
      |5498642478997987659557994976546799213567899766893129878764567895432498767366789234567892379899998545
      |7987643467986598998678932986435678934999999877893234999895678976321239743235678945778921295789989766
      |8999784589875439298789999984324567899878999998975549899976789765442398654134567896899990124678966987
      |9989895799954320129892987674101698998767989999986798789987899877653459768012346789998789235679445698
      |9976976899875434789910196543218789987545678989897987693498998998764578987434569897679678947893234989
      |9895989945986545678932989954567899999327899876799876589569987899878989986589698954598569658932129875
      |8789996434597657789549878899978959876438998965498765467989976789989998997679997893697678968954398654
      |9678987525799869897659965678989543998549897654329984376799895678999877679799876789798789878965986543
      |6578975436789978998998754567899432129756789543210986245789754568998768579898765688999899989876997541
      |3458987547994399789897643459998943239867899655329875347898743456987654456987654357899998999989898532
      |2367897698965987698765432568987894498978998785435985456789632348998712345699875176799987888998798643
      |1278929789979987579987643456896789987899219987546797578996540456989101234578987245678976567689659794
      |2389019899798998431099764568965679876567999987656898789897621239863212348799498656899765496567969875
      |3499999945697899592129975878976798996456789999877949895698754349654323456894398767899974375459899986
      |4699889322986799989298996989987987894345899931988932976789865598779949697965989898999876212358789997
      |5989778901995899878967987891299876543234999890199531989896986679898898989899875979989983102345679899
      |6974567899876789765254598990123989432149898789234949996945497789987676365798954569879954913656798798
      |9865679954987899873143459789234598543298789678959898954321249899876564284567892379867899894967897626
      |9978989943498987632012345679356987655987674567998797895430159988975432193456901298745448799899998435
      |8799598891279996543245656799459998899898562356798676798654398767986753012367912987532335679790129546
      |7653456789468998754356968988998999998754421334899545689986989754399854323568929899621026994689939657
      |8732568996567999866767899976787899879983210123987634598999878975456975434679439765432187893567898968
      |6641238987679899987998998765656789959876321249892123567898769876568998568789945976683298912348997899
      |5420237899898798998929789854545678935995434399783013458987654987678987689897896989794569325689876789
      |4321256789987677999434698783234579123987545987654124567899773598789799789956898999895978934698765867
      |6453399899866566789645789542125989012998659898543235689978981459893569893245939310989899545987654656
      |7664678998754315679956798683256892199899798798654348789567890345991096920139019329879789759876543545
      |8765789329893204567897999794347953989798998669965459893468921256789975321998998998768678999965432134
      |9876799934984512378998998987467899876677897549876567892379942967898976439876546987654456789876541014
      |7997899899976678589429997896568998765456799832987679901239899899976597689989769876543245679987432123
      |6798998778987789789998786889678999854345789654598789212398786788965498799999892986431045789998544255
      |5679097655598890999854655678989986532269898766899894323987665677994329899878931997642123990987655345
      |6989298743469991998743344567898794310178929877899985434596543456789212997767899876543237891998967458
      |7899999432345789769532123578987654324239910998998976645987856578999101986457901987984556789879798767
      |8939898931457898754321012489998988435545891299987989787998967689878919764346793499875698994565679878
      |9549767892388959769643235678979876545656789987996599898909989799867899843234589599986789573234567989
      |8699843459578949898764547989967987678769899876789467999329999898756898754565678987699895432123478996
      |9987432578989324939865768999856798989878998765498988989998998996546789965678789195497976543457569985
      |9876543467899439125989879298745899798989999986567899878767987989435667989789899096976898659568978964
      |7997754689998998934599989349656987667997898997678999969659876879323456899891998989865789798979989323
      |6459975899897867896999998498767996549875567998989298754345965469212356789910987678984599987899895212
      |4347976998785756789888976569979875420984379899992197643239879878901235679329876587943498976898754353
      |2136797987684345698767897678989985321975498798953985421023989989213446789999965456892347895789867965
      |3245698979567268997656898989994495439876798667899876572124599995324657899879876767891456789891979896
      |4399999865443155689747679999932398646989986456789987743245678975435778998765997989932367899930198789
      |5987898654321044599435568999893497657999876587892398954346789986545989549874989398795456789421987678
      |9876559865433123478924467898789598799978998788931459876457895498679897656989873245689579896592396577
      |9765431976576434569012346987678999978567899899892369997569989319989789767899965356789789987989987456
      |9876210987687949993123459876587899865456999998789478987678978901998578979979876467899896899878996567
      |9994321298789898789234599965486799654349789997699989998789767899877469989567987568945954989868987978
      |9989432349898767678945989874395678943254678976579999999894345678965347893459998979435943979654398999
      |8878953756999654589659878984234567892133578932467899899965456989878456892398789989569899767993209879
      |7767899897998765678998966796545678921012489991238998799878568998989767921499678997698798955879919867
      |6456789919879878789997654297657899543123456789449989679989879767899879932987568998987667543467897658
      |5347892109865989897998764349868999854234969997678976568998995545689989893986456789996558312345976646
      |5456789298754393976899987656979998765349898998899985469987654436578996799987878999985432101269875535
      |7967896987543212345789298767989999875498767999998999329898963123459865678998989999876543212998764323
      |9899964298955901234890199898996789976799856898987888998769894064998754567899999987987654339876543214
      |8789654399899892945992989999875678987989543987656567997656789129789653498998919876398767478987854435
      |7678969978786789896789878987954589499878956798745456889548899998678964567897929995459878567999876567
      |4599998765634896789898769876543489398767897987432345678937898763567899679956798889567999879876987678
      |3699976543012345678996545997694678987656999876543456789656789854579998989767987678998988998765498789
      |2789998432127469789989932198775799996546799987698678999897898765998997899879876569999976989874309899
      |3679876543235678999879894299889899987656789698909789768998929879876545978998965456989865768965212978
      |4567998754546799198768789989992998798987996569919897657999012989987834569887996349876743457894324567
      |5788979865657893239855678979921987659598985456899976545878934998798965799796789298765632386789535678
      |6789767979898994998434589467890997543479965345689397834457899877679986987645693129874341245678946799
      |8898756989949789876545789345699875412667891234594298321347999967567899768434679096543210146799758892
      |9999547990134689989686892157987654323458964345679109432656789753478987654323489987676543235789899901""".stripMargin