Advent of Code 2022-12.scala

import java.io.FileInputStream
import scala.annotation.{tailrec, targetName}
import scala.io.StdIn
import scala.math.abs

val startMarker: Int = 'S' - 'a'
val endMarker: Int = 'E' - 'a'
val cantMove: Int = Short.MaxValue

case class HeightMap(map: Vector[Vector[Int]]):
  def height(point: Point): Int =
    if point.x < 0 || point.x >= map.head.size || point.y < 0 || point.y >= map.size then
      cantMove
    else
      map(point.y)(point.x) match {
        case v if v == startMarker => 0
        case v if v == endMarker => 'z' - 'a'
        case _ => map(point.y)(point.x)
      }

case class CostMap(costs: Map[Point, History]):
  def cost(point: Point): Int =
    costs.get(point).map(_.history.size).getOrElse(cantMove)

  def updated(point: Point, history: History): CostMap =
      CostMap(costs + (point -> history))


case class History(history: Vector[Point]):
  def neighbors(heightMap: HeightMap): Vector[History] =
    val height = heightMap.height(history.last)
    history.last.neighbors.map { point =>
      History(history :+ point)
    }.filter { history =>
      val neighborHeight = heightMap.height(history.history.last)
      1 >= neighborHeight - height
    }


case class Point(x: Int, y: Int):
  def +(that: Point): Point = Point(this.x + that.x, this.y + that.y)

  def neighbors: Vector[Point] =
    Vector(Point(0, 1), Point(0, -1), Point(1, 0), Point(-1, 0)).map(this + _)


def findMarker(map: HeightMap, marker: Int): Point =
  val y = map.map.indexWhere(_.contains(marker))
  val x = map.map(y).indexOf(marker)
  Point(x, y)


@tailrec
def searchShortedPath(map: HeightMap, end: Point, costMap: CostMap, nexts: Vector[History]): Vector[Point] =
  nexts match {
    case next +: rest =>
      val point = next.history.last
      if point == end then
        next.history
      else
        val cost = costMap.cost(point)
        val newCost = next.history.size
        if newCost < cost then
          val newCostMap = costMap.updated(point, next)
          val newNexts = rest ++ next.neighbors(map)
          searchShortedPath(map, end, newCostMap, newNexts)
        else
          searchShortedPath(map, end, costMap, rest)
    case _ => Vector()
  }


def shortestPath(map: HeightMap, start: Point, end: Point): Vector[Point] =
  val history = History(Vector(start))
    val costMap = CostMap(Map(start -> history))
    searchShortedPath(map, end, costMap, history.neighbors(map))


def solve12_1(map: HeightMap): Int =
  val start = findMarker(map, startMarker)
  val end = findMarker(map, endMarker)

  val result = shortestPath(map, start, end)
  result.length - 1


def solve12_2(map: HeightMap): Int =
  val height = map.map.size
  val width = map.map.head.size
  val end = findMarker(map, endMarker)

  val points = (0 until height).flatMap(y => (0 until width).map(x => Point(x, y)))
  points.foldLeft(width * height) { (acc, p) =>
    map.map(p.y)(p.x) match
      case 0 =>
        val result = shortestPath(map, p, end)
        if result.isEmpty then
          acc
        else
          acc min (result.length - 1)
      case _ => acc
  }


@main def solve12(): Unit =
  val in = new FileInputStream("example12-2.in")
  System.setIn(in)
  val inputs = Iterator.continually(StdIn.readLine())
    .takeWhile(line => null != line)
    .map(_.map(_ - 'a').toVector)
    .toVector
  println(solve12_1(HeightMap(inputs)))
  println(solve12_2(HeightMap(inputs)))