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