= Solution
First remove a single matching token, so duplicates cannot be reused:
``
pluck :: Eq a => a -> [a] -> Maybe [a]
pluck _ [] = Nothing
pluck x (y:ys)
| x == y = Just ys
| otherwise = case pluck x ys of
Nothing -> Nothing
Just zs -> Just (y:zs)
overlap :: Eq a => [a] -> [a] -> [a]
overlap [] _ = []
overlap (x:xs) ys = case pluck x ys of
Nothing -> overlap xs ys
Just zs -> x : overlap xs zs
scoreBC :: Eq a => [a] -> [a] -> (Int,Int)
scoreBC secret guess = (bulls, matches - bulls)
where
bulls = length [() | (s,g) <- zip secret guess, s == g]
matches = length (overlap guess secret)
``
Equal game lengths are assumed. For each token, `overlap` retains exactly the smaller of its two multiplicities, so its length is the <multiset overlap>. It never spends a secret occurrence twice. Positional matches account for `bulls`; after reserving them, each token's remaining possible matches decrease by exactly its bull count. Hence `matches - bulls` counts precisely the cows. The source example gives \b[`(1,1)`]. With equality as the only operation on tokens, these definitions take $O(L^2)$ time for length $L$.
Back to article page
