"Mastermind"-esque safe opening problem.

I read this interview question for a trading job and it seems quite difficult. What is the technique to solving it?

You have a safe with six digits and a light. You can input a code, if you have between 0 and 3 of the 6 digits correct, the light will turn red. If you have between 4 and 5 of the 6 digits correct, it will turn yellow and if you have all 6 digits correct, it will open. There is $10, 000 inside the safe, you can guess the code as many times as you want, but need to pay each time you guess, how much would you be willing to pay for each guess? Thanks • Not a direct answer, but Knuth's five-guess algorithm for Mastermind seems general enough to be adapted. – user253804 Commented Aug 4, 2015 at 11:40 • Is the light red with 0 digits correct? Commented Aug 4, 2015 at 11:54 3 Answers Let's assume a base$10$number system. Then we can get the light to turn yellow in at most$10^4 = 10, 000$steps by simply brute-forcing the first$4$digits. If the safe unlocks, then we're done. Otherwise, there are either$4$or$5$digits correct. We then change exactly one digit at a time, for all$6$digits. If the light stays yellow for each guess, then we know there are$5$digits correct. Otherwise, there are$4$digits. Let's do the case for$5$first: • Case for$5$: We want to know which digit is not correct. We can find this in$6$more gueses. What we do is change digits$1$and$2$, then$1$and$3$etc. If the light stays yellow for every guess, then digit$1$is out, else the digit for which the light changes is out. In any case, we can solve the whole thing in another$9$guesses maximum.So the total guesses here is at most$10,000 + 6 + 6 + 9$. • Case for$4$: In this case, we recall the$4$digits for which the light changed colour when we changed them earlier. These are the correct ones. So the other two must be changed. There are$99$more combinations to try, so we get a total maximum of$10,000 + 6 + 99$. This is the worst-possible case. So with this approach, we'd need in the worst case$10,000 + 6 + 99$. Assuming a conservative player who wants a profit, the amount you'd be willing to pay is less than one dollar per guess. It isn't very clear in the question, but this is how I read it: The lights go on when the right number(s) are in the right place - that is, the permutation should be right, and not just the combination. Lets say, for example, you are willing to pay, at most 5000\$ as total fees for guessing. So, if you cracked the code in 1000 guess, that's 5\$a guess. But, if you took 10000 guesses, that's 0.5\$ a guess. Thus, the objective is to be able to crack the safe in the least possible guesses.

The safe can accept any of the $10^6$ permutations. The simple brute force method would involve running through that set and hoping that a solution is found. But, that leaves things to chance and it is possible that one may have to run through all the $10^6$ options.

Since the safe-code need not possess any pattern, we only have the lighting to help with our guessing. A maximum limit on the number of guesses can be established by the following method. The actual number of guesses ($N_g$) will be lesser than or equal to it. Initially, the safe reads $$x_0 = [x(1),x(2),\ldots x(6)]$$ and let us assume only the red light is lit (for anywhere between $0$ to $4$ correct numbers). For convenience, let this number be $000000$, but it could be anything.

1. Run $x(1),x(2),x(3),x(4)$ from $0001$ to $9999$. At some point, the light will turn from red to yellow. Thus $\textsf{max} \; N_g = 9999$.
2. Reset $x(4)$ to $0$ (which will turn the light back to red) and run $x(5)$ from $1$ to $9$. At some point, the light turns to yellow again. Thus $\textsf{max} \; N_g = 9999 + 9$.
3. Now, set $x(4)$ and $x(5)$ to their correct values and run $x(6)$ from $1$ to $9$. The safe will open at some point. Thus $\textsf{max} \; N_g = 9999 + 9 + 9 = 10017$.

This is the maximum number of guesses you will have to go through to crack the code. Now set a guessing fee based on the total amount you are willing to spend.

• Why don't you start with $x(1)$ alone, reset, then $x(2)$, then $x(3)$, etc. This way you need $9+9+9+9+9+9= 54$ guesses, and perhaps one or two extra in case your starting point have the red light on. Commented Aug 4, 2015 at 11:58
• Oops, looks I read the question wrongly. I read that the red light is switched on when three numbers are correct. I will make the edit. Thanks :) Commented Aug 4, 2015 at 12:00
• But the red light is on with 0 correct as well so you will not observe a change as x(1) runs from 1 to 9.
– eev2
Commented Aug 4, 2015 at 12:29
• @eev2 I re-read the question wrongly. Thanks for pointing out. :) Edited the answer. Commented Aug 4, 2015 at 12:48

My approach is a novel method that uses Markov Chain process. Essentially this pin-cracking problem is very similar to Mastermind game with k colors and n positions. In this problem, there are six positions creating a six digit sequence. Any sequence that represents the six digit code is chosen from (0-9) ten digits and all are equally likely. However, there are only two lights,namely, red and yellow that turn on when (0-3) digits match with the secret code by digit and position.

I am going to explore this problem even more generally by relaxing the two colors to six colors and that for every set of digits that match a corresponding set in the secret code by number and position, the appropriate light is going to turn on. Lights glowing for different number of correct answers is similar to the encoder giving clues in a game of Mastermind. Ultimately, the light that corresponds to six digits being correct is the desired state.

Remainder of the correct answers will have the respective lights signal their correctness. Thus there are seven states. You could have no light glow for 0 correct digits, a light for 1 correct digit, another light for 2 correct digits and henceforth a light for 6 correct digits. At the start of the game the codebreaker submits one sequence of 6 digits. He could get anywhere from 0 to all 6 being correct. The lights (an encoder) will signal the number of correct digits in number and position. In any of the guesses, if the codebreaker cracks 1 digit, the game reduces to codebreaker guessing other digits by submitting sequences of 5. This mimics a Markov Chain process with seven states and the probability of movement from one state to the other is given in the diagram below. All the states are transient except the last state 6 which is absorbing and the game comes to a close.

In this problem, you are supposed to find the expected number of guesses.

Cost of bet could be viewed as the transaction cost "c". Thus the average maximum payoff $= 10000-23.75349\times c$

Get into Jane Stree and wish you luck.

Thanks

Satish