Knäcka ett kodlås utan OK-knapp

1. $\underset{n=1}{\overset{4}{\sum n!}}$ = 33 tryck (123412314231243121342132413214321)

Angående tvåan:

Det finns ju totalt $10\ 000$ koder, så om man antar att vi kan hitta en siffersekvens som innehåller varje fyrsiffrig kod bara en gång (man har alltså inga dubbletter) borde denna vara den kortaste sekvensen. En sådan sekvens skulle ha längden $10\ 003$ siffror eftersom den ska innehålla $10\ 000$ separata fyrsiffriga koder.

En optimal sekvens skulle alltså innehålla $10\ 003$ siffror. Frågan är om en sådan sekvens existerar. Efter att ha skrivit ett ganska klumpigt brute-force-program i Java har jag kommit fram till att svaret är ja:

    private static int presentCombinations = 1;
    private static StringBuilder string = new StringBuilder("9999");

    private static void createString() {
        while (presentCombinations < 10000) {
            for (int i = 0; i <= 9; i++) {
                if (!string.toString().contains(string.substring(string.length() - 3) + i)) {
                    string.append(i);
                    presentCombinations++;
                    break;
                }
            }
        }
        System.out.println(string);
    }

Här är sekvensen som jag genererade:

https://hastebin.com/ezobecuxiz

Det intressanta är att det verkar finnas väldigt många sådana här optimala sekvenser. Hyfsat många starttal (jag har valt 9999 i koden ovan) ger en giltig sekvens, och om man hade en bättre kod (min fastnar i en oändlig loop på vissa tal) tror jag att det går att generera minst en sekvens för varje starttal.

I syfte att förankra det hela lite mer matematiskt fann jag att en sådan här optimal sekvens verkar vara en de Bruijn-sekvens av ordning $4$ med alfabetslängd $10$, $B(10, 4)$. Enda skillnaden är att längden på en de Bruijn-sekvens är $10\ 000$ siffror eftersom man "kopplar ihop" början och slutet av sekvensen, så man tillåts bilda en delsekvens av t.ex. de sista två och första två siffrorna, men det kan ju inte vi göra med vårt kodlås, och då får vi kopiera de tre första siffrorna och lägga dem i slutet så att vi inkluderar alla kombinationer, därav längden $10\ 003$.

Enligt Wikipedias formel finns det

$\displaystyle \frac{(10!)^{10^3}}{10^4}\approx 5,79 \cdot 10^{6555}$

olika $B(10,4)$-sekvenser.

Angående ettan:

Skrev och sparade ett Python-program i GitHub som skapar optimala sekvenser av knapptryck för olika längder på koden till låset. Kan användas med andra symboler än siffror.

Med en hygglig dator blir exekveringstiden bråkdelar av en sekund för kodlängder under 8. Exekveringstiden ökar dock exponentiellt så för längder över 10 kan man få vänta en god stund. Kan troligen optimeras med avseende på exekveringstid.

Ursäktar att jag tydligen aldrig kom tillbaka och gratulerade till lösningarna men påmindes av att dagens Veritasium involverade tydligen en variant på detta problem

https://www.youtube.com/watch?v=CNodxp9Jy4A