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.

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

C

That did not go accordingly to plan! Took hours and a bunch of notepad paper 😅

Major mistakes:

• Off by one reading input so I was missing a row.
• Messing up the area calculations for certain cases, like double-counting some diagonals or not counting them. Suppose those are off by ones too.
• Not realizing the odd grid size meant the tick/tock states would alternate between repetitions of the grid within the covered area.

Some code:

static char map[GSZ][GSZ];	/* all reachable replaced by \0 */
static int nobs[2][2];		/* [in/out diamond][even/odd t] */
static int sz;

/*
 * We call the big diamond in the input (covered by part 1) the 'inside 
 * diamond' and the diamond found by combining the corner pieces on the
 * 'outside diamond'. For both we found the number of unreachable tiles
 * (obstacles, 'nobs') for the even and odd time steps.
 *
 * The total number of tiles covered in t is (t+1)^2 - accounting for
 * the checkerboard reachability pattern. With the part 1 and 2
 * questions, this exactly covers a certain square amount of diamonds
 * (ndia*ndia).
 *
 * Finding out which types of diamonds and in what state (odd/even) is
 * the tricky bit, e.g. the state alternates between the repeating grids
 * because the grid size is uneven.
 */
static uint64_t find_reach(uint64_t t)
{
	int odd = t&1;
	uint64_t ndia = t/sz*2 +1;

	return (t+1)*(t+1) -
	    (ndia/2 +!odd) * (ndia/2 +!odd) * nobs[0][0] -
	    (ndia/2 + odd) * (ndia/2 + odd) * nobs[0][1] -
	    ndia*ndia/4 * nobs[1][0] -
	    ndia*ndia/4 * nobs[1][1];
}

https://github.com/sjmulder/aoc/blob/master/2023/c/day21.c

Haskell

Got it at last! I had the idea pretty early, but reckless assumptions gave me a lot of wrong results. Rather a lot of hard-coding here, but since this is another “works in this case” input, who cares!

8.988 line-seconds today (could be better with some golfing)

import Data.Array.IArray (Array)
import qualified Data.Array.IArray as Array
import Data.Foldable
import Data.Map (Map)
import qualified Data.Map as Map
import Data.Set (Set)
import qualified Data.Set as Set

type Pos = (Int, Int)

readInput :: String -> Array Pos Char
readInput s =
  let rows = lines s
   in Array.listArray ((-65, -65), (65, 65)) $ concat rows

walk :: Bool -> Int -> Pos -> Array Pos Char -> Int
walk parity steps start input = go 0 0 Set.empty $ Set.singleton start
  where
    go :: Int -> Int -> Set Pos -> Set Pos -> Int
    go a i seen cur
      | i > steps = a
      | Set.null cur = a
      | otherwise =
          let cur' =
                Set.fromList $
                  [ p
                    | (y, x) <- toList cur,
                      (dy, dx) <- [(-1, 0), (0, -1), (0, 1), (1, 0)],
                      let p = (y + dy, x + dx),
                      valid p,
                      p `Set.notMember` seen'
                  ]
              seen' = seen `Set.union` cur
              a' = if even i == parity then a + Set.size cur else a
           in go a' (i + 1) seen' cur'
    valid p = Array.inRange (Array.bounds input) p && input Array.! p /= '#'

part2 :: Array Pos Char -> Int
part2 input = total
  where
    steps = 26501365
    total =
      let qOdd = 2 * sum [1 .. 101149]
          qEven = sum [1 .. 202299] - qOdd
          full =
            4 * qEven * fullTile True
              + (4 * qOdd + 1) * fullTile False
          smallCorners =
            202300
              * ( count True 64 (65, 65)
                    + count True 64 (65, -65)
                    + count True 64 (-65, 65)
                    + count True 64 (-65, -65)
                )
          largeCorners =
            202299
              * ( count False 195 (65, 65)
                    + count False 195 (65, -65)
                    + count False 195 (-65, 65)
                    + count False 195 (-65, -65)
                )
          points =
            count True 130 (65, 0)
              + count True 130 (-65, 0)
              + count True 130 (0, 65)
              + count True 130 (0, -65)
       in full + smallCorners + largeCorners + points
    count parity steps start = walk parity steps start input
    fullTile parity = walk parity maxBound (0, 0) input

main = do
  input <- readInput <$> readFile "input21"
  print $ walk True 64 (0, 0) input
  print $ part2 input

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