/Wakamoleguy - home of the wakamoleguy

Advent of Code 2022 - Day 4: Camp Cleanup

December 4, 2022

In Day 4: Camp Cleanup, each elf has been assigned a range of segments to clean. We're given a list of these pairs, and we're tasked with comparing whether the ranges overlap completely (Part 1) or at all (Part 2).

The numbers in our input are all relatively small, to the point where we could brute-force check the elements of each range. But, let's try to avoid that by only examing the endpoints of the range.

This type of representation is bound to be more efficient. It also lends itself well to sweep line algorithms, which I bet we will see later this season.

The Range type

Our Range type is a data type that stores only its endpoints:

data Range = Range Int Int

In solving this challenge, I wanted to make the interface for this Range as reusable as possible. Most of the helper functions are analogs to similar functions on Data.Set or Data.List. For Part 1, we need to detect if one Range is a subset of another.

-- So reusable!
elem :: Int -> Range -> Bool
i `elem` Range a b = a <= i && i <= b

-- Much consistency!
isSubsetOf :: Range -> Range -> Bool
Range a b `isSubsetOf` target = a `elem` target && b `elem` target

-- Specific to Part 1:
isOverlap :: Range -> Range -> Bool
isOverlap a b = a `isSubsetOf` b || b `isSubsetOf` a

part1 :: [(Range, Range)] -> Int
part1 = length . filter (uncurry isOverlap)

For Part 2, we are looking for any overlap. We can also define some more commonly found functions:

-- Just like Sets!
intersection :: Range -> Range -> Range
intersection (Range a b) (Range x y) = Range (max a x) (min b y)

-- Just like Foldables, and Sets, and Maps...
null :: Range -> Bool
null (Range a b) = b < a

part2 :: [(Range, Range)] -> Int
part2 = length . filter (not . null . uncurry intersection)

Parsing

The final piece is to parse the input into a list of (Range, Range) pairs. To do this, I used Parsec.

parseRangePair :: GenParser Char u (Range, Range)
parseRangePair = do
  r1 <- parseRange
  _ <- char ','
  r2 <- parseRange
  return (r1, r2)
  where
    parseRange = do
      a <- read <$> many1 digit
      _ <- char '-'
      b <- read <$> many1 digit
      return $ Range a b

input :: IO (Either ParseError [(Range, Range)])
input = traverse (parse parseRangePair "") . lines <$> readDay 2022 4

This is pretty verbose, and I'm sure it can be optimized.

Full Code

Here it is all together:

module AOC2022.Day04 (spec) where

import Input
import Test.Hspec
import Text.ParserCombinators.Parsec
import Prelude hiding (elem, null)

input :: IO (Either ParseError [(Range, Range)])
input = traverse (parse parseRangePair "") . lines <$> readDay 2022 4

spec :: IO ()
spec = hspec $ do
  describe "Part 1" $ do
    it "runs on custom input" $ do
      myInput <- input
      part1 <$> myInput `shouldBe` Right 0 -- redacted

  describe "Part 2" $ do
    it "runs on custom input" $ do
      myInput <- input
      part2 <$> myInput `shouldBe` Right 0 -- redacted

data Range = Range Int Int

parseRangePair :: GenParser Char u (Range, Range)
parseRangePair = do
  r1 <- parseRange
  _ <- char ','
  r2 <- parseRange
  return (r1, r2)
  where
    parseRange = do
      a <- read <$> many1 digit
      _ <- char '-'
      b <- read <$> many1 digit
      return $ Range a b

elem :: Int -> Range -> Bool
i `elem` Range a b = a <= i && i <= b

isSubsetOf :: Range -> Range -> Bool
Range a b `isSubsetOf` target = a `elem` target && b `elem` target

isOverlap :: Range -> Range -> Bool
isOverlap a b = a `isSubsetOf` b || b `isSubsetOf` a

part1 :: [(Range, Range)] -> Int
part1 = length . filter (uncurry isOverlap)

intersection :: Range -> Range -> Range
intersection (Range a b) (Range x y) = Range (max a x) (min b y)

null :: Range -> Bool
null (Range a b) = b < a

part2 :: [(Range, Range)] -> Int
part2 = length . filter (not . null . uncurry intersection)

Advent of Code 2022 Series

This post is part of a series describing my Haskell solutions to Advent of Code 2022.