Much like yesterday, day 5's puzzle was solved mostly by writing down the problem definition and letting Haskell sort out the details. We're given a set of ranges (intervals of natural numbers) and ingredient IDs (natural numbers), and have to match various ingredient IDs and ranges.

Representation

The data in this puzzle was just about complex enough that I thought it would be easier to have some data types to represent it, and a parser to read it. As usual, I'm using attoparsec for parsing and the "applicative style" of defining parsers.

data Range = Range Int Int deriving Show
type Ingredient = Int

rangeIngredientP = (,) <$> rangesP <* endOfLine <* endOfLine <*> ingredientsP

rangesP = rangeP `sepBy` endOfLine
rangeP = Range <$> decimal <* "-" <*> decimal

ingredientsP = decimal `sepBy` endOfLine

A Range holds the upper and lower bounds of a range.

Part 1

I solved this by writing down the problem specification.

According the problem, an ingredient isFresh if it is within any range. An ingredient is within a range if it is between the range's upper and lower bounds (inclusive).

isFresh :: [Range] -> Ingredient -> Bool
isFresh ranges ingredient  = any (within ingredient) ranges

within :: Ingredient -> Range -> Bool
within ingredient (Range l u) = ingredient >= l && ingredient <= u

Then I just find the fresh ingredients and count them.

part1 :: [Range] -> [Ingredient] -> Int
part1 ranges ingredients = length $  filter (isFresh ranges) ingredients

Part 2

To answer this, I have to find how many ingredients are within any of the given ranges. I find the size of all the ranges and add them.

part2 :: [Range] -> Int
part2 ranges = sum $ fmap sizeOf ranges

sizeOf :: Range -> Int
sizeOf (Range l u) = u - l  + 1

However, that's wrong, because I'll double-count where there are overlapping ranges. For instance, in the example, the ranges "10-14" and "16-20" overlap, so I would double-count 14, 15, and 16.

Therefore, I need to merge the overlapping ranges before working out the total size. Again, writing down some definitions helps greatly. (This follows closely from my solution to Advent of Code 2022 day 4.)

One range is before another if its upper bound is less than the other's lower bound. Two ranges are disjoint if one is before the other. Two ranges overlap if they are not disjoint.

before, disjoint, overlaps :: Range -> Range -> Bool
before (Range _lower1 upper1) (Range lower2 _upper2) = (upper1 < lower2) 
disjoint range1 range2 = 
  (range1 `before` range2) || (range2 `before` range1)
overlaps range1 range2 = not $ disjoint range1 range2

Merging two ranges takes the infinum and suprenum of the two ranges (assuming they overlap).

merge :: Range -> Range -> Range
merge (Range l1 u1) (Range l2 u2) = Range (min l1 l2) (max u1 u2)

Now to combine a set of ranges. Given a set of mutually-disjoint ranges, I can incorporate one new range into it by splitting the set of ranges into those that overlap with this one and those that don't, merging this range into the overlapping ones, and adding the merged range to the set of non-overlapping ones. I incorporate all the ranges together by adding them one at a time.

That turns into a pair of nested fold operations.

incorporateAll :: [Range] -> [Range]
incorporateAll ranges = foldr incorporateOne [] ranges

incorporateOne :: Range -> [Range] -> [Range]
incorporateOne range ranges = merged : others
  where (overlapping, others) = partition (overlaps range) ranges
        merged = foldr merge range overlapping

That allows me to correct the solution.

part2 :: [Range] -> Int
part2 ranges = sum $ fmap sizeOf $ incorporateAll ranges

Aside

I could have sorted the intervals before merging, which would have simplified things a bit, but it was easy enough to have the more general solution here.

As with the 2022 puzzle, I could have used the Numeric.Interval library for some of this, but it was frankly overkill for what I was doing. It was easier to implement what I needed directly.

Code

You can get the code from Codeberg.