Bruteforcing a keypad lock

A particular lock at my university has a keypad with the digits 1-5 on it. When pressed in the correct permutation of those five digits, the lock will open.

Obviously, since there are only 120 permutations, we can bruteforce the lock in 600 presses. But we can do better! The sequence 1234512 actually tests three distinct sequences with only seven presses - 12345, 23451, and 34512.

What's the fastest strategy to bruteforce this lock?

(and for bonus points, other locks with more numbers, longer passcodes, etc.)

(I've taken a few stabs at this problem with no progress to speak of - particularly, De Bruijn sequences are not directly relevant here)

We want to find a word over the alphabet $\{1,\ldots,n\}$ that is as short as possible and contains all $n!$ permutations of the alphabet as infixes. Let $\ell_n$ denote the shortest achievable length. Clearly, $$\tag1\ell_n\ge n!+(n-1).$$ Of course, $(1)$ is somewhat optimistic because it requires $(n-1)$-overlaps between all consecutive permutations, but that is only possible for cyclicly equivalent permutations. As there are $(n-1)!$ equivalence classes under cyclic equivalence, and switching between these requires us to "waste" a symbol, we find that $$\tag2\ell_n\ge n!+(n-1)+(n-1)!-1=n!+(n-1)!+(n-2).$$ In particular, inequality $(2)$ is sharp for the first few cases $\ell_1=1$, $\ell_2=3$ (from "121"), $\ell_3=9$ (from "312313213"). However, it seems that that $\ell_4=33$ (from "314231432143124313421341234132413").

Feeding these few values into the OEIS search engine reveals http://oeis.org/A180632 and we see that the exact values seem to be known only up to $\ell_5=153$ (which is your original problem)! Quoting the known bounds from there, we have $$ \ell_n\ge n! + (n-1)! + (n-2)! + n-3$$ (which can supposedly be shown similarly to how we found ($2)$ above) and $$\ell_n\le \sum_{k=1}^nk!.$$ These bounds tell us that $152\le l_5\le 153$, but it has been shown in 2014 that in fact $\ell_5=153$. The next case seems to be still open: The inequalities only tell us $867\le \ell_6\le 873$, but another result of 2014 shows that $\ell_6\le 872$.

Hagen von Eitzen’s answer reports the state of the art. Since in the given link there is no example of the eight distinct $\ell_5$-character long solutions, here is one. I computed it with a simple python program. It is also found in the paper of Aug. 22, 2014 [arXiv] where Robin Houston exhibits his candidate for a minimal superpermutation of 6 symbols.

1234512341 5234125341 2354123145 2314253142 3514231542 
3124531243 5124315243 1254312134 5213425134 2153421354
2132451324 1532413524 1325413214 5321435214 3251432154
321

Edited: Prompted by the OP, I decided to post my python 2 code. It’s a quick-and-dirty script and no example of well written code. It can be improved and optimized in a zillion ways, but it works. I wouldn’t post it to a programming site, but here we are wearing a mathematician’s hat...

The basic idea is to grow our superpermutation step by step. We start from 12345 and at each step we identify the longest tail which could provide a permutation still unused. For example, at the second step we identify 2345, upon which we find 23451 as the next permutation, and we add 1 to our result, so that now we have 123451. Continuing in this way we find a first whole orbit of cyclic permutations at 123451234. After that, we have to add two characters, since the next permutation can only be 23415, and our growing result becomes 12345123415. We will have junctures where we have so few possible overlapping characters that we can choose between different new permutations (that’s why there are eight distinct optimal solutions). In this case I order the possible candidates lexicographically and choose the first. When there are no more available permutations, the program exits. This yields optimal results if the alphabet is up to five characters long. With six characters, my program yields a superpermutation of 873 characters, which was conjectured optimal before Houston’s paper. My program works with alphabets of arbitrary length (if given enough time to run ;-) ) but, as Houston proved, its result won’t be optimal. Houston arrived at his shorter superpermutation using a heuristic solver of operations research problems.

#!/usr/bin/python
# -*- coding: utf-8 -*-

## Change this if you want a step-by-step output
verbose = False

## The alphabet. Also, the first permutation dealt with,
## which defines lexicographic ordering for subsequent choices.
A = '12345'

N = len(A)

## The result string is initialized with the alphabet itself.
R = A

## A dictionary to keep track of the found permutations.
Done = { A: True }

# The basic iteration step.
def process():
    global R, Done
    # t represents how many characters we need to add.
    # First we try with one, then we increase...
    for t in range(1,N):
        # h is the initial stub (the “head”) of our new permutation.
        h=R[t-N:]
        while len(h) < N:
            # A crude way to find the characters still missing from 
            # the new permutation we are building.
            for c in [ x for x in A if x not in h ]:
                h += c
                break
        if h not in Done:
            # Found new permutation, update globals and return it.
            Done[h] = True
            R += h[-t:]
            return h
    # All possible permutations found!
    return ''

p = A
while p != '':
    if verbose:
        print 'found', p
    p = process()

print R
print len(R), 'bytes for', len(Done.keys()), 'permutations of', N, 'objects'

Bruteforcing a keypad lock

Related

Recent Posts