combinatorics - Hacking an electronic keypad

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

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.