0
$\begingroup$

I've been playing a game similar to Bulls and Cows, but it goes like this: one player has to pick a random $4$ digit number. Digits can repeat, any digit between $0$ to $9$ and, you only get the number of digits on correct positions on each guess and you have to guess it in as few tries as you can.

Let's say the number is: $3301$, if I say $3209$ then I get $2$, meaning I've got $2$ positions correct.

I'm trying to find an algorithm that can find the number in maximum $10$-$12$ tries. Until now I have found one that can guess between $6$ and $25$ guesses. You pick random $4$-digit numbers until you find a number with $0$ correct positions, use its digits to permute when you find another number, this time with at least one correct guess. For each digit of this last number, it is used in combination with the ones that aren't correct, and if you get the one, meaning that the digit you picked along with the incorrect ones, is indeed correct and you can add it to the final number. It goes like this until you have the full number.

$\endgroup$
11
  • $\begingroup$ Not sure the "Bulls and Cows" reference is familiar to most users here, might be worth explaining. Also: I suggest editing to include your algorithm that has a worst case of $25$. I assume you are restricting to $4$ digit inputs? $\endgroup$
    – lulu
    Commented May 25 at 22:01
  • $\begingroup$ A "dumb" algorithm: Just guess $0000, 1111, \cdots, 8888$ to get the digits (though not the order). Then try $4!-1$ orders. the worst case for that takes $9+23=32$ guesses. Not surprised to learn that better is possible. $\endgroup$
    – lulu
    Commented May 25 at 22:18
  • $\begingroup$ Post edit: using your principle, we can improve the "dumb" algorithm I mentioned. Note that guessing $0000,1111,\cdots, 8888$ not only yields the four digits (though not the order) but it gives us (several) strings with $0$ hits. Fixing one of those, it then takes (at worst) $3$ guesses to place the first digit, then $2$ guesses to place the second, and $1$ to place the third. Thus the worst case of the improved algorithm is $8+6=14$. $\endgroup$
    – lulu
    Commented May 25 at 22:22
  • $\begingroup$ Thank you for the comment, I just edited the post, hopefully it is more clear now. I think the algorithm I use is a little more efficient than the one you described, though I haven't thought about that method. I found it way harder without knowing the numbers on incorrect positions as in "cows" in the mentioned game. $\endgroup$
    – nex
    Commented May 25 at 22:23
  • $\begingroup$ Yes, I saw your edit...and I sketched how we can combine the two ideas to get a strategy with worst case $14$. I believe the worst case for Mastermind is $7$, so $14$ can't be all that far from optimal. $\endgroup$
    – lulu
    Commented May 25 at 22:24

1 Answer 1

Reset to default
1
$\begingroup$

I believe on can make the worst case $14$ by doing the $0000, 1111, \ldots 8888$ suggested in the comments to find the digits. I assume the worst case is having four different digits as there are $24$ possibilities to sort out. I will use $1,2,3,4$ as the digits. Now we guess $1234$. If we have four hits we are done. We try to minimize the maximum number of possibilities that can give the same answer. I find we can get it down to four with the first guess, then two with the next and finally it might take two to finally get it. If we have two hits we guess $3214$, if we have one hit we guess $3241$ and if we have none we guess $2341$. There are other possibilities that seem to be as good for the guess after $1234$ but I didn't find anything better.

$\endgroup$
2
  • $\begingroup$ Can you give another example where this is more efficient? I'm not quite sure I understand the method $\endgroup$
    – nex
    Commented May 26 at 9:27
  • $\begingroup$ All the examples are the same if you have four different numbers. I suggest you list the $24$ permutations of $1234$ and find how many hits each gives. I found 1 that gives 4 hits, 6 that give 2 hits, 8 that give 1 hit, and 9 that give 0 hits. Among the 9, when you guess 2341 you get 4 hits once, 2 hits twice, 1 hit 4 times, and 0 hits 2 times. The idea is to find the guess that leaves you the fewest possibilities with the same number of hits. $\endgroup$
    – Ross Millikan
    Commented May 26 at 13:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .