Trying to find an algorithm for the Number Mastermind game

[Arman777]

I am trying to write a code to guess the secret number. For example, if I have a secret number called 412.
My code will take the inputs as

120 - 0
312 - 2
439 - 1

where the numbers on the right gives the position of the correct digit at the correct location. I have thought some codes but it seems they would contain many many lines of codes. Can someone recommend me some algorithms

 

[Baluncore]

https://en.wikipedia.org/wiki/Mastermind_(board_game)#Algorithms_and_strategies

 

[Arman777]

The problem is I am given the number of guesses by another user. I mean I am not getting any values from a server or something. I am given the data let me give you an example. FOr instance I have given only data such as

402 0
390 0
816 2
848 2
777 0
815 1

By using only this data how can I find the secret number ?

 

[Baluncore]

By using only this data how can I find the secret number ?

If those are successive guesses with a score, all from one previous game, then how do you know that there is sufficient information to identify only one code, secret number?
Maybe your last guess will be different to the codebreaker's last guess.

 

[Halc]

The game is supposed to give two scores for each guess.
In master-mind, it was black pegs for correct color in correct position, and white for correct color in wrong position. There were two algorithms for white pegs which differed if a color could appear more than once in the answer.

I wrote a small program to play the other side so I could do it solitaire instead of requiring a second person. With 4 pegs each filled with one of 6 random colors, I could work out the answer in typically under 5 guesses.

 

[Mark44]

I am trying to write a code to guess the secret number. For example, if I have a secret number called 412.
My code will take the inputs as

120 - 0
312 - 2
439 - 1

where the numbers on the right gives the position of the correct digit at the correct location.

If the secret number is 412, shouldn't the algorithm tell you if you get two digits correct, or even all three? Why is only digit 2 in the middle guess above identified? The third digit is also correct.

The game is supposed to give two scores for each guess.
In master-mind, it was black pegs for correct color in correct position, and white for correct color in wrong position. There were two algorithms for white pegs which differed if a color could appear more than once in the answer.

This post seems to be related to the questions I've asked above. I've never played Mastermind, so I don't know how the game is played.

 

[Halc]

If the secret number is 412, shouldn't the algorithm tell you if you get two digits correct, or even all three? Why is only digit 2 in the middle guess above identified? The third digit is also correct.

2 means two of the digits are correct. It doesn't identify which ones.

 

[Mark44]

2 means two of the digits are correct. It doesn't identify which ones.

Which is different from what was stated in the OP.

where the numbers on the right gives the position of the correct digit at the correct location.

 

[Baluncore]

By using only this data how can I find the secret number ?

This is a protean game, with very many different implementations and rules.
The last rule is always; “Other rules may be specified.”

There is no possibility of writing code until every rule has been specified.
You may as well be playing “Mornington Crescent” or any of it's derivatives.
https://en.wikipedia.org/wiki/Mornington_Crescent_(game)

 

[pbuk]

Is this another coding challenge related question? It certainly isn't any standard version of the Mastermind game which is as others have described (and solutions for which are published as others have also linked).

The idea of a coding challenge is for you to work it out yourself. It is OK to ask for help with technical issues but asking for someone else to solve a problem so that you can submit the solution to a coding challenge is a waste of everyone's time.

 

[Arman777]

Is this another coding challenge related question? It certainly isn't any standard version of the Mastermind game which is as others have described (and solutions for which are published as others have also linked).

The idea of a coding challenge is for you to work it out yourself. It is OK to ask for help with technical issues but asking for someone else to solve a problem so that you can submit the solution to a coding challenge is a waste of everyone's time.

I am really not looking for a code. I am just trying to implement an algorithm. I have found one but it requires a great amount of coding and I was looking for a clever one.

Consider this as a new a game it looks like a mastermind yes, but it is different. Let me be muc more clear about the question. Suppose my friend Julia and I playing this game. She guessed a number which I don't know.

And she guessed "846". And my guesses are

402 0
390 0
816 2
848 2
777 0
815 1

For each guess Julia should answer how many digits are correct i.e. are the same in the proposed value and in his secret number - and are placed in the same position.

My algorithm should take the guess values and obtain the secret number.

 

[Arman777]

I think its a challenging question and we can find some clever algorithm to solve the problem with minimum effort.

 

[pbuk]

This

I am really not looking for a code. I am just trying to implement an algorithm. I have found one but it requires a great amount of coding and I was looking for a clever one.

