23
$\begingroup$

You are a spy trying to break into an enemy facility. The back door is protected by an electronic keypad lock. You know that this particular lock is opened by a four digit code. Any stream of button presses which contains the correct code consecutively will open the lock. For example, if the code was 1234, you could open the lock by pressing 911234 or 1237121234.

Unfortunately, you do not know the code. It would take a long time to punch in all 10,000 possible codes.

Fortunately, when you reach the lock, you notice that the buttons numbered 1, 7, 9 and 0 are worn down from repeated use...

With this extra information, at least how many button presses does it take to open the lock in the worst case?

Picture of an electronic keypad with the numbers 0, 1, 7 and 9 looking especially worn down

Image taken from https://redd.it/1kvb9u

$\endgroup$
  • 7
    $\begingroup$ In the worst case, would the answer not be infinite? I could keep pressing the same button over and over again until I feel like trying all the 24 permutations of 1,7,9 and 0. $\endgroup$ – A.B. Mar 22 '18 at 13:34
  • 2
    $\begingroup$ Possible duplicate of One beer too many $\endgroup$ – Quintec Mar 22 '18 at 19:36
  • 1
    $\begingroup$ @thecoder16 It is not a duplicate of that older question (in fact it even links to it already) as in this question the digits used are already known. You made the same mistake as Apep and w l above. $\endgroup$ – Jaap Scherphuis Mar 22 '18 at 20:58
  • 4
    $\begingroup$ 4 presses: 1970. Everyone knows that everyone else's 4-digit pascode must be their birth year. $\endgroup$ – user253751 Mar 23 '18 at 5:09
  • 2
    $\begingroup$ @JaapScherphuis I mean, in both cases the answer is "find the De Brujin sequence". (Except for Bass's lateral-thinking answer.) $\endgroup$ – Nic Hartley Mar 23 '18 at 5:30
19
$\begingroup$

As atonement for my insolent lateral-thinking answer, I offer an optimality proof.

If you keep repeating the correct code, the are six possible different orders:

1 abcdabcdabcd
2 abdcabdcabdc
3 acbdacbdacbd
4 acdbacdbacdb
5 adbcadbcadbc
6 adcbadcbadcb

Each of the orders contains four possible codes. The orders are important, since after testing one code in the order, the other three can be tested with only one keypress each.

After testing all codes in one order, we need to waste at least one keypress (guaranteed to not open the lock because of a duplicated digit) to switch to another one. The first 3 keypresses won’t open the lock either, so we need to waste at least 8 keypresses, for a lower bound of 32 keypresses. (There are 24 possible codes, and each requires one keypress to test)

Let’s see if we cannot find an answer that wastes only one press between the orders:

  1 abcDABCa
  5      bcaDBCAb
  2           cabDCABc
  1                abcd

Oops. Every order uniquely defines, which order can follow it with only only one wasted keypress in between. That ”order of orders” has a loop after 3 orders, so we need to waste at least one more keypress to get to the remaining orders. That brings the lower bound to 33.

Such answers have already been posted, so this proves that they are optimal.


EDIT: (bug found and fixed)

Here's also my attempt at a general solution. Again, the capitalised keypresses are the ones that introduce a previously untried possible combination, the lowercase keypresses are the wasted ones.

  1 abc-DABC-a
  5      (bc a)DBCA-b
  2             (ca b)DCAB-ac
  4                     (b ac)DBAC-b
  3                            (ac b)DACB-a
  6                                   (cb a)DCBA
or: abcDABCaDBCAbDCABacDBACbDACBaDCBA

In the middle, when choosing the two consecutive digits to waste, we can try to waste another pair of keypresses instead of "ac". That spot is highlighted above, and it's the first place where you actually get to choose anything. We can pick order 3 or 6 instead of order 4 as the fourth one. We can do that by choosing "da" or "ad" as the wasted presses. (Those are the only other choices, since we have to "reuse" the B from the earlier bit). However, those choices lead to unexpected disaster:

  attempt 1-5-2-4-3-6: abcDABCaDBCAbDCABacDBACbDACBaDCBA
  attempt 1-5-2-3-1-2: abcDABCaDBCAbDCABdaCBDAbCDABdCABD
  attempt 1-5-2-6-5-3: abcDABCaDBCAbDCABadCBADbCADBaCDBA

We get unexpected repeats on the order level.

Since we have not used any properties of the orderings whatsoever, everything must be perfectly symmetric, so we can deduce that the unique follower of an order, and consequently the three orderings involved in the resulting loop, will depend on which letter we started with. Observing this, and noticing that our every choice is forced by the fact that any other choice would cause us to waste another keypress, the only way to construct the two loops (of three orders each) so that every order gets included, is 1-5-2-4-3-6. That results in the string abcDABCaDBCAbDCABacDBACbDACBaDCBA.

Since we can arbitrarily assign the digits 0,1,7 and 9 to the letters, there will be 24 different 33-digit strings that are guaranteed to open the lock, all following the exact pattern given above.

Double checking with the other answers, found by Jaap Scherphuis and w l, (they happen to use the exact same string) we notice that the answer does indeed follow this pattern.

179017910791709171907197019710971 
abcDABCaDBCAbDCABacDBACbDACBaDCBA

(Afterthought: It is a beautiful testament to the many symmetries in this puzzle, that all the possible solutions are palindromes.)

Post Scriptum: having finished this answer, I managed to look up more information on it. For further reference, this problem type is known as "minimal superpermutation", and for 4 distinct symbols, the answer is indeed unique, as long as we are allowed to relabel the symbols.

$\endgroup$
  • $\begingroup$ Nicely explained! I wish I could award the checkmark to two different answers. $\endgroup$ – Mike Earnest Mar 22 '18 at 16:53
47
$\begingroup$

My most sincere apologies for this. Really.

None. The light is green, the lock is already open.

$\endgroup$
  • 6
    $\begingroup$ Unless green means that the door is locked but the poisonous gas has not yet been released due to an incorrect password. $\endgroup$ – Engineer Toast Mar 22 '18 at 16:41
  • 3
    $\begingroup$ Related: interpersonal.stackexchange.com/questions/12115 $\endgroup$ – user253751 Mar 23 '18 at 6:29
  • $\begingroup$ Cue the incoming mod wielding a wet blanket. :) I love this, but ... $\endgroup$ – Rubio Mar 23 '18 at 13:42
