Aoc2021-day15.scala

package lascala.aoc2021.day11_20.day15

import scala.collection.immutable.SortedSet

type Position     = (Int, Int)
type RiskLevelMap = Map[Position, 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),
      )

extension (m: RiskLevelMap)
  def xSize: Int = m.keys.map(_._1).max + 1
  def ySize: Int = m.keys.map(_._2).max + 1
  def totalRisk: Int =
    val destination = (xSize - 1, ySize - 1)
    @annotation.tailrec
    def loop(
        toVisit: SortedSet[(Int, Position)],
        visited: Map[Position, Int],
    ): Int =
      val (risk, pos) = toVisit.head
      if pos == destination then risk
      else
        val neighbors =
          pos.neighbors.filter(m.contains).filterNot(visited.contains)
        val visited1 = visited + (pos -> risk)
        val toVisit1 = toVisit.tail ++ neighbors.map { neighbor =>
          val risk1 = risk + m(neighbor)
          (risk1, neighbor)
        }
        loop(toVisit1, visited1)
    loop(SortedSet((0, (0, 0))), Map.empty)

  def enlarge: RiskLevelMap =
    val (xS, yS)           = (xSize, ySize)
    def wrap9(n: Int): Int = if n <= 9 then n else wrap9(n - 9)
    for
      ((x, y), r) <- m
      i           <- 0 to 4
      j           <- 0 to 4
    yield (x + i * xS, y + j * yS) -> wrap9(r + i + j)

object RiskLevelMap:
  def parse(s: String): RiskLevelMap = s
    .split("\n")
    .zipWithIndex
    .flatMap { case (line, y) =>
      line.zipWithIndex.map { case (c, x) =>
        (x, y) -> c.toString.toInt
      }
    }
    .toMap

def solve1(s: String): BigInt =
  val map = RiskLevelMap.parse(s)
  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
  }