Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 3 / e / Solution

Let $N$ be the number of distinct dictionary candidates. A wrong guess is itself a current candidate, but its actual score differs from its score against itself, which has all positions as bulls. Therefore each wrong reply removes at least that candidate while retaining the true secret. There can be at most $N-1$ wrong guesses. A correct guess leaves only the secret consistent with the all-bull reply. Hence every such infinite game's history eventually has the constant tailThis is the finite candidate elimination bound; it assumes a nonempty finite dictionary of fixed-length secrets and a strategy that chooses from the remaining candidates.

The stated end condition is identification, so stop when just one candidate remains, even if it has not been guessed. Replace the worker above byThe scorer can stay map (score secret): once the guess list ends, its score list ends too. The unchanged game then returns a finite history, with at most $N-1$ rounds; a singleton initial dictionary needs no round. If the identified secret is also wanted as an explicit output, return that sole surviving candidate alongside the history.