Day 21: Step Counter

import json
import re
from copy import copy, deepcopy
from utils.grid.errors import MoveError
from utils.grid.grid import Grid
from utils.grid.pointer import Pointer

class Solver:

    def __init__(self):
        with open('input.txt', 'r', encoding='utf-8') as f:
            self.lines = [line.strip() for line in f.readlines()]
        self.grid = Grid.read_from_lines(self.lines)

    def parse_line(self, line):
        return {

        }

    def run(self):
        total = 0
        first_pointer = self.grid.new_pointer()
        first_pointer.move_to_value('S')
        queue = [first_pointer]
        for i in range(64):
            next_queue = []
            found_cells = []
            for ptr in queue:
                for cell in ptr.current_neighbors():
                    if cell.value == '#':
                        continue
                    if cell in found_cells:
                        continue
                    found_cells.append(cell)
                    new_ptr = ptr.clone()
                    new_ptr.move_to(cell.row, cell.col)
                    next_queue.append(new_ptr)
            queue = next_queue
        return len(queue)


if __name__ == '__main__':
    print(Solver().run())

Then I looked at the output of part 1 in my favorite visualizer, Notepad++, and realized the edges of the diamond/rotated square are all perfectly filled in at n=64. But there's this parity thing going on. scratch paper here

At this point I called my friend, and we looked at some manual cases (one of which demonstrated that there's an enclosed set of . that you have to flood fill to find) and then he did some numpy magic with masks.

Specifically, we called the final area an enclosure, each tile that's exactly equal to the center a garden, and each point a square. The parity of a square is the parity of x+y, and the parity of a garden is its origin's x+y. The order of an enclosure is the number of gardens between the origin and the endpoint along an axis (rounded up since the origin is at the center of one garden).

Let the order be n. Then there are n^2 + (n-1)^2 complete gardens fully inside the enclosure. Of these, n^2 have even parity and (n-1)^2 have odd parity (wlog for what 'even' and 'odd' mean). Furthermore, there are (n-1) per each quadrant of:

• Gardens intersecting the perimeter which are triangles
• Gardens intersecting the perimeter which are pentagons and not located along the axis (we called these 'ugly pentagons')

And there are 4 gardens located on the axis, which are different pentagons.

Two masks are needed to compute all of this, one even-odd parity mask, and one perimeter mask. The mask for ugly pentagons is the mask for the triangle, but inverted; and the mask for the corners is 2x of the mask for the traingle, one rotated the other way from itself.

If the order is odd, all pentagons (including the corners) have even parity, and all triangles have even parity.

So, sum the possibilities for the masks & the allowed squares you can step on, and multiply each one by the # of times it occurs. That's the answer.

Pretty sure we did this in a very complicated way based on what I've seen on reddit, but that's ok. It was a lot of fun tbh.

Part 1 went smoothly enough, just tracking a set of reachable positions for each step. I suppose I could have memoized the neighbor finding, which may have sped up part 2 a bit, but I didn't bother.

Part 2 was an endeavor! I recognized that the expansion of the reachable positions would leave a large area in the middle just flipping between two states, which wouldn't need to be calculated. My initial thought was to only track the positions at the perimeter of this area, reducing the size of the reachable positions from ∝n^2 to ∝n. This actually worked, and I kept it as "part 1.5", but I had forgotten that I would still need to step n times, so this solution just brought brute force from n^3 to n^2...

I then figured that, due to the repetition of the map, with any number of steps that was a multiple of the map size, the reachable states should grow quadratically. Using the "part 1.5" solution, I found 3 points with the same step offset as the goal number of steps, did a quadratic interpolation, and then plugged in the actual number of steps.

module Main (main) where
import qualified Data.Map as Map
import Data.Map (Map, (!))
import qualified Data.Set as Set
import Data.Set (Set)
import Data.List (genericLength)

main :: IO ()
main = do
    input <- readFile "./input.txt"
    putStrLn $ "Part 1: " ++ show (uncurry solve1 $ parseInput input)
    putStrLn $ "Part 2: " ++ show (uncurry solve2 $ parseInput input)

type Coord = (Integer, Integer)

data GardenCell = Plot | Rock deriving (Show, Eq)

type Garden = (Map Coord GardenCell, Integer, Integer)

parseCell :: Char -> GardenCell
parseCell c = case c of
    '.' -> Plot
    'S' -> Plot
    '#' -> Rock
    _   -> error "invalid garden cell"

parseInput :: String -> (Garden, Coord)
parseInput str = ((gardenMap, rows, cols), startingPos) where
    rows = genericLength . lines $ str
    cols = genericLength . head . lines $ str
    indexed = concat [[((r, c), x)| (c, x) <- zip [0..] row] | (r, row) <- zip [0..] (lines str)]
    gardenMap = Map.fromList $ map (\(c, x) -> (c, parseCell x)) indexed
    startingPos = fst . head . filter (\(c, x) -> x == 'S') $ indexed

solve1 :: Garden -> Coord -> Int
solve1 garden startingPos = Set.size finalPositions where
    startingPositions = Set.singleton startingPos
    finalPositions = iterate step startingPositions !! 64 where
        step :: Set Coord -> Set Coord
        step positions = positions' where
            positions' = foldl (getOpenNeighbors garden) Set.empty positions

getOpenNeighbors :: Garden -> Set Coord -> Coord -> Set Coord
getOpenNeighbors garden s (r, c) = s' where
    neighbors = filter (\pos -> getCell garden pos /= Rock) [(r+1, c), (r-1, c), (r, c+1), (r, c-1)]
    s' = foldr Set.insert s neighbors

getCell :: Garden -> Coord -> GardenCell
getCell (gardenMap, rows, cols) (r, c) = gardenMap ! (r `mod` rows, c `mod` cols)

solve1point5 :: Garden -> Coord -> Integer -> Integer
solve1point5 garden startingPos numSteps = finalPositions where
    limit = 10
    singleStart = Set.singleton startingPos
    startingPositions = if even numSteps then singleStart else nextPositions singleStart
    finalPositions = step (startingPositions, numSteps `mod` 2, toInteger (Set.size startingPositions)) where
        step :: (Set Coord, Integer, Integer) -> Integer
        step (positions, n, count)
            | n == numSteps = count
            | otherwise = step (positions', n+2, count') where
            positions' = Set.filter (\pos -> dist pos startingPos > n - limit) $ nextPositions (nextPositions positions)
            newCells = Set.difference positions' positions
            count' = count + toInteger (Set.size newCells)
    nextPositions :: Set Coord -> Set Coord
    nextPositions = foldl (getOpenNeighbors garden) Set.empty

dist :: Coord -> Coord -> Integer
dist (r1, c1) (r2, c2) = abs (r1 - r2) + abs (c1 - c2)

solve2 :: Garden -> Coord -> Integer
solve2 garden startingPos = a * x^2 + b * x + c where
    (_, cycleLength, _) = garden
    (x, offset) = 26501365 `divMod` cycleLength
    f = solve1point5 garden startingPos
    (a, b, c) = quadInterp (f offset, f (offset+cycleLength), f (offset+2*cycleLength))

quadInterp :: (Integer, Integer, Integer) -> (Integer, Integer, Integer)
quadInterp (y0, y1, y2) = (a, b, c) where
    a = (y2 - 2*y1 + y0) `div` 2
    b = (4*y1 - y2 - 3*y0) `div` 2
    c = y0

Part 1 was easy to brute force. I had a similar idea as @scarecrw about not needing to compute the center region, but it didn't scale (as they noted).

I started thinking about the pattern in terms of the pattern that is present in each copy of the grid, and I found the diamond pattern, and even the way it will grow. Here's an example from the test input. The values here are hash values for the state of each cell in the copy of the grid, so each each entry represents an entire grid copy, not a single cell. The numbers are arbitrary and don't have any relationship to each other.

Iteration 44 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,   106,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,   107,   108,   109,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,   107,    39,    47,    39,   109,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,   107,    39,    47,    39,    47,    39,   109,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,   188,   218,    47,    39,    47,    39,    47,   219,    65,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,   112,    39,    47,    39,    47,   191,   114,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,   112,    39,    47,   191,   114,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,   112,   113,   114,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,    65,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 

Iteration 55 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,   106,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,   107,   108,   109,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,   107,    39,    47,    39,   109,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,   107,    39,    47,    39,    47,    39,   109,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,   107,    39,    47,    39,    47,    39,    47,    39,   109,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,   188,   218,    47,    39,    47,    39,    47,    39,    47,   219,    65,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,   112,    39,    47,    39,    47,    39,    47,   191,   114,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,   112,    39,    47,    39,    47,   191,   114,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,   112,    39,    47,   191,   114,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,   112,   113,   114,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,    65,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 
    0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0, 

From here, it's just a matter of figuring out the period of the pattern, picking the pattern that starts on the right offset to get an even number of steps to the target steps, then computing the growth of the pattern over how ever many pattern iterations it takes to get to the max. I have it 90% of the way there, but I'm out of time.

I think in the end, the math I'm doing is pretty much the same (but more complex and less efficient) than the interpolation that @scarecrw did.