Optimised day 19

[advent-of-code-22.git] / advent09 / Main.hs

diff --git a/advent09/Main.hs b/advent09/Main.hs
index 0f7714dad8a9bd6694671998cccd76ff95c8c991..4273e24d61deb1003d8a2dc88078432ec5d93d4e 100644 (file)
--- a/advent09/Main.hs
+++ b/advent09/Main.hs
@@ -1,4 +1,4 @@
--- Writeup at https://work.njae.me.uk/2022/12/04/advent-of-code-2022-day-4/
+-- Writeup at https://work.njae.me.uk/2022/12/10/advent-of-code-2022-day-9/
 
 import AoC
 import Data.Text (Text)
@@ -15,8 +15,8 @@ type Trace = S.Set Position
 type Path = [Position]
 
 data Rope = Rope 
-  { _headR :: Position
-  , _tailR :: Position
+  { _headK :: Position
+  , _knots :: [Position]
   , _trace :: Trace
   } deriving (Show, Eq)
 makeLenses ''Rope
@@ -31,10 +31,15 @@ main =
       let path = successfulParse text
       let steps = expandPath path
       print $ part1 steps
+      print $ part2 steps
+
+part1, part2 :: Path -> Int
+part1 steps = S.size $ rope ^. trace
+  where rope = ropeSteps (newRope 1) steps
+
+part2 steps = S.size $ rope ^. trace
+  where rope = ropeSteps (newRope 9) steps
 
-part1 :: Path -> Int
-part1 steps = S.size $ rope' ^. trace
-  where rope' = ropeSteps newRope steps
 
 expandPath :: [Direction] -> Path
 expandPath = concatMap expandStep
@@ -43,32 +48,34 @@ expandPath = concatMap expandStep
         expandStep (D n) = replicate n (V2  0 -1)
         expandStep (R n) = replicate n (V2  1  0)
 
-
-manhattan :: Position -> Position -> Int
-manhattan p1 p2 = max dx dy
+lInfNorm :: Position -> Position -> Int
+lInfNorm p1 p2 = max dx dy
   where V2 dx dy = abs $ p1 ^-^ p2
 
 touching :: Position -> Position -> Bool
-touching p1 p2 =  (manhattan p1 p2) <= 1
+touching p1 p2 = (lInfNorm p1 p2) <= 1
 
 towards :: Position -> Position -> Position
 towards p1 p2 = signum $ p2 ^-^ p1
 
-newRope :: Rope
-newRope = Rope { _headR = V2 0 0, _tailR = V2 0 0, _trace = S.singleton (V2 0 0) }
+newRope :: Int -> Rope
+newRope n = Rope { _headK = V2 0 0, _knots = replicate n (V2 0 0), _trace = S.singleton (V2 0 0) }
 
 ropeSteps :: Rope -> Path -> Rope
 ropeSteps rope steps = foldl' ropeStep rope steps
 
 ropeStep :: Rope -> Position -> Rope
-ropeStep rope step = rope & headR .~ hr 
-                          & tailR .~ tailR'
-                          & trace %~ S.insert tailR'
-  where hr = (rope ^. headR) ^+^ step
-        tr = rope ^. tailR
-        tailR' = if tr `touching` hr
-                 then rope ^. tailR
-                 else tr ^+^ (tr `towards` hr)
+ropeStep rope step = rope & headK .~ h
+                          & knots .~ (reverse kts)
+                          & trace %~ S.insert kt
+  where h = (rope ^. headK) ^+^ step
+        (kt, kts) = foldl' knotStep (h, []) $ rope ^. knots -- kts
+
+knotStep :: (Position, [Position]) -> Position -> (Position, [Position])
+knotStep (h, ks) kt = (kt', (kt':ks)) 
+  where kt' = if kt `touching` h
+              then kt
+              else kt ^+^ (kt `towards` h)
 
 -- Parse the input file