Advent of Code 2022 - Day 6: Tuning Trouble

For a refreshing change, Day 6: Tuning Trouble does not require us to parse our input at all. We're given a single line of characters, and we need to process it looking for sets of unique characters.

This problem seems like a natural fit for recursion. Our core functionality will be a function that peeks the first few characters of the string. If they are unique, it returns the count. Otherwise, we discard a letter and try again with the rest of the string. Here's my first iteration at this, for Part 1:

charsUntilPacket :: String -> Int
charsUntilPacket (a : b : c : d : rest)
  | Set.size (Set.fromList [a, b, c, d]) == 4 = 4
  | otherwise = 1 + charsUntilPacket (b : c : d : rest)

Part 2 - Windows of size 14

Looking at 14 characters in a row is much the same. Pattern matching on 14 characters seemed a little excessive, though. I restructured charsUntilPacket to take a window size parameter, and renamed it charsUntilNUnique.

Lastly, I changed how we are checking for uniqueness. The Set approach works fine, but it forces the entire Set to be constructed to check its size. The alternative approach of nub s == s is, perhaps surprisingly, more efficient: it compares the elements one by one and can skip the remaining computation of nub s as soon as it discovers a mismatch. Laziness for the win!

Hoogle does find a function isNub that is equivalent. However, it's not in a package I'm familiar with.

Full Code

module AOC2022.Day06 (spec) where

import Data.List (nub)
import Input (readDay)
import Test.Hspec (describe, hspec, it, shouldBe)

input :: IO String
input = readDay 2022 6

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

charsUntilNUnique :: Int -> String -> Int
charsUntilNUnique i s =
  if nub (take i s) == take i s
    then i
    else 1 + charsUntilNUnique i (tail s)

part1 :: String -> Int
part1 = charsUntilNUnique 4

part2 :: String -> Int
part2 = charsUntilNUnique 14

Advent of Code 2022 Series

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

Next: Day 7: No Space Left On Device Previous: Day 5: Supply Stacks