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<Vec<Tile>> instead of a linear Vec<Tile>.

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.

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

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

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.

• Day 21, part 1
• Day 21, part 2