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