Day 3 - Rucksacks and Badges

Dec 3

All 2022 Problems

Problem Overview

Today's problem is essentially a deduplication problem. Each input line is a series of letters. For part 1, we're deduplicating within lines, finding one character that is in both sides of the word. For part 2, we're dividing the inputs into groups of 3, and then finding the only letter common to all three strings.

To "answer the question", we have to provide a "score" for each of the unique characters. The lowercase letters get the scores 1-26. Uppercase letters get the scores 27-52. Then we'll take the sum of the scores from each line or group.

Solution Approach and Insights

This is quite straightforward if you know your list library functions! We'll use filter, elem, chunksOf and nub!

Parsing the Input

Here's a sample input

vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw
```:

Nothing tricky about the parsing code, since it's all just strings with only letters!

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

type InputType = [LineType]
type LineType = String

parseLine :: (MonadLogger m) => ParsecT Void Text m LineType
parseLine = some letterChar

Getting the Solution

We'll start with our scoring function. Of course, we'll use the ord function to turn each character into its ASCII number. By then we have to subtract the right amount so that lowercase 'a' (ASCII 97) gets a score of 1 and uppercase 'A' (ASCII 65) gets the score of 27:

scoreChar :: Char -> Int
scoreChar c = if isUpper c
  then ord c - 38
  else ord c - 96

The rest of the solution involves the same folding pattern from Day 2. As a reminder, here's the setup code (I'll omit this in future examples):

solveFold :: (MonadLogger m) => [LineType] -> m EasySolutionType
solveFold = foldM foldLine initialFoldV

type FoldType = Int

initialFoldV :: FoldType
initialFoldV = 0

foldLine :: (MonadLogger m) => FoldType -> LineType -> m FoldType
foldLine = ...

So the only challenge is filling out the folding function. First, we divide our word into the first half and the second half.

foldLine :: (MonadLogger m) => FoldType -> LineType -> m FoldType
foldLine prevScore inputLine = ...
  where
    compartmentSize = length inputLine `quot` 2
    (firstHalf, secondHalf) = splitAt compartmentSize inputLine

Then we find the only character in both halves by filtering the first half based on being an elem of the second half. We also use nub to get rid of duplicates. We break this up with a case statement. If there's only one (as we expect), then we'll take its score and add it to the previous score. Otherwise we'll log an error message and return the previous score.

foldLine :: (MonadLogger m) => FoldType -> LineType -> m FoldType
foldLine prevScore inputLine = do
  case charsInBoth of
    [c] -> return (prevScore + scoreChar c)
    cs -> logErrorN ("Invalid chars in both sides! " <> (pack . show $ cs)) >> return prevScore
  where
    compartmentSize = length inputLine `quot` 2
    (firstHalf, secondHalf) = splitAt compartmentSize inputLine
    charsInBoth = nub $ filter (`elem` secondHalf) firstHalf

And that's all for part 1!

Part 2

For part 2, we want to divide the input lines into groups of 3, and then find the common letter among them. Once again, we use a fold that starts with chunksOf to divide our input into groups of 3.

processInputHard :: (MonadLogger m) => InputType -> m HardSolutionType
processInputHard allLines = foldM foldHard 0 (chunksOf 3 allLines)

foldHard :: (MonadLogger m) => Int -> [String] -> m Int
foldHard = ...

With this function, we first make sure we have exactly 3 strings.

foldHard :: (MonadLogger m) => Int -> [String] -> m Int
foldHard prevScore [s1, s2, s3] = ...
foldHard prevScore inputs = logErrorN ("Invalid inputs (should be size 3) " <> (pack . show $ inputs)) >> return prevScore

Now for the primary case, we do the same thing as before, only we filter s1 based on s2. Then we filter that result with s3 and do the same nub trick.

foldHard :: (MonadLogger m) => Int -> [String] -> m Int
foldHard prevScore [s1, s2, s3] = ...
  where
    s1AndS2 = filter (`elem` s2) s1
    all3 = nub $ filter (`elem` s3) s1AndS2

And we conclude with the same process as before. Log an error if we don't get the right outputs, otherwise add the score for the character.

foldHard :: (MonadLogger m) => Int -> [String] -> m Int
foldHard prevScore [s1, s2, s3] = do
  case all3 of
    [c] -> logErrorN ("Found " <> (pack [c]) <> " with score " <> (pack . show $ scoreChar c)) >> return (prevScore + scoreChar c)
    cs -> logErrorN ("Invalid chars in all 3 ! " <> (pack . show $ cs)) >> return prevScore
  where
    s1AndS2 = filter (`elem` s2) s1
    all3 = nub $ filter (`elem` s3) s1AndS2

Answering the Question

As with the past couple days, we don't have any more work to do after processing the input:

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 gives us our answer!

Video

YouTube Link

Advent of Code

James Bowen