Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm playing a video game at the moment called Sleeping Dogs, in which some of the mini-missions are to 'hack' a security camera, by guessing a four-digit PIN code.

Here are the rules:

1) You are allowed 6 attempts to enter a four-digit PIN code. After 6 attempts, the PIN code resets to a random (other) one.

2) Repeated digits are not allowed (e.g. $9981, 1131, 5555,$ etc. are not allowed).

3) If the correct digit is in the correct place, that digit will be green.

If the correct digit (i.e. a digit that is in the actual PIN) is in the incorrect place, that digit will be amber.

If an incorrect digit is entered (i.e. a digit that is not in the actual PIN), that digit will be red.

e.g. Suppose that the actual code is $\boxed{1234}.$

If I entered $1427$, it would show up as

$$\color{green}1\color{orange}4\color{orange}2\color{red}7.$$

My question is this:

What is the minimum number of attempts in order to guarantee entry to the system, (can it be achieved with certainty in fewer than six attempts)?

There seem to be so many factors that I can't come up with a quick solution. Any hints/tips would be welcome.


(Background info-- I'm familiar with elementary probability and statistics).

share|improve this question
    
This kind of puzzle was issued commercially under the name "Mastermind", you can find some information here. –  David Aug 15 at 0:43
    
This seems to be a question "Is there a winning strategy in Mastermind which has a provably minimal number of turns?" –  Asaf Karagila Aug 15 at 0:43
1  
Here is what I would have done: Start with $1234$. Let $r$ be the number of red digits, $g$ and $a$ similarly denoted; if $g=4$ we are done; otherwise pick the next $r$ digits, and try a code where all the $a$ digits have been moved around to previously unattempted positions. Repeat. It will probably not give you a six tries win, but it seems like a good approach that one can do quickly. –  Asaf Karagila Aug 15 at 0:54
1  
Say the code is $3825$ and we do the above algorithm, each time pick the code whose numeric value is minimal and satisfies the requirements above, then we have five turns: $$\begin{array}{c|c}1234&raar\\2356&aaar\\3257&gaar\\3528&gaga\\3825&gggg\end{array}‌​$$ (Where the letters denote the color of the digit, of course.) I still have no idea how to prove that this strategy, which is essentially Knuth's algorithm as it seems (I just don't quite know how minmax works), finishes in five moves or less. –  Asaf Karagila Aug 15 at 1:00
1  
The algorithm finishes in $5$ moves even if given what seemingly is the worst case scenario of $9876$. This has sufficiently few options that one can write code to test the algorithm that actually checks all possible codes against it. I am far too lazy to write it, though, sorry. :-) –  Asaf Karagila Aug 15 at 1:07

3 Answers 3

up vote 4 down vote accepted

Once you know the correct numbers it should take you at most 3 more guesses to find their positions (since any number in wrong position can be corrected in at most 3 guesses).

Also you can find the four correct numbers by guessing 1234; 5678; 9012.

So this algorithm is perhaps not the most efficient, but always gives the answer within 6 tries.

share|improve this answer
1  
You can also notice that by the second attempt you have guessed at least two amber digits and you can use that to construct the third attempt (rather than a crude $9012$) and it may save you a try. –  Asaf Karagila Aug 15 at 1:23
    
@AsafK Good idea! I like it. –  paw88789 Aug 15 at 1:28

Below algorithm guarantee that no matter which code given, you can hack the security camera in maximum of 5 moves:

It requires somewhat intelligent planning and roughly goes like this:

  1. Check your guess. If it's solution stop, otherwise continue.
  2. If there are amber (misplaced) digits, then try to find (if possible) precisely these digits' places in sequence. For example, if the digit in 4th place is amber, and this digit was already tried in 1st and 3rd place (or maybe we know digit in 3rd place), then we know precisely that its place is 2nd in the sequence. Check if it's solution. If not, try #2 again until you found all possible digits which can only come to one place. If there are no ambers go to #4.
  3. Try these amber digits in new (previously non-tried) places.
  4. Try new (previously non-tried) digits in empty places. Then go to #1 again.

There are some subtleties in this algorithm which i pointed out in the end.

Here are some examples:

  • Code: $6435$. $$\color{red}{012}\color{orange}{3}\\ \color{orange}{3}\color{green}{4}\color{orange}{56}$$ Now, digit 3, was tried in 1st and 4th place, also we know the digit in 2nd place is 4. Therefore digit 3 belongs to 3rd place. And we know the digits in 2nd and 3rd place are $43$, therefore digit 6 belongs to 1st place. There is only one place left in digit 5 and it's 4th place. $$\color{green}{6435}$$ We repeatedly use #2 to find solution.
  • Code: $9123$. $$\color{red}{0}\color{green}{123}$$ There are no ambers so try new digits. $$\color{red}{4567}\\ \color{red}{8}\color{orange}{9}**$$ It doesn't matter which digit you try in 3rd and 4th places. Now apply #2 again to get: $$\color{green}{9123}$$
  • Seemingly, one of the worst-case-scenarios is the code (Provided if we start with $1234$): $8790$ $$\color{red}{1234}\\\color{red}{56}\color{orange}{78}$$ From this point on, we can find third and fourth place at maximum of three tries. Also we can find the position of digits 7 and 8, at maximum of three tries. In order to get the most information from digits 9 and 0, we should place 87 to third and fourth place*, therefore if 0 and 9 belong to third and fourth place (worst-case), we could find them in two tries. $$\color{orange}{0987}$$ Now we know digits 7 and 8 belong to first and second place, so digits 0 and 9 belong to third and fourth place. Therefore it would take maximum of two tries to find the code: $$\color{orange}{7809}\\ \color{green}{8790}$$