No, the idea is not to implement someone else's algorithm, the idea is to come up with the algorithm yourself. This belongs in homework really so if the following hint isn't enough to get to one solution I suggest you repost there.

Spoiler

Solving a problem by 'brute force' means trying every possible solution and seeing if it works. Often there are too many possible solutions to make this work in a reasonable amount of time so we have to try something else. How many possible solutions are there here?

 

[Vanadium 50]

What is it you want?

You asked for an algorithm for Mastermind.
You got one.
Then you said, "No, no, this isn't Mastermind. It is some other game like Mastermind."

You have to give us the rules. It is not sufficient to give us one example of a played game and hope we can infer the rules. You are asking us to guess the correct question and then provide the answer.

 

[Arman777]

This

No, the idea is not to implement someone else's algorithm, the idea is to come up with the algorithm yourself. This belongs in homework really so if the following hint isn't enough to get to one solution I suggest you repost there.

Spoiler

Solving a problem by 'brute force' means trying every possible solution and seeing if it works. Often there are too many possible solutions to make this work in a reasonable amount of time so we have to try something else. How many possible solutions are there here?

I know that its just I am trying to create a discussion type subject. You don't have to give me the answer. I can start by telling my idea

So for the 3 digit number we can separate the digits. Let me consider the previous example

1 - Create an array that contains all the 3 digit numbers (100, 999) (Let us call this array pos_num)
2- Take a guess number (let us take 402)
3 - If the returned value is "0",
3 - Seperate its digits _4_, _0_, _2_
4 - Remove all numbers that contains _4_ in the first digit, similarly remove all the numbers that contains _0_ in the second digit and remove all the numbers that contain _2_ at the third digit.

It goes like this. Its similar if the returned value is 1 and for the 2 but it seems a bit messy to create a code. This is not a homework ..

 

[Halc]

I can start by telling my idea

So for the 3 digit number we can separate the digits. Let me consider the previous example

1 - Create an array that contains all the 3 digit numbers (100, 999)

First of all, zero is not legal as a first digit? That's one 'color' that is not legal in certain positions, which kind of goes against the general master-mind vibe. The general form of the game is X many positions, and Y many colors/characters that each position can be. There's no rule about it having to look like a number at all, let alone a normalized one. The program I use uses letters, so up to 26 'colors'.
Your OP is very vague about this. Nowhere does it say that the number of digits of your normalized number is known, so the correct answer may well be 332780195.
Secondly, this brute method works for this trivial example of a thousand possibilities, but not so good if there's say 20 positions and 17 colors to choose from. Your computer doesn't have enough time or memory for an array that large.

How does a human do it? I don't find myself iterating though all 1000 numbers and rejecting them one by one. I can glance at just those middle two clues and narrow it down to just two possibilities. What is a non-brute method that might do that?

Finally, suppose there is more than one answer that satisfies all the clues. How does the algorithm pick one? Just say "unsolvable with current information"? Or is it playing the game and needs to choose something? If the latter, what makes for a good choice vs. a poor one? Does it only pick from the list of possible solutions or is it trying to minimize the number of guesses needed?

 

[Baluncore]

Let the first poor guess be 402 – 0. Then a second very lucky guess is 846, which happens to be the correct answer.

If I gave you 402 – 0, you could not possibly derive the correct answer from that one bad guess.

It demonstrates that there may be no rational solution to many examples.

 

[Jarvis323]

Is this the game?

You guess a number. If it's wrong you get back the number of correct digits. The goal is to find the answer using the fewest guesses?

If so, you probably want to track not just what you've ruled out, but also the probabilities.

 

[pbuk]

1 - Create an array that contains all the 3 digit numbers (100, 999) (Let us call this array pos_num)

Like @Halc I am surprised that you are excluding the possibility of 0 as a first digit.

2- Take a guess number (let us take 402)
3 - If the returned value is "0",
3 - Seperate its digits _4_, _0_, _2_
4 - Remove all numbers that contains _4_ in the first digit, similarly remove all the numbers that contains _0_ in the second digit and remove all the numbers that contain _2_ at the third digit.

So doing it that way you take the set of possible solutions and eliminate from it elements that cannot be solutions - that should work, at the end you should have left only candidates that fit each of the marking responses (of which there may be none, one or more than one).

I can think of an easier way to find candidates that fit each of the marking responses though, can you?

This is not a homework ..

No but it fits the criteria for the homework section, I'll get it moved.

