Scala3
val allowed: Map[Char, List[Dir]] = Map('>'->List(Right), '<'->List(Left), '^'->List(Up), 'v'->List(Down), '.'->Dir.all)
def toGraph(g: Grid[Char], start: Pos, goal: Pos) =
def nb(p: Pos) = allowed(g(p)).map(walk(p, _)).filter(g.inBounds).filter(g(_) != '#')
@tailrec def go(q: List[Pos], seen: Set[Pos], acc: List[WDiEdge[Pos]]): List[WDiEdge[Pos]] =
q match
case h :: t =>
@tailrec def findNext(prev: Pos, n: Pos, d: Int): Option[(Pos, Int)] =
val fwd = nb(n).filter(_ != prev)
if fwd.size == 1 then findNext(n, fwd.head, d + 1) else Option.when(fwd.size > 1 || n == goal)((n, d))
val next = nb(h).flatMap(findNext(h, _, 1))
go(next.map(_._1).filter(!seen.contains(_)) ++ t, seen ++ next.map(_._1), next.map((n, d) => WDiEdge(h, n, d)) ++ acc)
case _ => acc
Graph() ++ go(List(start), Set(start), List())
def parseGraph(a: List[String]) =
val (start, goal) = (Pos(1, 0), Pos(a(0).size - 2, a.size - 1))
(toGraph(Grid(a.map(_.toList)), start, goal), start, goal)
def task1(a: List[String]): Long =
val (g, start, goal) = parseGraph(a)
val topo = g.topologicalSort.fold(failure => List(), order => order.toList.reverse)
topo.tail.foldLeft(Map(topo.head -> 0.0))((m, n) => m + (n -> n.outgoing.map(e => e.weight + m(e.targets.head)).max))(g.get(start)).toLong
def task2(a: List[String]): Long =
val (g, start, goal) = parseGraph(a)
// this problem is np hard (reduction from hamilton path)
// on general graphs, and I can't see any special case
// in the input.
// => throw bruteforce at it
def go(n: g.NodeT, seen: Set[g.NodeT], w: Double): Double =
val m1 = n.outgoing.filter(e => !seen.contains(e.targets.head)).map(e => go(e.targets.head, seen + e.targets.head, w + e.weight)).maxOption
val m2 = n.incoming.filter(e => !seen.contains(e.sources.head)).map(e => go(e.sources.head, seen + e.sources.head, w + e.weight)).maxOption
List(m1, m2).flatMap(a => a).maxOption.getOrElse(if n.outer == goal then w else -1)
val init = g.get(start)
go(init, Set(init), 0).toLong