As always, we start by parsing the input into something more manageable.
The input consists of two sections separated by a blank line.
The first section contains fresh ingredient ID ranges (e.g.,
3-5), and the second contains available ingredient
IDs. We split on \n\n to separate these sections,
then parse each range into a list of two integers and each point
as a single integer:
import Data.List.Split (splitOn)
parse i = (ranges, points)
where
[h1, h2] = splitOn "\n\n" i
ranges = map (map read . splitOn "-") $ lines h1
points = map read $ lines h2Our representation of intervals is list with two elements
[start, end]. contains is a helper
function to check if an ingredient ID falls within a given
range:
contains :: Int -> [Int] -> Bool
contains e [start, end] = e >= start && e <= endFor part one, we need to count how many of the available
ingredient IDs are fresh. An ID is fresh if it falls within
any of the fresh ranges:
p1 :: [[Int]] -> [Int] -> Int
p1 is = length . filter (\p -> any (contains p) is)For part two, we need to count the total number of unique
ingredient IDs covered by all the fresh ranges. The methodology
here is to iterate over the intervals sorted by ascending start
bounds, while keeping track of the last end-bound we jumped over.
This is necessary to avoid double-counting overlapping ranges. If
we have 10-14 followed by 12-18, we
should avoid counting 12, 13, 14 twice. So we first
account for 10-14, and keep note of 14.
Upon encountering 12-18, we then only count
18 - 14 = 4 new points, and not
18 - 12 + 1 = 7 new points, since the three points
12, 13, 14 are accounted for.
import Data.List (sortBy)
import Data.Ord (comparing)p2 :: [[Int]] -> Int
p2 = go 0 0 . sortBy (comparing (!! 0))
where
go tot _ [] = tot
go tot le (i@[start, end] : rest)
| le > end = go tot le rest
| contains le i = go (tot + end - le) end rest
| le < start = go (tot + end - start + 1) end restFinally, a main function to wrap it all up:
main = do
(is, pts) <- parse <$> getContents
print $ p1 is pts
print $ p2 is