2 import Text.ParserCombinators.Parsec.Number
3 import Control.Applicative ((<$), (<*), (*>), (<*>), liftA)
4 import Data.List (foldl')
6 data Interval = Interval Int Int deriving (Show, Eq)
11 high :: Interval -> Int
12 high (Interval _ h) = h
16 text <- readFile "advent20.txt"
17 let intervals = successfulParse $ parseIfile text
21 part1 :: [Interval] -> IO ()
22 part1 intervals = print $ (+1) $ high $ head $ foldl' (mergeAdjacent) [] $ foldl' (merge) [] intervals
24 part2 :: [Interval] -> IO ()
26 let ints = foldl' (mergeAdjacent) [] $ foldl' (merge) [] intervals
27 let gapCount = gaps ints
28 let lowGap = low $ head ints
29 let highGap = 4294967295 - (high $ last ints)
30 print (lowGap + gapCount + highGap)
32 disjoint :: Interval -> Interval -> Bool
33 disjoint (Interval a b) (Interval c d)
40 intersect :: Interval -> Interval -> Bool
41 intersect a b = not $ disjoint a b
43 merge :: [Interval] -> Interval -> [Interval]
45 merge (i1:intervals) i0
46 | (high i0) < (low i1) = i0:i1:intervals
47 | intersect i0 i1 = merge intervals (Interval a' b')
48 | otherwise = i1:(merge intervals i0)
49 where a' = minimum [low i0, low i1]
50 b' = maximum [high i0, high i1]
52 mergeAdjacent :: [Interval] -> Interval -> [Interval]
53 mergeAdjacent [] i0 = [i0]
54 mergeAdjacent (i1:intervals) i0
55 | high i0 + 1 == low i1 = (Interval (low i0) (high i1)):intervals
56 | low i0 == high i1 + 1 = (Interval (low i1) (high i0)):intervals
57 | otherwise = i1:(mergeAdjacent intervals i0)
59 gaps :: [Interval] -> Int
62 gaps ((Interval _ b):(Interval c d):intervals) =
63 (c - b - 1) + gaps ((Interval c d):intervals)
65 intervalFile = intervalLine `endBy` newline
66 intervalLine = Interval <$> int <*> (string "-" *> int)
68 parseIfile :: String -> Either ParseError [Interval]
69 parseIfile input = parse intervalFile "(unknown)" input
71 successfulParse :: Either ParseError [a] -> [a]
72 successfulParse (Left _) = []
73 successfulParse (Right a) = a