Day 4 - Overlapping Ranges — Monday Morning Haskell

Problem Overview

For today's problem, our elf friends are dividing into pairs and cleaning sections of the campsite. Each individual elf is then assigned a range of sections of the campsite to clean. Our goal is to figure out redundant work.

In part 1, we want to calculate the number of pairs where one range is fully contained within the other. In part 2, we'll figure out how many pairs of ranges have any overlap.

Relevant Utilities

We'll be parsing a lot of numbers for this puzzle, so we'll need a handy function for that. Here's parsePositiveNumber:

parsePositiveNumber :: (Monad m) => ParsecT Void Text m Int
parsePositiveNumber = read <$> some digitChar

Parsing the Input

Now let's look at the sample input:

2-4,6-8
2-3,4-5
5-7,7-9
2-8,3-7
6-6,4-6
2-6,4-8

Again, we parse this line-by-line. And each line just consists of a few numbers interspersed with other characters.

parseInput :: (MonadLogger m) => ParsecT Void Text m InputType
parseInput =
  sepEndBy1 parseLine eol

type InputType = [LineType]
type LineType = ((Int, Int), (Int, Int))

parseLine :: (MonadLogger m) => ParsecT Void Text m LineType
parseLine = do
  a1 <- parsePositiveNumber
  char '-'
  a2 <- parsePositiveNumber
  char ','
  b1 <- parsePositiveNumber
  char '-'
  b2 <- parsePositiveNumber
  return ((a1, a2), (b1, b2))

Getting the Solution

In part 1, we count the number of lines where one range fully contains another. In the example above, these two lines satisfy this condition:

2-8,3-7
6-6,4-6

So we start with a function to evaluate this:

rangeFullyContained :: ((Int, Int), (Int, Int)) -> Bool
rangeFullyContained ((a1, a2), (b1, b2)) =
  a1 <= b1 && a2 >= b2 ||
  b1 <= a1 && a2 <= b2

And now we use the same folding pattern that's served us for the last couple days! If the condition is satisfied, we add one to the previous score, otherwise no change.

processInputEasy :: (MonadLogger m) => InputType -> m EasySolutionType
processInputEasy = foldM foldLine initialFoldV

type FoldType = Int

initialFoldV :: FoldType
initialFoldV = 0

foldLine :: (MonadLogger m) => FoldType -> LineType -> m FoldType
foldLine prev range = if rangeFullyContained range
  then return $ prev + 1
  else return prev

Part 2

Part 2 is virtually identical, only with a different condition. In the above example, here are the examples with any overlap in the ranges:

5-7,7-9
2-8,3-7
6-6,4-6
2-6,4-8

So here's our new condition:

rangePartiallyContained :: ((Int, Int), (Int, Int)) -> Bool
rangePartiallyContained ((a1, a2), (b1, b2)) = if a1 <= b1
  then b1 <= a2 
  else a1 <= b2

And the application of this condition is virtually identical to part 1.

processInputHard :: (MonadLogger m) => InputType -> m HardSolutionType
processInputHard = foldM foldPart2 0

findHardSolution :: (MonadLogger m) => HardSolutionType -> m (Maybe Int)
findHardSolution _ = return Nothing

foldPart2 :: (MonadLogger m) => Int -> LineType -> m Int
foldPart2 prev range = if rangePartiallyContained range
  then return $ prev + 1
  else return prev

Answering the Question

Nothing has changed from our previous examples in terms of post-processing.

solveEasy :: FilePath -> IO (Maybe Int)
solveEasy fp = runStdoutLoggingT $ do
  input <- parseFile parseInput fp
  Just <$> processInputEasy input

solveHard :: FilePath -> IO (Maybe Int)
solveHard fp = runStdoutLoggingT $ do
  input <- parseFile parseInput fp
  Just <$> processInputHard input

And this means we're done!

Video

YouTube Link

Day 4 - Overlapping Ranges