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
7 comments
  • Rust

    https://github.com/Treeniks/advent-of-code/blob/master/2023/day21/rust/src/main.rs

    I reused my Grid struct from day 17 for part 1, just to realize that I'll need to expand the grid for part 2 so I awkwardly hacked it to be a Vec> instead of a linear Vec.

    I solved task 2 by reading through the reddit thread and trying to puzzle together what I was supposed to do. Took me a while to figure it out, even with literally looking at other people's solutions. I wrote a lengthy comment about it for anyone that's still struggling, but I honestly still don't really understand why it works. I think I wouldn't have solved it if I didn't end up looking at other solutions. Not a fan of the "analyze the input and notice patterns in them" puzzles.

  • Python

    The data today has a special property, which allows for a fast solution. This won't work on other data, including the example data in the problem description.

    1645 line-seconds.

    import collections
    import math
    
    from .solver import Solver
    
    
    class Day21(Solver):
      first_star_steps: int
      second_star_steps: int
      lines: list[str]
    
      def __init__(self):
        super().__init__(21)
        self.first_star_steps = 64
        self.second_star_steps = 26501365
    
      def presolve(self, input: str):
        self.lines = input.splitlines()
    
      def solve_first_star(self) -> int | str:
        positions = {(i, j) for i, line in enumerate(self.lines) for j, c in enumerate(line) if c == 'S'}
        for _ in range(self.first_star_steps):
          next_positions = set()
          for i, j in positions:
            for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
              if not 0 <= i + di < len(self.lines):
                continue
              if not 0 <= j + dj < len(self.lines[i]):
                continue
              if self.lines[i + di][j + dj] == '#':
                continue
              next_positions.add((i + di, j + dj))
          positions = next_positions
        return len(positions)
    
      def solve_second_star(self) -> int:
        positions = {(i, j) for i, line in enumerate(self.lines) for j, c in enumerate(line) if c == 'S'}
        modulus = self.second_star_steps % len(self.lines)
        points_to_extrapolate = (modulus, modulus + len(self.lines), modulus + len(self.lines) * 2)
        values = []
        for step_count in range(modulus + len(self.lines) * 2 + 1):
          if step_count in points_to_extrapolate:
            values.append(len(positions))
          next_positions = set()
          for i, j in positions:
            for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
              ni = i + di
              nj = j + dj
              if self.lines[ni % len(self.lines)][nj % len(self.lines)] == '#':
                continue
              next_positions.add((ni, nj))
          positions = next_positions
        a = (values[2] - values[1] *2 + values[0]) // 2
        b = values[1] - values[0] - 3 * a
        c = values[0] - b - a
        cycles = math.ceil(self.second_star_steps / len(self.lines))
        return a * cycles * cycles + b * cycles + c
    
  • 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
    
  • Nim

    My part 2 solution assumes the input has an unimpeded shortest path from the center of each garden section to its corner, and to the center of its neighbor. The possible destinations will form a diamond pattern, with "radius" equal to the number of steps. I broke down the possible section permutations:

    • Sections that are completely within the interior of the diamond

      • Even number of sections away from the starting section
      • Odd number of sections away from the starting section
    • Sections containing the points of the diamond

    • Depending on the number of steps, there may be sections adjacent to the point sections, that have two corners outside of the diamond

    • Edge sections. These will form a zig-zag pattern to cover the diamond boundary.

      • "Near" edge sections. These are the parts of the zig-zag nearer to the center of the diamond.
      • "Far" edge sections. These won't occur if the edge of the diamond passes perfectly through the corners of the near edge sections.

    I determined how many of each of these should be present based on the number of steps, used my code from part 1 to get a destination count for each type, and then added them all up.

7 comments