Advent of Code 2022 day 13

Day 13 was the first real foray into Haskell's typeclass system, with the implementation of an Ord instance for a custom data type. Some functions in Data.List made the rest of the processing easy.

Data type

The problem wanted me to define an ordering for packets, so I had to be able to represent packets. This required a new data type, and a parser for it.

data Packet = List [Packet] | Element Int
  deriving (Eq)

pairsP = pairP `sepBy` (endOfLine <* endOfLine)
pairP = (,) <$> (packetP <* endOfLine) <*> packetP

packetP = listP <|> elementP
elementP = Element <$> decimal
listP = List <$> ("[" *> (packetP `sepBy` ",")) <* "]"

Next was to define how packets should be ordered. This was the definition of the Ord typeclass for this type. I chose to define compare, following the rules given in the problem description. The definition of this function allows Haskell to provide all the other comparison operators for this data type.

instance Ord Packet where
  (Element a)   `compare` (Element b)  = a `compare` b
  (Element a)   `compare` (List bs)    = (List [Element a]) `compare` (List bs)
  (List as)     `compare` (Element b)  = (List as) `compare` (List [Element b])
  (List [])     `compare` (List [])    = EQ
  (List [])     `compare` (List (_:_)) = LT
  (List (_:_))  `compare` (List [])    = GT
  (List (a:as)) `compare` (List (b:bs)) 
    | a `compare` b == EQ = (List as) `compare` (List bs)
    | otherwise = a `compare` b

Solving the problems

For part 1, I used uncurry (<) to convert each pair into the Boolean showing if it was correctly ordered, then find the indices of the True values (adding 1 to each to make it one-based numbering.

part1  = sum . fmap (1 +) . elemIndices True . fmap (uncurry (<))

Because Packet is an instance of Ord, the standard sort function works on lists of Packets. That meant part 2 was just finding which elements of the sorted packet list were dividers, then multiplying them.

part2 pairs = product dividerLocations
  where dividers = [ List [List [Element 2]] , List [List [Element 6]] ]
        packets = dividers ++ concatMap (\(a, b) -> [a, b]) pairs
        dividerLocations = fmap (1 +) $ findIndices (`elem` dividers) $ sort packets

Code

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