Minimum number of attempts to guess a PIN code, given constraints
By James Williams
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).
$\endgroup$ 133 Answers
$\begingroup$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.
$\endgroup$ 2 $\begingroup$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:
- Check your guess. If it's solution stop, otherwise continue.
- 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.
- Try these amber digits in new (previously non-tried) places.
- 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.
$\endgroup$ 8 $\begingroup$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$.
- Input $0123$.
- If all four digits have status $g$ we are finished.
- Remove the digits marked as $r$, and add the least digits marked with $u$.
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.
- 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!
$\endgroup$ 4
