Quest 4 was fiddly rather than difficult, revolving around different specifications for how to sort various subsets of data. That needed a fair bit of data wrangling to get things into the correct form.

Representation and parsing

The source data gives, for each person/quest/part combination, the time that person took to complete that part of that quest. That suggests a Map as the best data structure. This gets converted to a total time for a person, or a total score for a person.

data QuestKey = QuestKey { personId :: Int, questId :: Int, questPart :: Int }
  deriving (Show, Eq, Ord)
  
type QuestRecord = M.Map QuestKey Int

type PersonTimes = M.Map Int Int

Parsing the data converts each line into a singleton Map then returns the full set via a union of them

questsP = M.unions <$> questP `sepBy` endOfLine
questP = M.singleton <$> questKeyP <* " " <*> timeP
questKeyP = QuestKey <$> personIdP <* " " <*> questIdP <* " " <*> questPartP
personIdP = "id=" *> decimal
questIdP = "quest=" *> decimal
questPartP = "part=" *> decimal
timeP = "time=" *> decimal

Part 1

This is finding the total time for each participant. That's a fold over the initial QuestRecord, building up a PersonTimes map. The records are then sorted by the total time and the checksum calculated.

part1 :: QuestRecord -> Int
part1 questRecord = sum $ zipWith (*) [1..] $ fmap snd rankedTimes
  where totalTimes = M.foldlWithKey' includeOneTime M.empty questRecord
        rankedTimes = sortBy (compare `on` snd) $ M.toList totalTimes

includeOneTime :: PersonTimes -> QuestKey -> Int -> PersonTimes
includeOneTime times qk t = M.insert qk.personId (t + currentT) times 
  where currentT = M.findWithDefault 0 qk.personId times 

Part 2

This is similar, but the sorting is different. Rather than sorting by time (shortest time first), the sorting is now by number of parts completed (most parts first), then shortest time within those groups.

I handled this by combining the quest records into a Map from person ID to the pair of (number of parts, total time), then defining a custom sort on that result.

type PersonTimesParts = M.Map Int (Int, Int) -- number of parts, time

part2 questRecord = 
  sum [ r * t | (r, (_p, t)) <- zip [1..] $ fmap snd rankedTimesParts ]
  where totalTimesParts = M.foldlWithKey' includeOneTimePart M.empty questRecord
        rankedTimesParts = sortBy compareTimesParts $ M.toList totalTimesParts
        compareTimesParts (_, (p1, t1)) (_, (p2, t2)) = 
          case (p1 `compare` p2) of
            GT -> LT
            LT -> GT
            EQ -> t1 `compare` t2

includeOneTimePart :: PersonTimesParts -> QuestKey -> Int -> PersonTimesParts
includeOneTimePart timesParts qk t = 
  M.insert qk.personId (n + 1, t + currentT) timesParts
  where (n, currentT) = M.findWithDefault (0, 0) qk.personId timesParts 

Having the custom ordering function local to the rest of the code was the path of least resistance here.

Part 3

This part has more complex sorting, and a different way of handling tied scores.

For part 1 of a quest, the score is based on the time for that part. The shortest time gets 50 points, the next-shortest 49 points, and so on. If several people have the same time, they all get the same score and the score for the next person changes by the number of people in this place.

For parts 2 and 3 of a quest, the score is based on the sum of the times for this part and all previous parts. The scores for the parts are higher.

The total score for a quest is the sum of the scores for all parts. A person's overall score is the sum of scores for all quests.

The checksum (final answer) is calculated the same as before, but again has to respect ties.

Let's put together a solution from the bottom up.

The times for one part of one quest are found from the questRecord, filtering it by the quest and part, and converting the map from a QuestRecord to a PersonTime. The times for parts 2 and 3 of a quest are found by finding the times for each part individually and adding them up.

timesForPreviousParts, timesForOnePart :: QuestRecord -> Int -> Int -> PersonTimes
timesForPreviousParts questRecord questNo partNo = foldl' go base [n | n <- [2..partNo]]
  where go times p = M.intersectionWith (+) times $ timesForOnePart questRecord questNo p
        base = timesForOnePart questRecord questNo 1

timesForOnePart questRecord questNo partNo = M.mapKeys (\k -> k.personId) pRec
  where qRec = M.filterKeys (\k -> k.questId == questNo) questRecord
        pRec = M.filterKeys (\k -> k.questPart == partNo) qRec

The scores for a part required me to go through the PersonTime in time order. That's easier by converting the Map Person Time data into a Map Time (Set Person) , holding all the people that got the same time. I convert that latter map into an ordered list of times with M.toAscList.

includePersonScores converts the ordered list of (time, people) into a Map Person Score, handling the correct updating of the current score based on the number of people with that time.

scoreForPart :: QuestRecord -> Int -> Int -> PersonScores
scoreForPart questRecord questNo partNo = 
  fst $ foldl' includePersonScore (M.empty, (50 * partNo)) $ M.toAscList timedPeople
  where pRec = timesForPreviousParts questRecord questNo partNo
        timedPeople = M.unionsWith S.union [M.singleton t (S.singleton p) | (p, t) <- M.toList pRec ]

includePersonScore :: (PersonScores, Int) -> (Int, S.Set Int) -> (PersonScores, Int)
includePersonScore (scored, currentScore) (time, people) = (scored', nextScore)
  where theseScores = M.fromList [(p, currentScore) | p <- S.toList people ]
        scored' = M.union scored theseScores
        nextScore = max 0 (currentScore - (length people))

Given that, the score for a quest is the sum of the scores for each part.

scoreForQuest :: QuestRecord -> Int -> PersonScores
scoreForQuest questRecord questNo = 
  M.unionsWith (+) [scoreForPart questRecord questNo n | n <- [1..3]]

Then I find the checksum by extracting all the scores, sorting and grouping them, then walking over the list (with foldl') to calculate the checksum.

part3 questRecord = snd checksum
  where questScores = fmap (scoreForQuest questRecord) $ allQuests questRecord
        totalScores = group $ reverse $ sort $ M.elems $ M.unionsWith (+) questScores
        checksum = foldl' go (1, 0) totalScores
        go (n, cs) scores = ( n + (length scores)
                            , cs + n * (head scores) * (length scores)
                            )

Code

You can get the code from Codeberg. or on my self-hosted Git site.