Hacking an electronic keypad

Question

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?

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

Answer 1

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.

Answer 2

My most sincere apologies for this. Really.

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

Answer 3

I can do it in

33 presses

A possible combination:

179017910791709171907197019710971

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

Answer 4

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 graph-theory 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.

Answer 5

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

Answer 6

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.

Answer 7

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.