Guess my number

Question

There is a popular game called Mastermind in which one player guesses another player's secret sequence - it could be a word, some colors, or numbers. The guesser says a possible sequence, and they get back the number of correct numbers in the right spot and the number of correct numbers in the wrong spot. Here we will be playing Mastermind with 4-digit numbers.

Here is an example game with the answer "4560".

You start with 1234 and get the response "-1"; that means one digit is correct but in the wrong location. You guess 3465 and get "-2 +1"; that means two digits are in the wrong location and one digit is in the correct location. The other digit isn't part of the number at all.

The game continues:

1234: -1
3465: -2 +1
4503: -1 +2
4560 +4 (4 tries and win!)

You are very smart, so as soon as you get enough information you'll be able to guess the number instantly, but the problem is that you are the unluckiest person alive, especially at guessing numbers. So, in the worst case scenario, how many guesses do you need to find your opponent's number?

Keep in mind that 4-digit numbers can't start with 0!

that's a joke because you've just described the popular board game "mastermind" — Slepz, Jan 18 '16 at 20:24
i didnt know the name of the game, to be honest i had no idea there was such game that everbody knows :p we were playing it with numbers though, not colors. — Oray, Jan 18 '16 at 20:29
https://upload.wikimedia.org/wikipedia/commons/2/2d/Mastermind.jpg
it's different in that you use colours instead of numbers and allows repeated colours in the solution, but I assume it has the same strategy (generally guess 1122, then 3344 etc until you know which numbers are in the solution, then try different permutations. I read somewhere that worst case scenario is 6 tries with the right algorithm but that doesn't apply here — Slepz, Jan 18 '16 at 20:37
This is sort of similar to mastermind but slightly different I their are more numbers than the colours in mastermind — Beastly Gerbil, Jan 18 '16 at 21:26
plus you have the wrinkle of 0 being unique in that it can't be the first number — Slepz, Jan 18 '16 at 22:50
I've cleaned up the question a bit (grammar, formatting, etc) - is there anything that I shouldn't have changed? I don't want to make the question go against your original intent. — Deusovi, Jan 18 '16 at 23:28
Read the answers at http://puzzling.stackexchange.com/questions/546/clever-ways-to-solve-mastermind . Most of them are applicable here as well. Your particular version has been mentioned by @JoeZ. I have not flagged because I am not 100% sure, but I have a strong feeling this would qualify as a duplicate question. — ghosts_in_the_code, Jan 19 '16 at 11:11
@ghosts_in_the_code i was asking myself the same question, in the end i didn't flag either and linked to the most applicable part of the best answer there. — DrunkWolf, Jan 19 '16 at 11:17
i do not agree this is the same as the games u linked, 10 different numbers makes the game much more complicated. but it is a close one though as u suggested. — Oray, Jan 19 '16 at 14:41
@Oray it hardly gets more complicated, you'd use the exact same algorithm. It will take more then 5 turns though — DrunkWolf, Jan 19 '16 at 16:19

DrunkWolf · Answer 1 · 2016-01-20T10:08:55.680

1

The answer is

11

Using a script to simulate games where one picks randomly but draws perfect conclusions (excludes all possible configurations that can be eliminated based on previous guesses) given in javascript here as determined over runs of 10 million.

Comparing this to the normal version with 6 pegs we see that the average solve time with random guessing increases from 4.638 to 6.05 even though the amount of initial possibilities goes from 1296 to 9000.

edited Jan 20 '16 at 10:08

answered Jan 19 '16 at 11:14

DrunkWolf

2,418
1
13
25

sorry but this is bit applicable to my question because there are 10 different colors/numbers for this case. – Oray Jan 19 '16 at 14:33
@Oray true, I'll write a "random-smart" solver later an see how long that takes in worst case – DrunkWolf Jan 19 '16 at 16:25
@Oray ok so i wrote a 'random-smart' solver here and i've let it run up to a million runs. Haven't gotten a run that took more then 11 guesses. What it does is it generates all possible configuration, guesses randomly from between them, and eliminates all configurations that are no longer possible before guessing again. It averages steadily around 6 tries, and i don't believe it will go past 11 (or maybe 12) – DrunkWolf Jan 19 '16 at 18:18
yes the answer is 11 :) but there is a good explanation rather than running a program :p – Oray Jan 19 '16 at 18:20
@Oray writing a program is usually a lot faster though :) And it's nice to see that a very simple strategy that's also very doable by hand produces adequate results. – DrunkWolf Jan 19 '16 at 18:23
thanks for the coding but it will take a little time to figure the function of random-smart... :) – Oray Jan 19 '16 at 18:31

LowIntHighCha · Answer 2 · 2016-01-19T11:37:24.397

Let's assume the number is 1234

First guess will be 7890, response 0 (we know 7890 aren't included)

Second guess will be 5612, response -2 (two of 5612 are included, don't know where)

Third guess will be 3456, response -2 (two of 3,4,5,6 are included. Since we know from guess 1 that 7,8,9 and 0 don't feature, the other two digits must be 1 and 2. This means that keeping 5 and 6 from the second guess was incorrect, and going forward we need 1,2,3 and 4 in some order)

Fourth guess - 4,3,2,1, response is -4 (from guess 2, we now know that 1 and 2 are not the last 2 digits)

Fifth - 2,1,4,3, response is -4

Sixth - 1,2,3,4, response is 4 and we win.

This assumes that no digits in the answer can be repeated and that there isn't a worse way to mix things up between steps 4 and 5.

this is good start but in the worst case, you cannot guess 7890 at first. it is actually a good start for this game — Oray, Jan 19 '16 at 14:34

Guess my number

2 Answers2