0
$\begingroup$

A few days ago I came across such a problem at the contest my uni was holding:

Given the history of guesses in a mastermind game using digits instead of colors in a form of pairs $(x, y)$ where $x$ is the guess and $y$ is how many digits were placed correctly, guess the correct number. Each input is guaranteed to have a solution.

Example for a $5$-place game:

$$(90342, 2) \\ (70794, 0) \\ (39458, 2) \\ (34109, 1) \\ (51545, 2) \\ (12531, 1)$$

Should yield: $$ 39542 $$ Create an algorithm to correctly guess the result in an n-place mastermind given the history.

So the only idea I had was to keep the probability of each digit being correct based on the correct shots in a given guess and then try to generate the most possible number, then the next one and so on - so for example we'd have $9$ being $40\%$ possible for the first place (cause the first guess has $\frac{2}{5}=40\%$ correct), $7$ being impossible and so on. Then we do the same for other places in the number and finally generate a number with the highest probability to test it against all the guesses.

The problem with this approach, though, is that generating the next possible number, and the next, and so on (as we probably won't score a home run in the first try) is really non-trivial (or at least I don't see an easy way of implementing this) and since this contest had something like a 90 minute timeframe and this wasn't the only problem, I don't think something so elaborate was the anticipated approach.

So how could one do it easier?

$\endgroup$
1
$\begingroup$

The title and body pose two different questions. I'll answer the question in the body, how one could do it easier, without providing an algorithm as requested in the title.

$90342$, $39458$ and $51545$ all have two hits; that's a total of six hits in five digits, so at least one hit must be shared. The only coinciding digit is the $4$ in the penultimate place, so that must be correct, and the remaining four hits must be distributed over the remaining four digits.

That means that the single hits in $34109$ and $12531$ must also be shared with one of the above numbers, and the only coincidences are the $3$ in the first digit (shared with $39458$) and the $5$ in the middle digit (shared with $51545$).

That leaves one hit in $39458$ and one in $90342$, which must be in the second and last digits. $70794$ is all wrong, so the second digit can't be $0$, so $90342$ must provide the last digit and $39458$ must provide the second.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.