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


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

    Neil Smith

    Read more posts by this author.