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 IntParsing 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=" *> decimalPart 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) qRecThe 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.