Scala3

Learning about scala-graph yesterday seems to have paid off already. This explicitly constructs the entire graph of allowed moves, and then uses a naive dijkstra run. This works, and I don’t have to write a lot of code, but it is fairly inefficient.

import day10._
import day10.Dir._
import day11.Grid

// standing on cell p, having entered from d
case class Node(p: Pos, d: Dir)

def connect(p: Pos, d: Dir, g: Grid[Int], dists: Range) = 
    val from = Seq(-1, 1).map(i => Dir.from(d.n + i)).map(Node(p, _))
    val ends = List.iterate(p, dists.last + 1)(walk(_, d)).filter(g.inBounds)
    val costs = ends.drop(1).scanLeft(0)(_ + g(_))
    from.flatMap(f => ends.zip(costs).drop(dists.start).map((dest, c) => WDiEdge(f, Node(dest, d), c)))

def parseGrid(a: List[List[Char]], dists: Range) =
    val g = Grid(a.map(_.map(_.getNumericValue)))
    Graph() ++ g.indices.flatMap(p => Dir.all.flatMap(d => connect(p, d, g, dists)))

def compute(a: List[String], dists: Range): Long =
    val g = parseGrid(a.map(_.toList), dists)
    val source = Node(Pos(-1, -1), Right)
    val sink = Node(Pos(-2, -2), Right)
    val start = Seq(Down, Right).map(d => Node(Pos(0, 0), d)).map(WDiEdge(source, _, 0))
    val end = Seq(Down, Right).map(d => Node(Pos(a(0).size - 1, a.size - 1), d)).map(WDiEdge(_, sink, 0))
    val g2 = g ++ start ++ end
    g2.get(source).shortestPathTo(g2.get(sink)).map(_.weight).getOrElse(-1.0).toLong

def task1(a: List[String]): Long = compute(a, 1 to 3)
def task2(a: List[String]): Long = compute(a, 4 to 10)