Advent of Code 2022 day 3

    Day 3 didn't end up in the place I was expecting, which meant I over-engineered part 1 for a part 2 that didn't arrive. It was also the first use of the containers package, for Data.Set.

    For data types, I followed the problem and defined a Rucksack, a type synonym for Contents, and a function that would convert a string to a Rucksack:

    type Contents = S.Set Char
    data Rucksack = Rucksack String String deriving (Show, Eq)
    mkRucksack :: String -> Rucksack
    mkRucksack contents = Rucksack (take n contents) (drop n contents)
      where n = length contents `div` 2

    Part 1

    This needed definitions for commonItem (the common item in both halves of the rucksack) and priority.

    commonItem :: Rucksack -> Char
    commonItem (Rucksack contents1 contents2) = S.findMin (c1 `S.intersection` c2)
      where c1 = S.fromList contents1
            c2 = S.fromList contents2
    priority :: Char -> Int
    priority item 
      | isLower item = ord item - ord 'a' + 1
      | otherwise = ord item - ord 'A' + 27

    The result is by finding the sums of the priorities of the common items.

    part1 :: [Rucksack] -> Int
    part1 = sum . fmap (priority . commonItem)

    Part 2

    I was expecting to find a reallocation of items to the compartments of the rucksacks, even though that would have been a large jump in complexity for this early in the event. (Perhaps we'll revisit this scenario later?)

    But this wasn't too bad. My approach is to split the input into chunks of three rucksacks then, for each chunk,

    1. merge each rucksack into a set of carried items
    2. find the intersection of all the merged rucksacks
    3. extract the badge from the set
    part2 :: [Rucksack] -> Int
    part2 rucksacks = sum $ fmap priority badges
      where groups = chunksOf 3 rucksacks
            badges = fmap badgeOf groups
    merge :: Rucksack -> Contents
    merge (Rucksack contents1 contents2) = 
      S.union (S.fromList contents1) (S.fromList contents2)
    badgeOf :: [Rucksack] -> Char
    badgeOf rucksacks = S.findMin $ intersections (fmap merge rucksacks)
    intersections :: [Contents] -> Contents
    intersections sets = foldl1' S.intersection sets

    (It still annoys me slightly that Data.Set provides unions but not intersections.)


    You can get the code from my locally-hosted Git repo, or from Gitlab.

    Neil Smith

    Read more posts by this author.