From bd05a32800503977f2641d1970538836790ce748 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Mon, 11 Dec 2023 11:12:40 +0000 Subject: [PATCH] Simplified data structure. --- advent11/Main.hs | 64 +++++++++++++++++++----------------------------- 1 file changed, 25 insertions(+), 39 deletions(-) diff --git a/advent11/Main.hs b/advent11/Main.hs index 03d3e69..283060d 100644 --- a/advent11/Main.hs +++ b/advent11/Main.hs @@ -9,9 +9,7 @@ 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 = @@ -24,13 +22,11 @@ main = print $ part2 galaxies part1, part2 :: Galaxies -> Int -part1 galaxies = allDistances gs - where (Galaxies gs _) = expandGalaxies galaxies 2 +part1 galaxies = allDistances $ expandGalaxies galaxies 2 -part2 galaxies = allDistances gs - where (Galaxies gs _) = expandGalaxies galaxies (10^6) +part2 galaxies = allDistances $ expandGalaxies galaxies (10^6) -allDistances :: Gals -> Int +allDistances :: Galaxies -> Int allDistances gs = case S.minView gs of Nothing -> 0 Just (g, gs') -> (S.foldl' (addDist g) 0 gs) + allDistances gs' @@ -44,48 +40,38 @@ distance g1 g2 = abs dr + abs dc expandGalaxies :: Galaxies -> Int -> Galaxies expandGalaxies galaxies scale = 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 -- 2.34.1