7
$\begingroup$

I can do it in

33 presses

A possible combination:

179017910791709171907197019710971

The number of presses appears to be $\sum_{k=1}^{n}{k!}$

$\endgroup$
  • 3
    $\begingroup$ The pattern of this sequence is A180632 in the Online Encyclopedia of Integer Sequences, which follows your pattern for $n=1,2,3,4,5$. However, it is not known how the pattern continues for $n > 5$, but it is strictly less than the pattern you suggests (according to the OEIS entry, at least). $\endgroup$ – Frxstrem Mar 22 '18 at 20:08
  • $\begingroup$ Seems right to me, but I would prefer to see a practical reasoning to get a full sequence of buttons pressed. Something like: write all the possible combinations, then start with one combination and try to attach an unrepeated combination that starts with the last previously pressed buttons. If it's not possible, try to continue with a combination that starts with the last pressed buttons. $\endgroup$ – cinico Mar 23 '18 at 11:15
7
$\begingroup$

My best solution has

$33$

button presses.

Consider the sequence $abcdabc$. This tests the 4 combinations that are cyclic rearrangements of $abcd$.
Every code can be cyclically rearranged to start with the $1$, so you now only have to apply the above sequence to the six possibilities that start with $a=1$.
This gives: $1790179\ 1709170\ 1970197\ 1907190\ 1079107\ 1097109$

It has $42$ presses but can be improved to $33$ button presses. By cyclically rearranging each of the 6 sequences (i.e. using any of the equivalent sequences $abcdabc$, $bcdabcd$, $cdabcda$, $dabcdab$), they can be made to overlap:
$17901(79)107(91)7091(7)1907(19)701(97)10971$
This saves $9$ presses so has length $42-9=33$

I notice that the question has the tag. This suggest that there is a graph-based method to solve it.

You can make a graph with 24 nodes, where each node represents one of the 4-digit sequences you need to try. Connect every pair of nodes with two directed edges, one in each direction. Each directed edge is given a weight that is equal to $4$ minus the amount you can save by having the two sequences overlap. For example the edge from $abcd$ to $bcda$ would have a weight of $4-3=1$ because you can combine them as $abcda$.
You now have to find a path through this graph that visits every node. This path gives you the order in which you try out the combinations. The total number of button presses you need is equal to the sum of the weights of all the edges you traverse, plus another $4$ presses for the final node you land on.
This has turn this problem into an instance of the Travelling Salesman Problem.

