Skip Navigation

🦶️ - 2023 DAY 21 SOLUTIONS - 🦶️

Day 21: Step

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

7

You're viewing a single thread.

7 comments
  • Scala3

    task2 is extremely disgusting code, but I was drawing an ugly picture of the situation and just wrote it down. Somehow, this worked first try.

    import day10._
    import day10.Dir._
    import day11.Grid
    
    extension (p: Pos) def parity = (p.x + p.y) % 2
    
    def connect(p: Pos, d: Dir, g: Grid[Char]) = 
        val to = walk(p, d)
        Option.when(g.inBounds(to) && g.inBounds(p) && g(to) != '#' && g(p) != '#')(DiEdge(p, to))
    
    def parseGrid(a: List[List[Char]]) =
        val g = Grid(a)
        Graph() ++ g.indices.flatMap(p => Dir.all.flatMap(d => connect(p, d, g)))
    
    def reachableIn(n: Int, g: Graph[Pos, DiEdge[Pos]], start: g.NodeT) =
        @tailrec def go(q: List[(Int, g.NodeT)], depths: Map[Pos, Int]): Map[Pos, Int] =
            q match
                case (d, n) :: t =>
                    if depths.contains(n) then go(t, depths) else
                        val successors = n.outNeighbors.map(d + 1 -> _)
                        go(t ++ successors, depths + (n.outer -> d))
                case _ =>
                    depths
    
        go(List(0 -> start), Map()).filter((_, d) => d <= n).keys.toList
    
    def compute(a: List[String], n: Int): Long =
        val grid = Grid(a.map(_.toList))
        val g = parseGrid(a.map(_.toList))
        val start = g.get(grid.indexWhere(_ == 'S').head)
        reachableIn(n, g, start).filter(_.parity == start.parity).size
    
    def task1(a: List[String]): Long = compute(a, 64)
    def task2(a: List[String]): Long = 
        // this only works for inputs where the following assertions holds
        val steps = 26501365
        assert((steps - a.size/2) % a.size == 0)
        assert(steps % 2 == 1 && a.size % 2 == 1)
    
        val d = steps/a.size
        val k = (2 * d + 1)
        val k1 = k*k/2
    
        def sq(x: Long) = x * x
        val grid = Grid(a.map(_.toList))
        val g = parseGrid(a.map(_.toList))
        val start = g.get(grid.indexWhere(_ == 'S').head)
        val center = reachableIn(a.size/2, g, start)
    
        // If you stare at the input enough, one can see that
        // for certain values of steps, the total area is covered
        // by some copies of the center diamond, and some copies
        // of the remaining triangle shapes.
        // 
        // In some repetitions, the parity of the location of S is
        // the same as the parity of the original S.
        // d0 counts the cells reachable in a center diamond where
        // this holds, dn0 counts the cells reachable in a center diamond
        // where the parity is flipped.
        // The triangular shapes are counted by dr and dnr, respectively.
        //
        // The weird naming scheme is taken directly from the weird diagram
        // I drew in order to avoid further confusing myself.
        val d0 = center.count(_.parity != start.parity)
        val dr = g.nodes.count(_.parity != start.parity) - d0
        val dn0 = center.size - d0
        val dnr = dr + d0 - dn0
    
        // these are the counts of how often each type of area appears
        val r = sq(2 * d + 1) / 2
        val (rplus, rminus) = (r/2, r/2)
        val z = sq(2 * d + 1) / 2 + 1
        val zplus = sq(1 + 2*(d/2))
        val zminus = z - zplus
    
        // calc result
        zplus * d0 + zminus * dn0 + rplus * dr + rminus * dnr
    
You've viewed 7 comments.