Aoc2021-day15.scala

package lascala.aoc2021.day11_20.day15

import scala.collection.immutable.SortedSet

type Position = (Int, Int)
case class RiskLevelMap(
  m: Map[Position, Int],
  xSize: Int,
  ySize: Int,
)

extension (p: Position)
  def neighbors: List[Position] = p match
    case (x, y) => List(
      (x - 1, y),
      (x + 1, y),
      (x, y - 1),
      (x, y + 1),
    )

private val memo: collection.mutable.Map[Position, Int] =
  collection.mutable.Map.empty[Position, Int]

extension (m: RiskLevelMap)
  def apply(p: Position): Int = m.m(p)
  def totalRisk: Int =
    def loop(currentRisk: Int, visited: Map[Position, Int], toVisit: SortedSet[Position]): Int =
      println(s"===> visited: $visited, toVisit: $toVisit currentRisk: $currentRisk")
      val next = toVisit.head
      if next == (m.xSize - 1, m.ySize - 1) then currentRisk
      else 
        val nextRisk = currentRisk + m.apply(next)
        val visited1 = visited + (next -> currentRisk)
        val toVisit1 = toVisit.tail ++ next.neighbors.filter(m.m.contains).filterNot(visited.contains)
        loop(nextRisk, visited1, toVisit1)
    loop(0, Map.empty, SortedSet((0, 0))(Ordering.by(p => (m(p), p))))

  def enlarge: RiskLevelMap =
    val map = for
      ((x, y), r) <- m.m
      i <- 0 to 4
      j <- 0 to 4
    yield
      (x + i * m.xSize, y + j * m.ySize) -> wrap9(r + i + j)
    RiskLevelMap(map.toMap, m.xSize * 5, m.ySize * 5)

def wrap9(n: Int): Int =
  if (n <= 9) n else wrap9(n - 9)

object RiskLevelMap:
  def parse(s: String): RiskLevelMap =
    val map = s.split("\n").zipWithIndex.flatMap { case (line, y) =>
      line.zipWithIndex.map { case (c, x) =>
        (x, y) -> c.toString.toInt
      }
    }.toMap
    val xSize = map.keys.map(_._1).max + 1
    val ySize = map.keys.map(_._2).max + 1
    RiskLevelMap(map, xSize, ySize)


def solve1(s: String): BigInt =
  val map = RiskLevelMap.parse(s)
  println(map)
  println((0,0).neighbors.filter(map.m.contains))
  map.totalRisk
end solve1

def solve2(s: String): BigInt =
  val map = RiskLevelMap.parse(s)
  val fullMap = map.enlarge
  fullMap.totalRisk
end solve2

@main def part1: Unit =
  val ans = solve1(input)
  println(ans)

@main def part2: Unit =
  val ans = solve2(input)
  println(ans)

val input = 

Aoc2021-day15Test.scala

package lascala.aoc2021.day11_20.day15

import minitest.SimpleTestSuite
import hedgehog.minitest.HedgehogSupport
import hedgehog.*

object Day15Test extends SimpleTestSuite with HedgehogSupport:

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

  example("day15 - solve 1") {
    solve1(testInput) ==== 40
  }

  example("day15 - solve 2") {
    solve2(testInput) ==== 315
  }

  example("day15 - solve 1 - real") {
    val s = """11199
99199
91199
91999
91111"""
    solve1(s) ==== 10
  }