day 20 reflections

mstksg · Dec 30, 2024 · 37e586e · 37e586e
1 parent f845c9a
commit 37e586e
Show file tree

Hide file tree

Showing 3 changed files with 66 additions and 20 deletions.
diff --git a/bench-results/2024/day20.txt b/bench-results/2024/day20.txt
@@ -1,19 +1,19 @@
 >> Day 20a
 benchmarking...
-time                 40.47 ms   (38.84 ms .. 41.22 ms)
-                     0.995 R²   (0.979 R² .. 1.000 R²)
-mean                 41.80 ms   (41.15 ms .. 43.37 ms)
-std dev              1.933 ms   (950.7 μs .. 3.288 ms)
-variance introduced by outliers: 12% (moderately inflated)
+time                 34.12 ms   (32.70 ms .. 35.54 ms)
+                     0.994 R²   (0.983 R² .. 1.000 R²)
+mean                 34.98 ms   (34.32 ms .. 36.48 ms)
+std dev              1.880 ms   (715.8 μs .. 3.355 ms)
+variance introduced by outliers: 18% (moderately inflated)
 
 * parsing and formatting times excluded
 
 >> Day 20b
 benchmarking...
-time                 393.2 ms   (380.9 ms .. 402.4 ms)
-                     1.000 R²   (1.000 R² .. 1.000 R²)
-mean                 393.2 ms   (391.2 ms .. 396.0 ms)
-std dev              2.621 ms   (1.132 ms .. 3.309 ms)
+time                 405.5 ms   (393.5 ms .. 431.8 ms)
+                     0.999 R²   (0.999 R² .. 1.000 R²)
+mean                 393.5 ms   (390.1 ms .. 399.7 ms)
+std dev              5.956 ms   (1.238 ms .. 7.831 ms)
 variance introduced by outliers: 19% (moderately inflated)
 
 * parsing and formatting times excluded

diff --git a/reflections/2024/day18.md b/reflections/2024/day18.md
@@ -16,17 +16,7 @@ data BFSState n = BS
   -- ^ queue
   }
 
-bfs ::
-  forall n.
-  Ord n =>
-  -- | neighborhood
-  (n -> Set n) ->
-  -- | start
-  n ->
-  -- | target
-  (n -> Bool) ->
-  -- | the shortest path, if it exists
-  Maybe [n]
+bfs :: forall n. Ord n => (n -> Set n) -> n -> (n -> Bool) -> Maybe [n]
 bfs ex x0 dest = reconstruct <$> go (addBack x0 Nothing (BS M.empty Seq.empty))
   where
     reconstruct :: (n, Map n (Maybe n)) -> [n]

diff --git a/reflections/2024/day20.md b/reflections/2024/day20.md
@@ -0,0 +1,56 @@
+Because this is a "race track" with no branching, finding the path to the end
+can be a straightforward DFS with no-takebacksies:
+
+```haskell
+cardinalNeighbsSet :: Point -> Set Point
+cardinalNeighbsSet p = S.fromDistinctAscList . map (p +) $
+    [ V2 (-1) 0 , V2 0 (-1) , V2 0 1 , V2 1 0 ]
+
+racePath :: Set Point -> Point -> Point -> Maybe [Point]
+racePath walls start end = go Nothing start
+  where
+    go :: Maybe Point -> Point -> Maybe [Point]
+    go prev here = do
+      next <- S.lookupMin candidates
+      (here :)
+        <$> if next == end
+          then pure [end]
+          else go (Just here) next
+      where
+        candidates = maybe id S.delete prev $ cardinalNeighbsSet here `S.difference` walls
+```
+
+Since our racepath is one continuous line, a cheat therefore involves
+"pinching" the line so that you skip straight over one segment of the line. So,
+we can basically iterate over each point in the line and imagine if we jumped
+ahead N spaces. If the time saved by jumping N spaces minus the real-world
+distance is greater than the threshold, it's a legitimate cheat.
+
+```haskell
+mannDist :: Point -> Point
+mannDist x y = sum (abs (x - y))
+
+mannNorm :: Point -> Int
+mannNorm = mannDist 0
+
+findCheats :: Set Point -> Point -> Point -> Int -> Int -> Maybe Int
+findCheats walls start end len thresh = do
+  path <- racePath walls start end
+  pure . sum . snd $ mapAccumR go (0, M.empty) path
+  where
+    go :: (Int, Map Point Int) -> Point -> ((Int, Map Point Int), Int)
+    go (i, xs) x =
+      ( (i + 1, M.insert x i xs)
+      , M.size $
+          M.filterWithKey (\y j -> i - j - mannDist x y >= thresh) $
+            xs `M.restrictKeys` S.mapMonotonic (+ x) diamond
+      )
+    diamond = floodFill (S.filter ((<= len) . mannNorm) . cardinalNeighbsSet) (S.singleton 0)
+```
+
+Our `mapAccumR` here iterates from the end of the list with the index (`i`) and
+a map `xs` of points to the index where that point is on the racetrack. At each
+point, we output the number of cheats: it's the `xs` filtered by points legally
+jumpable within a given distance, and then further filtered where the jump in
+index `i - j` minus the time to travel `mannDist x y` is greater than the
+threshold for counting the cheat.  In the end we sum all of those outputs.