{-# Language QuasiQuotes #-}
{-|
Module      : Main
Description : Day 20 solution
Copyright   : (c) Eric Mertens, 2021
License     : ISC
Maintainer  : emertens@gmail.com

<https://adventofcode.com/2016/day/20>

-}
module Main where

import Advent.Format (format)
import Data.List (sort)

type Blacklist = [(Integer,Integer)]

-- | >>> :main
-- 23923783
-- 125
main :: IO ()
IO ()
main =
  do Blacklist
blacklist <- Blacklist -> Blacklist
removeOverlap (Blacklist -> Blacklist) -> IO Blacklist -> IO Blacklist
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [format|2016 20 (%lu-%lu%n)*|]
     Integer -> IO ()
forall a. Show a => a -> IO ()
print (Blacklist -> Integer
lowest     Blacklist
blacklist)
     Integer -> IO ()
forall a. Show a => a -> IO ()
print (Blacklist -> Integer
countValid Blacklist
blacklist)

-- | Remove all redundancy from the blacklist and put it in sorted order.
removeOverlap :: Blacklist -> Blacklist
removeOverlap :: Blacklist -> Blacklist
removeOverlap = Blacklist -> Blacklist
forall {b}. (Ord b, Num b) => [(b, b)] -> [(b, b)]
go (Blacklist -> Blacklist)
-> (Blacklist -> Blacklist) -> Blacklist -> Blacklist
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Blacklist -> Blacklist
forall a. Ord a => [a] -> [a]
sort
  where
    go :: [(b, b)] -> [(b, b)]
go ((b
lo1,b
hi1):(b
lo2,b
hi2):[(b, b)]
rest)
      | b
hi1 b -> b -> Bool
forall a. Ord a => a -> a -> Bool
>= b
lo2b -> b -> b
forall a. Num a => a -> a -> a
-b
1 = [(b, b)] -> [(b, b)]
go ((b
lo1, b -> b -> b
forall a. Ord a => a -> a -> a
max b
hi1 b
hi2) (b, b) -> [(b, b)] -> [(b, b)]
forall a. a -> [a] -> [a]
: [(b, b)]
rest)
    go ((b, b)
x:[(b, b)]
xs) = (b, b)
x (b, b) -> [(b, b)] -> [(b, b)]
forall a. a -> [a] -> [a]
: [(b, b)] -> [(b, b)]
go [(b, b)]
xs
    go [] = []

-- | Smallest address that isn't blacklisted
lowest :: Blacklist -> Integer
lowest :: Blacklist -> Integer
lowest ((Integer
0,Integer
hi):Blacklist
_) = Integer
hiInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
+Integer
1
lowest ((Integer
lo,Integer
_):Blacklist
_) = Integer
loInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
1
lowest Blacklist
_ = Integer
0

-- | Number of addresses not blacklisted
countValid :: Blacklist -> Integer
countValid :: Blacklist -> Integer
countValid Blacklist
xs = Integer
2Integer -> Int -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^(Int
32::Int) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- [Integer] -> Integer
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [Integer
1Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+Integer
bInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
a | (Integer
a,Integer
b) <- Blacklist
xs]