*There is a subtlety here. We can't place digits randomly and try our luck. For example, if given code would be $9087$, and we try: $$\color{red}{1234}\\ \color{red}{56}\color{orange}{78}\\ \color{orange}{7809}\\ \color{orange}{8790}\\ \color{orange}{09}\color{green}{87}$$ Then we cannot get the result in five tries. In order to neglect this, we can say; "If you guess two red and two amber digits, then swap these amber digits' places if it's possible." to the algorithm.

share|improve this answer
    
Seems like you didn't read the question. –  Asaf Karagila Aug 15 at 3:24
    
@AsafKaragila Why did you say that? Question is: "What is the minimum number of attempts in order to guarantee entry to the system?" I prove (if proof is true) that minimum number of attempts is 5. –  Alistair Aug 15 at 3:30
    
"Repeated digits are not allowed" –  Asaf Karagila Aug 15 at 3:40
    
$AsafKaragila Quote: "I'm assuming digits can be same, because question only says digits can't be repetitive." I already say in my answer that, question says digits can't be repeated. This means i did read the question. In fact i also specified i can't be sure if that meant only codes like adjoining digits (like 1123), since question didn't say anything codes like same not-adjoined digits (like 1010). So i include this condition in my answer. –  Alistair Aug 15 at 3:54
    
So you willingly wrote half of a not-short answer despite knowing full well that it won't be applicable here? Also I don't understand the algorithm here. How do you choose the next guess? One particular example is not very enlightening here, since I don't know quite know how you would choose the next guess if the first guess has two amber and two green ones, and the second guess has also two amber and two green ones. What would be the result in that case? –  Asaf Karagila Aug 15 at 4:29

The constraints actually give six attempts, so while the following algorithm may fail to produce the answer in just five tries, it is still guaranteed to give it in at most six. (So far I could only find two examples of codes requiring six guesses, and I think these might be the only two.)


For each digit define its status as $u,r,a,g$ meaning untested, red, amber and green. Initially all have status $u$.

  1. Input $0123$.
  2. If all four digits have status $g$ we are finished.
  3. Remove the digits marked as $r$, and add the least digits marked with $u$.
  4. Reorder the four digits you have to the least numerical value such that the following two constraints hold:

    • No digit marked $a$ is in a place previously located.
    • Every digit marked $g$ remains in its place from last time.
  5. Input the number, and repeat.

Why are six moves enough? Once a digit appears has status $a$ it will take at most three more attempts to place it in its right place (since there are only three more places for it to go). Meaning that by the fifth step we have placed at least two digits correctly. We only have one option to continue and guess, to switch the two marked $a$.

So far all the codes I have tried to guess except $9876$ and $8976$ were broken in five attempts, because by the second guess the algorithm guaranteed to be "close" to a solution. Here are a few examples:

$$\begin{array}{c|c|c|c} \begin{array}{c|c} \text{Code:}&1980\\\hline 0123&aarr\\ 1045&garr\\ 1607&grar\\ 1890&gaag\\ 1980&gggg \end{array} & \begin{array}{c|c} \text{Code:}&6837\\\hline 0123&rrra\\ 3456&arra\\ 6378&gaaa\\ 6837&gggg\\ \vphantom{1} \end{array} & \begin{array}{c|c} \text{Code:}&3672\\\hline 0123&rraa\\ 2345&aarr\\ 3267&gaaa\\ 3672&gggg\\ \vphantom{1} \end{array} & \begin{array}{c|c} \text{Code:}&6581\\\hline 0123&rarr\\ 1456&araa\\ 5617&aaar\\ 6581&gggg\\ \vphantom{0} \end{array} \end{array}$$

Ultimately, this algorithm is simple enough, and quick enough, to merit a full check, running all possible codes against it. But I'm too lazy to write this code. If someone wants to, please post the results in a comment/separate answer!

share|improve this answer
3  
@alexqwx and Asaf: Quit it! Both of you! –  Arthur Fischer Oct 17 at 16:11
    
@ArthurFischer He started the argument. You're not gonna suspend my account again, are you? –  alexqwx Oct 17 at 16:12
3  
@alexqwx: Even if you think he started it, this doesn't permit you to respond in kind. If someone is being abusive FLAG. This site is pretty much impossible to moderate without users FLAGGING bad behaviour. (Also, if you don't want to be suspended don't act in ways that are likely to get you suspended. It's really simple.) –  Arthur Fischer Oct 17 at 16:15
    
This downvote is oddly timed. Could the downvoter explain what is wrong with the answer, except for it being unaccepted after two months of being accepted? –  Asaf Karagila Oct 18 at 22:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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