Removed needless directory
[advent-of-code-16.git] / app / advent20.hs
1 module Main(main) where
2
3 import Text.Parsec
4 import Text.ParserCombinators.Parsec.Number
5 import Data.List (foldl')
6
7 data Interval = Interval Int Int deriving (Show, Eq)
8
9 low :: Interval -> Int
10 low (Interval l _) = l
11
12 high :: Interval -> Int
13 high (Interval _ h) = h
14
15 main :: IO ()
16 main = do
17 text <- readFile "data/advent20.txt"
18 let intervals = successfulParse $ parseIfile text
19 part1 intervals
20 part2 intervals
21
22 part1 :: [Interval] -> IO ()
23 part1 intervals = print $ (+1) $ high $ head $ foldl' (mergeAdjacent) [] $ foldl' (merge) [] intervals
24
25 part2 :: [Interval] -> IO ()
26 part2 intervals = do
27 let ints = foldl' (mergeAdjacent) [] $ foldl' (merge) [] intervals
28 let gapCount = gaps ints
29 let lowGap = low $ head ints
30 let highGap = 4294967295 - (high $ last ints)
31 print (lowGap + gapCount + highGap)
32
33 disjoint :: Interval -> Interval -> Bool
34 disjoint (Interval a b) (Interval c d)
35 | b < c = True
36 | d < a = True
37 | a > d = True
38 | c > b = True
39 | otherwise = False
40
41 intersect :: Interval -> Interval -> Bool
42 intersect a b = not $ disjoint a b
43
44 merge :: [Interval] -> Interval -> [Interval]
45 merge [] i0 = [i0]
46 merge (i1:intervals) i0
47 | (high i0) < (low i1) = i0:i1:intervals
48 | intersect i0 i1 = merge intervals (Interval a' b')
49 | otherwise = i1:(merge intervals i0)
50 where a' = minimum [low i0, low i1]
51 b' = maximum [high i0, high i1]
52
53 mergeAdjacent :: [Interval] -> Interval -> [Interval]
54 mergeAdjacent [] i0 = [i0]
55 mergeAdjacent (i1:intervals) i0
56 | high i0 + 1 == low i1 = (Interval (low i0) (high i1)):intervals
57 | low i0 == high i1 + 1 = (Interval (low i1) (high i0)):intervals
58 | otherwise = i1:(mergeAdjacent intervals i0)
59
60 gaps :: [Interval] -> Int
61 gaps [] = 0
62 gaps [_] = 0
63 gaps ((Interval _ b):(Interval c d):intervals) =
64 (c - b - 1) + gaps ((Interval c d):intervals)
65
66 intervalFile = intervalLine `endBy` newline
67 intervalLine = Interval <$> int <*> (string "-" *> int)
68
69 parseIfile :: String -> Either ParseError [Interval]
70 parseIfile input = parse intervalFile "(unknown)" input
71
72 successfulParse :: Either ParseError [a] -> [a]
73 successfulParse (Left _) = []
74 successfulParse (Right a) = a