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