Secondly, this brute method works for this trivial example of a thousand possibilities, but not so good if there's say 20 positions and 17 colors to choose from. Your computer doesn't have enough time or memory for an array that large.

Yes but we don't have 20 positions and 17 colours: premature generalisation is an even bigger sin than premature optimisation IMHO.

If I gave you 402 – 0, you could not possibly derive the correct answer from that one bad guess.

Why do you see this as a problem? A suitable algorithm should be able to identify and report all possible solutions, even if there are more than one (or none).

It demonstrates that there may be no rational solution to many examples.

What does an irrational solution look like

 

[pbuk]

Oh, you might find the following piece of code useful:

def getDigit(n, index):
  return (n // (10 ** index)) % 10

 

[sysprog]

I was ready to give the post #19 reply of @pbuk a 'like', but the

What does an irrational solution look like

at the end made me change the 'like' to a 'haha', and now he gets a 'like' for post #20 $\dots$

 

[Halc]

If so, you probably want to track not just what you've ruled out, but also the probabilities.

There are probabilities? I mean, each clue eliminates a bunch of otherwise viable answers. The remaining ones are equally probable assuming it was randomly chosen in the first place.
That said, some next-guesses are far superior to other ones, and a good algorithm would choose one of those despite the fact that all remaining possibilities are equally probable. Sometimes the best next guess is one that is known to have been eliminated, and thus has zero probability of being correct.

Yes but we don't have 20 positions and 17 colours: premature generalisation is an even bigger sin than premature optimisation IMHO.

I could just write a program that does effectively: print ("846") then. It seems to be a generalization to write one that prints the answer for a different data set. Just saying, where do you draw the line?
I always think in terms of scalability, but nevertheless agree that a good scalable solution may not be optimal if the working dataset is known to be confined to small cases.

 

[Jarvis323]

There are probabilities? I mean, each clue eliminates a bunch of otherwise viable answers. The remaining ones are equally probable assuming it was randomly chosen in the first place.
That said, some next-guesses are far superior to other ones, and a good algorithm would choose one of those despite the fact that all remaining possibilities are equally probable. Sometimes the best next guess is one that is known to have been eliminated, and thus has zero probability of being correct.I could just write a program that does effectively: print ("846") then. It seems to be a generalization to write one that prints the answer for a different data set. Just saying, where do you draw the line?
I always think in terms of scalability, but nevertheless agree that a good scalable solution may not be optimal if the working dataset is known to be confined to small cases.

The probability would be based on your knowledge (in a Bayesian sense).

There would be probabilities for each digit separately. For example, if your first guess is 123 and it gives back 2. Then it means that 1 out of 3 digits were incorrect. So there is a 2/3 chance for each digit that it is the one you guessed and 1/3 probability it is something else.

At each guess there would be one or more maximum likely guesses. You keep updating your probabilities after each guess.

A greedy algorithm would always choose one of the most probable new guesses. I'm not saying that the greedy algorithm is necessarily optimal though. That was just my initial thought.

 

[Arman777]

I can think of an easier way to find candidates that fit each of the marking responses though, can you?

Maybe a hint ?

 

[pbuk]

I could just write a program that does effectively: print ("846") then. It seems to be a generalization to write one that prints the answer for a different data set.

No, it is a requirement that the program works out the solution for any set of marked guesses, not just the example.

Just saying, where do you draw the line?

At the requirements. It is a requirement to solve for any 3-digit problem.

 

[pbuk]

Maybe a hint ?

Well I am not sure I can give a much better hint, and there seems to be a few posts here getting lost down rabbit holes so I am just going to post a solution in the spoiler below and on repl.it.

Spoiler

# The number of digits in a possible solution.
DIGITS = 3

def getDigit(n, index):
  return (n // (10 ** index)) % 10

def mark(answer, guess):
  correct = 0
  for digit in range(DIGITS):
    if getDigit(guess, digit) == getDigit(answer, digit):
      correct += 1
  return correct

def solve(problem):
  solutions = []
  # Iterate over all possible answers.
  for answer in range(10 ** DIGITS - 1):
    markIsWrong = False
    # Check the mark given for each round.
    for [guess, marked] in problem:
      if mark(answer, guess) != marked:
        markIsWrong = True
        break
    if (not markIsWrong):
      solutions.append(answer)
  return solutions

# Try the example problem.
problem = [
  [402, 0],
  [390, 0],
  [816, 2],
  [848, 2],
  [777, 0],
  [815, 1],
]

solutions = solve(problem)
count = len(solutions)

if count == 0:
  print('No solutions found')
elif count == 1:
  print('Found unique solution', solutions[0])
else:
  print('Found', count, 'solutions:', solutions)

 

[Halc]

No, it is a requirement that the program works out the solution for any set of marked guesses, not just the example.

At the requirements. It is a requirement to solve for any 3-digit problem.

Obviously, but I saw no such explicit requirement in the OP, so I labeled that a generalization, which is how a scalable solution was labeled by you. The OP asked how to solve the one example, and it didn't even specify that the size of the number was known to be 3 items, and that the items were to be selected from and only from an alphabet of 10 digits. Without such a specification, it wasn't really known how complex the program needed to be.
Really, the brute method is probably optimal for a 3-digit number. Saving an extra 100th of a second isn't going to get anybody back to their family any sooner.

The clues in the OP are not enough to determine a unique answer. Was the program to simply report this fact, or should it take a valid guess, or should it play an optimal move? The 'specification' doesn't say.

The probability would be based on your knowledge (in a Bayesian sense).

There would be probabilities for each digit separately. For example, if your first guess is 123 and it gives back 2. Then it means that 1 out of 3 digits were incorrect. So there is a 2/3 chance for each digit that it is the one you guessed and 1/3 probability it is something else.

But the purpose of the program is not to find the probability that the first digit is X. It is supposed to find the one (or one of? or a list of all?) answer.

At each guess there would be one or more maximum likely guesses.

Kindly illustrate with an example where one answer is more likely than any other.

For instance, suppose the answer is 412 (per OP) and the one and only (very lucky) guess so far is 312 which yields an reply of <2 correct>. That means each of the 3, 1, and 2 has a 2/3 probability of being correct. So what? That just means that in a list of all the 27 possible answers, each of those digits appears in its respective place in 18 of them, but it doesn't make anyone of those 27 answers more probable than any other.

 

[Arman777]

I won't look at it..as I said I am not looking for a solution..let me try to think more and maybe I start a new thread..and when I find it I ll come back and compare.. but that's really amazing you find a solution in such a short time. I guess I am not really a good coder

 

[Vanadium 50]

A greedy algorithm would always choose one of the most probable new guesses. I'm not saying that the greedy algorithm is necessarily optimal though. That was just my initial thought.

Well, it's hard to tell since we seem to be playing Calvinball, but I think "greedy" has at least two meanings: one would be to get the highest possible number of hits on this turn, and the other would be to remove as many incorrect solutions from the search space as possible.

The example is likely confusing because it is an example of non-optimal play:

402 0
390 0
816 2
848 2
777 0
815 1

After 848 there are only two possibilities: 846 and 818. Guessing 777 gives no new information. Guessing 717 or 776 or 778 etc. would all you to infer the answer in the next turn, but at this point no strategy is better than guessing one number and if it isn't right, guessing the other.

 

[Jarvis323]

But the purpose of the program is not to find the probability that the first digit is X. It is supposed to find the one (or one of? or a list of all?) answer.

I obviously misread the problem statement if you read my first post.

Kindly illustrate with an example where one answer is more likely than any other.

For instance, suppose the answer is 412 (per OP) and the one and only (very lucky) guess so far is 312 which yields an reply of <2 correct>. That means each of the 3, 1, and 2 has a 2/3 probability of being correct. So what? That just means that in a list of all the 27 possible answers, each of those digits appears in its respective place in 18 of them, but it doesn't make anyone of those 27 answers more probable than any other.

In the case where you already have 2 out of 3 right, and know nothing else, then it is true that each possible answer is equally likely next. An example where they aren't equal is after getting back a 1 on the first guess. With more than 3 digits you would get a lot more interesting and complicated situations in terms of probability.

 

[pbuk]

The example is likely confusing because it is an example of non-optimal play:

It is true that the OP was not as clear as they could have been, but it is clear to me at least that the problem is NOT to find an a priori strategy for playing the game by making guesses, it is to determine ex post from a set of marked guesses the solution(s) (if any).

 

[Halc]

In the case where you already have 2 out of 3 right, and know nothing else, then it is true that each possible answer is equally likely next. An example where they aren't equal is after getting back a 1 on the first guess.

[/QUOTE]So you assert.
Back to the OP, guessing 439 (1). That just means that in the remaining list of all the 243 possible answers , each of those digits appears in its respective place in 81 of them, but it doesn't make anyone of those 243 answers more probable than any other. I notice you didn't call out any specific answer as being more probable than some other valid answer.
Yes, the list is longer with a reply of 1 (and even longer with 0 in the case of only 3 digits), but that doesn't make their probabilities unequal.

With more than 3 digits you would get a lot more interesting and complicated situations in terms of probability.

With more than 3 digits, there would be n*9^n-1 possible answers, all equally probable.

 

[Jarvis323]

So you assert.
Back to the OP, guessing 439 (1). That just means that in the remaining list of all the 243 possible answers , each of those digits appears in its respective place in 81 of them, but it doesn't make anyone of those 243 answers more probable than any other. I notice you didn't call out any specific answer as being more probable than some other valid answer.
Yes, the list is longer with a reply of 1 (and even longer with 0 in the case of only 3 digits), but that doesn't make their probabilities unequal.
With more than 3 digits, there would be 9ⁿ possible answers, all equally probable.

https://en.wikipedia.org/wiki/Bayesian_probability

439 (1) means P(437) > P(457) > 0

 

[Arman777]

It is true that the OP was not as clear as they could have been, but it is clear to me at least that the problem is NOT to find an a priori strategy for playing the game by making guesses, it is to determine ex post from a set of marked guesses the solution(s) (if any).

Yeah that's the whole idea. Guesses are given by the computer. No one is guessing in here. Someone puts the guesses in front of you and he says its certain that for the given numbers, you ll find the secret number. What would be your algorithm to obtain this secret number from the given list of guesses

 

[pbuk]

I won't look at it..as I said I am not looking for a solution..let me try to think more and maybe I start a new thread..and when I find it I ll come back and compare..

I'll give you another hint. From the example in #3:

Guess Mark
402    0
390    0
816    2
848    2
777    0
815    1

How can I tell that the secret is not 400?

thats really amazing you find a solution in such a short time. I guess I am not really a good coder

I've been doing this sort of thing for 45 years which means that (i) I have had a lot of practice and (ii) I have seen many different problems with some similar characteristics.

 

[Halc]

439 (1) means P(437) > P(457) > 0

Au contraire, P(437) is zero. It cannot be the correct answer, while P(457) is 1/243.
437 has a higher probability of not scoring (0), but it has a zero probability of scoring (3).

 

[Jarvis323]

Au contraire, P(437) is zero. It cannot be the correct answer, while P(457) is 1/243.
437 has a higher probability of not scoring (0), but it has a zero probability of scoring (3).

Oh yeah, that's true.

How about after having made these guesses?

123 (1)
353 (1)

Maybe you're right in your claim that at no point will the probability of one possible solution be different than another in the Bayesian sense (even in the generalized game to n digits)? But based on my intuition, I sort of doubt that. I might try to work it out later on when I have some more time.

It was only a suggestion, as my first thought.

 

[Halc]

Maybe you're right in your claim that at no point will the probability of one possible solution be different than another in the Bayesian sense (even in the generalized game to n digits)?

Yes, even under the generalized game. But as I said, if P(guess) is defined as probability of not scoring zero, then your relation P(437) > P(457) above is true, at least for a low number of digits and a single initial guess scoring 1.

How about after having made these guesses?

123 (1)
353 (1)

It gets only slightly more complicated now.
If the trailing 3 is correct, then all the other digits are wrong and there are 64 possibilities remaining.
Otherwise the solution is 15x or 32x which totals more 18 possibilities, so the any given valid guess has an equal 1/82 probability of being correct. Did I do that right? The solutions in the two subsets cannot overlap, so you can just add them.

Maybe a hint ?

For the general case I'd have gone with a recursive algorithm, but the brute iteration probably works fine for these simple cases.

 

[Arman777]

How can I tell that the secret is not 400?

From these two lines..
402 0

4 cannot be since it is 0.

I'll give you another hint. From the example in #3:

Guess Mark
402    0
390    0
816    2
848    2
777    0
815    1

How can I tell that the secret is not 400?I've been doing this sort of thing for 45 years which means that (i) I have had a lot of practice and (ii) I have seen many different problems with some similar characteristics.

I understand the idea but these days I am really busy. But I ll try to write a code soon.

 

[Arman777]

I find the solution. But I write in R

digit_1 - c()
digit_2 - c()
digit_3 - c()
a - seq(100, 999)
for (i in a)
{
  b - unlist(strsplit(as.character(i), ))
  digit_1 - append(digit_1, as.integer(b[1]))
  digit_2 - append(digit_2, as.integer(b[2]))
  digit_3 - append(digit_3, as.integer(b[3]))
}
#creating a data frame for digits between (100, 999)
num_list - data.frame(digit1 = digit_1, digit2 = digit_2, digit3 = digit_3)

#obtaining the digits of a function as an array
digits - function(num)
{
  b - unlist(strsplit(as.character(num), ))
  return (c(as.integer(b[1]), as.integer(b[2]), as.integer(b[3])))
}

#For guess = 0
guess0 - Problem36_data$V1[Problem36_data$V2 == 0]
for (num in guess0)
{
  d - digits(num)
  ind1 - num_list$digit1 != d[1]
  ind2 - num_list$digit2 != d[2]
  ind3 - num_list$digit3 != d[3]
  num_list - num_list[ind1 & ind2 & ind3, ]
}

guess1 - Problem36_data$V1[Problem36_data$V2 == 1]
for (num in guess1)
{
  d - digits(num)
  ind1 - num_list$digit1 == d[1]
  ind2 - num_list$digit2 == d[2]
  ind3 - num_list$digit3 == d[3]
  num_list - num_list[ind1  ind2  ind3, ]
}

guess1 - Problem36_data$V1[Problem36_data$V2 == 1]
for (num in guess1)
{
  d - digits(num)
  ind1 - num_list$digit1 == d[1] & num_list$digit2 == d[2]
  ind2 - num_list$digit1 == d[1] & num_list$digit3 == d[3]
  ind3 - num_list$digit2 == d[2] & num_list$digit3 == d[3]
  ind4 - ind1  ind2  ind3
  num_list - num_list[!ind4, ]
}guess2 - Problem36_data$V1[Problem36_data$V2 == 2]
for (num in guess2)
{
  d - digits(num)
  ind1 - num_list$digit1 == d[1] & num_list$digit2 == d[2]
  ind2 - num_list$digit1 == d[1] & num_list$digit3 == d[3]
  ind3 - num_list$digit2 == d[2] & num_list$digit3 == d[3]
  num_list - num_list[ind1  ind2  ind3, ]
}

First a created a data frame of digits and then applies some conditions to obtain the secret number. For instance, if we had 4 digits, could we apply the same algorithm ?

 

[Arman777]

Well I am not sure I can give a much better hint, and there seems to be a few posts here getting lost down rabbit holes so I am just going to post a solution in the spoiler below and on repl.it.

Spoiler

# The number of digits in a possible solution.
DIGITS = 3

def getDigit(n, index):
  return (n // (10 ** index)) % 10

def mark(answer, guess):
  correct = 0
  for digit in range(DIGITS):
    if getDigit(guess, digit) == getDigit(answer, digit):
      correct += 1
  return correct

def solve(problem):
  solutions = []
  # Iterate over all possible answers.
  for answer in range(10 ** DIGITS - 1):
    markIsWrong = False
    # Check the mark given for each round.
    for [guess, marked] in problem:
      if mark(answer, guess) != marked:
        markIsWrong = True
        break
    if (not markIsWrong):
      solutions.append(answer)
  return solutions

# Try the example problem.
problem = [
  [402, 0],
  [390, 0],
  [816, 2],
  [848, 2],
  [777, 0],
  [815, 1],
]

solutions = solve(problem)
count = len(solutions)

if count == 0:
  print('No solutions found')
elif count == 1:
  print('Found unique solution', solutions[0])
else:
  print('Found', count, 'solutions:', solutions)

Your algorithm seems different. Not what I was expected actually

 

[Frodo]

I am really not looking for a code. I am just trying to implement an algorithm. I have found one but it requires a great amount of coding and I was looking for a clever one.

Consider this as a new a game it looks like a mastermind yes, but it is different. Let me be muc more clear about the question. Suppose my friend Julia and I playing this game. She guessed a number which I don't know.

And she guessed "846". And my guesses are

402 0
390 0
816 2
848 2
777 0
815 1

For each guess Julia should answer how many digits are correct i.e. are the same in the proposed value and in his secret number - and are placed in the same position.

My algorithm should take the guess values and obtain the secret number.

The simplest method is the slowest with a max of 1,000 steps or 500 on average.
Start:
try all numbers 000 - 999 until you get 3 correct.
End:
You can speed it up because you know the changed digit(s) was the correct one.

The next method probably needs 2 or 3 random guesses at max, followed by 30 guesses at max for, say 33 guesses max or 17 on average.

Make random guesses till you have 0 correct.
Vary digit 1 till you have 1 correct, then vary digit 2 till you have 2 correct, then vary digit 3 till you have 3 correct.

The more complex the algorithm, the less steps are required. The next method should give you some ideas but is undoubtedly wrong in detail. Each step can be further optimised to solve in fewer guesses by remembering which is the correct (the varied) digit and not changing it again.

Start:
Solve_0
Make random guess (making a different guess for repeats will speed it up)
If 0 correct GOTO Solve_0
If 1 correct GOTO Solve_1
If 2 correct GOTO Solve_2
If 3 correct GOTO END

Solve_1:
REM We have 1 correct
Choose a digit at random and vary it
- If you now have none correct, the varied digit was correct. Put it back and remember it. Choose another digit and vary it. When you get 2 correct, vary the third till all 3 are correct. GOTO END
- if you still have one correct, keep varying the varied digit until you have two correct. GOTO Start_2
- if you have 2 correct GOTO Start_2

Start_2:
REM We have 2 correct
Solve_2:
Choose a digit at random and vary it (remembering correct digit(s) from Solve_1 will speed it up)
- if you still have two correct, keep varying that digit till you solve it. GOTO END
- If you now have only one correct, the one you varied was correct. Remember and vary another until you have 2 correct. Vary the third till you have 3 correct. GOTO END

END:

A recursive program would probably be just a few lines of code. To solve 3 we need to start with 2 solved. To solve 2 we need to start with 1 solved. To solve 1 we need to start with 0 solved.

 

[Vanadium 50]

Frodo is right - the simplest is exhaustive. You have 1000 choices to check, and very conservatively, a computer can do a million per second, so you finish in a millisecond. How much faster does this need to be?

Put another way, no matter how many times a computer plays this game, you will never recover the time it takes to write a single additional line of code.

If your response is "fiddlesticks - I want speed, speed and more speed". The fastest thing to do is to look at the zeros and remove them from the searches: in the example, you know there are no 0s, 2s, 3s, 4s, 7s or 9s. That reduces the number of possibilities to check to 64. It's sure going to be faster to test all 64 than to figure out how to test a few less.

You can speed it up because you know the changed digit(s) was the correct one.

Not if you run them in normal arithmetic order. If 119 has zero matches and 120 has one, is the 2 right or the 0? You would need to use something like Gray coded decimals.

 

[Frodo]

Not if you run them in normal arithmetic order. If 119 has zero matches and 120 has one, is the 2 right or the 0? You would need to use something like Gray coded decimals.

Sorry - I didn't make myself clear. If you are at 163 and you have zero correct, and you go to 164, and you have one correct, it must be the 4. You now only have to check the first two digits. It fails at 169 goes to 170.

More complexity results in fewer guesses needed to get the number. You could do a Gray code like progression (only one digit changes at a time) of the decimal digits - I think it results in needing about 11% more numbers to cover the field as some must be repeated to ensure only 1 decimal digit changes at each guess.

If you want the fewest number of guesses to get the solution then you need to construct a logic tree and decide what is the best guess to make now knowing everything you have already deduced - it's a type of state table.

Basically, after your first guess of a, b, c, you have four branches: 0 correct, 1 correct, 2 correct each with location unknown; or three correct.

With 0 correct, remove the 3 digits a, b, c you chose so you have only 7 left to work with. Do a random guess with d, e, f from these 7 digits.

With 1 correct you don't know where it is but you know one digit is a or b or c. Follow the logic above.

With 2 correct but not knowing which digits or where, follow the logic above.

You will, for example, need one route for "1 correct, position known" and another for "1 correct, position unknown".

This should get it done with the fewest number of guesses.

See Martin Gardner's A matchbox game learning machine Chapter 35 in The Colossal Book of Mathematics where he describes HER, a Hexapawn Educatable Robot, built from 28 matchboxes to play the game of Hexapawn. I have uploaded the pages in the PDF below. See the graph - starting from nothing it took the matchboxes 36 games, including 11 defeats, to "work out" how to play a perfect game.

You could probably make a matchbox equivalent to play your number guessing game.

Years ago I wrote a solver for proper Mastermind using APL and it took eight lines of code. It included full error checking of the input and I didn't sweat trying to put it all on one line which was probably possible. I redid it in Basic and it was about 140 loc ... and failed on first trial when someone typed a Backspace into the input field

 

[Vanadium 50]

Sorry - I didn't make myself clear. If you are at 163 and you have zero correct, and you go to 164, and you have one correct, it must be the 4. You now only have to check the first two digits. It fails at 169 goes to 170.

I understand that. But if you are at 119 and you have zero correct, and you go to 120, and you have one correct, you don't know if the right digit was 2 or 0. So if you want to do this, you need to organize things so you only change one digit at a time, e.g.

111
112
122
121
221
222
223
123
...
As I said above, I don't see a good reason to need to do better than a millisecond. If you feel the need to do 50 microseconds for personal pride, well...

Since this is about inferring the secret number based on someone else's guesses, and not coming up with a guessing strategy, a reasonable question is whether we are using the information in the best order.

If the first guess returns a zero, there are 343 remaining possibilities.
If the first guess returns a one, there are 243 remaining possibilities.
If the first guess returns a two, there are 27 remaining possibilities.
If the first - or any - guess returns a three, the answer is trivial.

That suggests there is something to be gained by looking at the input in the right order.

 

[votingmachine]

Well, it's hard to tell since we seem to be playing Calvinball, but I think "greedy" has at least two meanings: one would be to get the highest possible number of hits on this turn, and the other would be to remove as many incorrect solutions from the search space as possible.

The example is likely confusing because it is an example of non-optimal play:
After 848 there are only two possibilities: 846 and 818. Guessing 777 gives no new information. Guessing 717 or 776 or 778 etc. would all you to infer the answer in the next turn, but at this point no strategy is better than guessing one number and if it isn't right, guessing the other.

You know it is not 818 because 815 contains only one digit in the right place. That sequence of guesses and answers has only one remaining solution.

I will spitball how I think it might work.
I think I would create two 10x10x10 matrix which would correspond to the answer set. And have two options a 0 (for incorrect), or a 1 (for correct). Start with everything set to 0 in Matrix-A and 1 in Matrix-B. Matrix A has to be re-set to 1 after each round.

Any answer that is ZERO allows 3 sets to be marked as incorrect in the Matrix-B. So if you guess 1,1,1 and get zero, then 1,a,b is incorrect, a,1,b is incorrect, and a,b,1 is incorrect.

Any answer that is ONE allows 3 sets to be marked as correct in the Matrix-A. So if you guess 1,1,1 and get ONE, then 1,a,b is correct. As is a,1,b and a,b,1. In Matrix B, you change the 1,1,a and 1,a,1 and a,1,1 (those would have required a TWO).

Then compare Matrix B to Matrix A. Change any 1's in B to 0's if they are 0's in A.

Any answer that is TWO requires marking some other space as correct in Matrix-A. Again using 1,1,1 and getting TWO ... 1,1,a is marked as correct. 1,a,1 and a,1,1 get marked as correct. Set 1,1,1 as incorrect.

Then compare Matrix B to Matrix A. Change any 1's in B to 0's if they are 0's in B.

Codewise, you keep looping the same three counters from 0-9. You know you have an answer when the sum of the Matrix-B elements is 1.

Each guess allows you to mark elements as incorrect, in a freshly initialized Matrix A. Then transfer the information of disallowed answers into the matrix that started with everything allowed.

I think a person keeps track of the things that are excluded, or required, and tests the possible right answers against the others. Although this is not Mastermind, before you make the next guess, you see how the previous scoring would look against it. If it is not perfectly consistent with previous scoring, you try again. You have to exclude all the guesses that the current information excludes. I'm not sure how we do that in our head, but coding, I would do it with record keeping 10x10x10 matrices, and an i,j,k nested loop system.

In prior programs I have written, I have found that it is often necessary to mave more matrices than you expect. It might be good to have a 3rd. The code can often be very compact if you get the matrices and tests precisely thought out. Because you don't want to change the matrices to lose previous info, you often need a BUNCH of placeholder Matrices.

For example, the two guesses 848 and 816 in the example. The first allows 8,4,a and 8,a,8 and a,4,8. The second allows 8,1,a and 8,a,6 and a,1,6. The second guess allows a set that intersects with the set allowed by the first. If your code tracks the DISallowed sets, and keeps them cumulatively, then there ends with one answer. The other guess in that series of 815 and an answer of ONE, allows the sets 8,not-1,not-5 and not-8,1,not-5 and not-8,not-1,5 to intersect with those.

I hope that helps ... I know I have mistakes, but the gist is that if you set up the right loops and matrices, the code is not that crazy.

 

[pbuk]

I know I have mistakes, but the gist is that if you set up the right loops and matrices, the code is not that crazy.

The code is not crazy at all, I posted one solution in #26 and it fits into 20 SLOC.