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