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