Skip Navigation

🍡 - 2023 DAY 17 SOLUTIONS -🍡

Day 17: Clumsy Crucible

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

9

You're viewing a single thread.

9 comments
  • 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)
    
You've viewed 9 comments.