More tinkering

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

diff --git a/advent11/Main.hs b/advent11/Main.hs
index 03d3e6936c1d7251966b25d55e797b6591f6d9c5..41b28f1f4a2ab73f1707bd8ad84dd69b6c503168 100644 (file)
--- a/advent11/Main.hs
+++ b/advent11/Main.hs
@@ -1,17 +1,15 @@
--- Writeup at https://work.njae.me.uk/2023/12/10/advent-of-code-2023-day-10/
+-- Writeup at https://work.njae.me.uk/2023/12/11/advent-of-code-2023-day-11/
 
 import AoC
 
-import Data.List
-import Data.Maybe
+-- import Data.List
+-- import Data.Maybe
 import Linear (V2(..), (^+^), (^-^))
 import qualified Data.Set as S
 
 type Position = V2 Int -- r, c
 
-type Gals = S.Set Position
-data Galaxies = Galaxies Gals (Position, Position) 
-  deriving (Show)
+type Galaxies = S.Set Position
 
 main :: IO ()
 main = 
@@ -20,72 +18,63 @@ main =
       let galaxies = mkGalaxies text
       -- print galaxies
       -- print $ expandGalaxies galaxies 10
+
+      -- print $ allDist $ expandGalaxies 2 galaxies
+      -- print $ allDist $ expandGalaxies (10^6) galaxies
+
       print $ part1 galaxies
       print $ part2 galaxies
 
 part1, part2 :: Galaxies -> Int
-part1 galaxies = allDistances gs
-  where (Galaxies gs _) = expandGalaxies galaxies 2
+part1 = allDistances . expandGalaxies 2
+part2 = allDistances . expandGalaxies 10e6
 
-part2 galaxies = allDistances gs
-  where (Galaxies gs _) = expandGalaxies galaxies (10^6)
-
-allDistances :: Gals -> Int
-allDistances gs = case S.minView gs of
-  Nothing -> 0
-  Just (g, gs') -> (S.foldl' (addDist g) 0 gs) + allDistances gs'
-  where addDist g1 acc g2 = acc + distance g1 g2
+allDistances :: Galaxies -> Int
+allDistances gs = snd $ S.foldl' addGalaxy (S.empty, 0) gs
+  where addGalaxy (seen, d) new = 
+            (S.insert new seen, S.foldl' (addDist new) d seen)
+        addDist g1 d g2 = d + distance g1 g2
 
 distance :: Position -> Position -> Int
 distance g1 g2 = abs dr + abs dc
   where (V2 dr dc) = g1 ^-^ g2
 
 
-expandGalaxies :: Galaxies -> Int -> Galaxies
-expandGalaxies galaxies scale = galaxies''
+expandGalaxies :: Int -> Galaxies -> Galaxies
+expandGalaxies scale galaxies = galaxies''
   where er = emptyRows galaxies
-        galaxies' = expandRows galaxies er (scale - 1)
+        galaxies' = expandRows galaxies er scale
         ec = emptyCols galaxies'
-        galaxies'' = expandCols galaxies' ec (scale - 1)
+        galaxies'' = expandCols galaxies' ec scale
 
 emptyRows, emptyCols :: Galaxies -> [Int]
-emptyRows (Galaxies gs (V2 r0 _, V2 r1 _)) =
-  [ r | r <- [0..r1] , S.null $ onRow gs r ]
-  where r1 = S.findMax $ S.map (\(V2 r _) -> r) gs
-emptyCols (Galaxies gs (V2 _ c0, V2 _ c1)) =
-  [ c | c <- [0..c1] , S.null $ onCol gs c ]
-  where c1 = S.findMax $ S.map (\(V2 _ c) -> c) gs
+emptyRows galaxies = [ r | r <- [0..r1] , S.null $ onRow galaxies r ]
+  where r1 = S.findMax $ S.map (\(V2 r _) -> r) galaxies
+emptyCols galaxies = [ c | c <- [0..c1] , S.null $ onCol galaxies c ]
+  where c1 = S.findMax $ S.map (\(V2 _ c) -> c) galaxies
 
-onRow, onCol :: Gals -> Int -> Gals
-onRow gs r = S.filter (\(V2 r' _) -> r == r') gs
-onCol gs c = S.filter (\(V2 _ c') -> c == c') gs
+onRow, onCol :: Galaxies -> Int -> Galaxies
+onRow galaxies r = S.filter (\(V2 r' _) -> r == r') galaxies
+onCol galaxies c = S.filter (\(V2 _ c') -> c == c') galaxies
 
 expandRows, expandCols :: Galaxies -> [Int] -> Int -> Galaxies
-expandRows (Galaxies gs (V2 r0 c0, V2 r1 c1)) expansions scale =
-  Galaxies gs' (V2 r0 c0, V2 (r1 + nExp) c1)
-  where nExp = length expansions * scale
-        gs' = foldr (shiftRows scale) gs expansions
-expandCols (Galaxies gs (V2 r0 c0, V2 r1 c1)) expansions scale =
-  Galaxies gs' (V2 r0 c0, V2 r1 (c1 + nExp))
-  where nExp = length expansions * scale
-        gs' = foldr (shiftCols scale) gs expansions
-
-shiftRows, shiftCols :: Int -> Int -> Gals -> Gals
-shiftRows scale n gs = S.union small large'
-  where (small, large) = S.partition (\(V2 r _) -> r < n) gs
-        large' = S.map (^+^ (V2 scale 0)) large
-shiftCols scale n gs = S.union small large'
-  where (small, large) = S.partition (\(V2 _ c) -> c < n) gs
-        large' = S.map (^+^ (V2 0 scale)) large
+expandRows galaxies expansions scale = foldr (shiftRows scale) galaxies expansions
+expandCols galaxies expansions scale = foldr (shiftCols scale) galaxies expansions
+
+shiftRows, shiftCols :: Int -> Int -> Galaxies -> Galaxies
+shiftRows scale n galaxies = S.union small large'
+  where (small, large) = S.partition (\(V2 r _) -> r < n) galaxies
+        large' = S.map (^+^ (V2 (scale - 1) 0)) large
+shiftCols scale n galaxies = S.union small large'
+  where (small, large) = S.partition (\(V2 _ c) -> c < n) galaxies
+        large' = S.map (^+^ (V2 0 (scale - 1))) large
 
 -- reading the map
 
 mkGalaxies :: String -> Galaxies
-mkGalaxies text = 
-  Galaxies (S.fromList [ V2 r c | r <- [0..maxR], c <- [0..maxC]
+mkGalaxies text = S.fromList [ V2 r c | r <- [0..maxR], c <- [0..maxC]
                                       , rows !! r !! c == '#'
-                       ])
-           (V2 0 0, V2 maxR maxC)
+                             ]
   where rows = lines text
         maxR = length rows - 1
         maxC = (length $ head rows) - 1