Day 22: A Long Walk

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • cvttsd2si@programming.dev
    2·
    1 year ago

    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