Sped up day 21 by only simulating the boundary

[advent-of-code-23.git] / advent21 / Main.hs

diff --git a/advent21/Main.hs b/advent21/Main.hs
index ac3b637eee13e4b1b7ce180d4428c700ad92c142..ee247dd832e8a962eb2dbf8f6387e04cf339e4d8 100644 (file)
--- a/advent21/Main.hs
+++ b/advent21/Main.hs
@@ -44,7 +44,8 @@ part2 rocks bounds start =
   where (V2 minR _, V2 maxR _) = bounds
         tileWidth = maxR - minR + 1
         (doubleTileSteps, extraSteps) = divMod 26501365 (tileWidth * 2)
-        positions = (!! (tileWidth * 2 + extraSteps)) $ iterate (takeSteps rocks bounds) start
+        start1 = takeSteps rocks bounds start
+        (_, positions) = (!! (tileWidth + (extraSteps `div` 2))) $ iterate (take2Steps rocks bounds) (start1, start1)
         
         evenFilled = countInRange bounds (V2 0 0) positions
         oddFilled = countInRange bounds (V2 tileWidth 0) positions
@@ -78,6 +79,11 @@ countInRange bounds delta cells =
 shiftBounds :: (Position, Position) -> Position -> (Position, Position)
 shiftBounds (a, b) d = (a ^+^ d, b ^+^ d)
 
+take2Steps rocks bounds (boundary, old) = (boundary2 S.\\ old, new)
+  where boundary1 = takeSteps rocks bounds boundary
+        boundary2 = takeSteps rocks bounds boundary1
+        new = S.union old boundary2
+
 takeSteps :: Grid -> (Position, Position) -> Grid -> Grid
 takeSteps rocks bounds places =
   S.filter (notAtRock rocks bounds) $ S.unions $ S.map adjacents places