$\endgroup$
  • $\begingroup$ The question asks for the worst case though. $\endgroup$ – moopet Mar 22 '18 at 14:07
  • 2
    $\begingroup$ @moopet: The worst case is when the code happens to be the last one in the sequence you try. It is asking for the shortest sequence, so that the worst case won't be too bad. $\endgroup$ – Jaap Scherphuis Mar 22 '18 at 14:09
  • $\begingroup$ @Saeïdryl Thanks. I messed up the cyclic rearrangement of the sub-sequences. It's fixed now, but still the same length. $\endgroup$ – Jaap Scherphuis Mar 22 '18 at 15:35
  • $\begingroup$ @JaapScherphuis I hadn't checkyour combination entirely , so I thought you could just remove it, but I'm sure I saw another answer with 32 presses that I checked at 100%, so I think it's doable in 32 $\endgroup$ – Saeïdryl Mar 22 '18 at 15:47
  • $\begingroup$ I don't think 32 is possible. The answer posted that claimed 32 moves described a way of building the sequence that didn't quite work, and turned out to be equivalent to mine and that of w-l. You can't join together the 6 sub-sequences with 2 digits of overlap every time. $\endgroup$ – Jaap Scherphuis Mar 22 '18 at 15:53
2
$\begingroup$

I think the answer is 35 key presses. For a four digit number that does not change its order we need 7 key presses for all 4 combinations. So based on that if we follow the following key sequences we will get all the possibilities.

 17901 79 107 91 7091 7 01970 1 90719 0 971097 . 
 i.e   1790179 for first sequence 
 then  7910791 for the next and 
       9170917 for the next and so on
$\endgroup$
0
$\begingroup$

Twenty-Four

The first number is clearly 0 as the number is most faded of the four, and the first press would absorb the most oil off of the legitimate user's finger. The 1 is most likely the second or fourth number as it is the second most worn which could also be from finger oil, or extra confidence from the final press. As such I'd try 0179 0791 0197 0971 0719 0917 with fair confidence in that order.

$\endgroup$
  • 1
    $\begingroup$ That's 24 button presses, not 6. $\endgroup$ – Frxstrem Mar 22 '18 at 20:10
  • $\begingroup$ Indeed you are correct, "knowing" the first digit does preclude a De Bruijn sequence though. $\endgroup$ – aslum Mar 22 '18 at 20:21
-1
$\begingroup$

256: There are four digits in the code, and four possibilities for each digit. To achieve every combination of those four digits, including repeats (e.g., 0000) requires 4*4*4*4=256 button presses.

$\endgroup$
  • 3
    $\begingroup$ There should not be repeats, as using one button twice means on of the others isn't pressed in the 4 digit combination, so it wouldn't be worn. Thus all digits must be used in the passcode $\endgroup$ – Fifth_H0r5eman Mar 22 '18 at 14:00
  • 1
    $\begingroup$ Note that you can type a stream of numbers consecutively, so you can actually perform two tries with only 5 digits (i.e. 17901 is 1790 and 7901) and three tries with 6 digits, etc. $\endgroup$ – Rick van Osta Mar 22 '18 at 14:00
  • $\begingroup$ @Fifth_H0r5eman - The buttons as shown do not appear to be worn evenly, implying that they're not used evenly. Given that, I can't be sure that all four are used in the code; only that those four seem to be used for entering the code, and at least one of them must be in the code. I agree that it's likely that all four are in the code, but querent is asking for "worst case". $\endgroup$ – Jeff Zeitlin Mar 22 '18 at 14:03
  • $\begingroup$ If 4 buttons are used in a 4 digit code, they must be used evenly though, unless you mean to say that other uses repeatedly press a button that is not required? $\endgroup$ – Fifth_H0r5eman Mar 22 '18 at 14:07
  • 1
    $\begingroup$ The passcode is 4 digits long, and includes 4 distinct digits. The B(4,4) De Bruijn sequence you propose is far longer than required, since it includes many passcodes that you can rule out, such as "1799". $\endgroup$ – Mark Mar 23 '18 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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