--- 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 =
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