4 svar
470 visningar
SeriousCephalopod är nöjd med hjälpen!
SeriousCephalopod 1783
Postad: 2 jun 2018 Redigerad: 2 jun 2018

Knäcka ett kodlås utan OK-knapp

Låt säga att du vill knäcka ett sifferkodlås där du vet att det är en fyr-siffrig kod bestående av siffrorna 1,2,3,4 (säg för att de är utnötta på knappsatsen). Om låset är sådant att man måste slå in koden och därefter trycka OK för att läsa av det hela så måste man slå in 4!=24 st olika koder

1234, 1243, 1423, 4123, 1324, 1342, 1432, 4132, 3124, 3142, 3412, 4312, 2134, 2143, 2413, 4213, 2314, 2341, 2431, 4231, 3214, 3241, 3421, 4321

vilket kan kräva upp till 4*4! = 96 sifferknapptryck och och 4!  = 24 OK-tryck vilket man inte har tid för som inbrottstjuv. Om kodlåset däremot är av typen där man kan kontinuerligt kan slå in siffor tills dess att de 4 senaste man slagit in motsvarar koden så är det en bättre strategi att kontinuerligt slå in strängen av siffor

123412312431241324132134213414231421432143 (42 tryck),  eller ännu bättre

1234123142312431241324134213432143 (34 tryck)

då alla permutationer av 1234 dyker upp någonstans i sekvenserna.

Två frågor:

1. Är 34 tryck det maximala antalet knapptryck som krävs för att med säkerhet knäcka låset ovan?

2. Om man stöter på ett 4-siffrigt kodlås med 0-9 utan några nötta knappar och du vill knäcka koden så snabbt som möjligt genom att mata in sekvens som innehåller alla möjliga koder. Hur många knapptryck skulle man behöva då?

(Jag har inte löst dessa fullständigt utan har endast uppskattningar så så kanske är onödigt svårt)

Lindehaven 206
Postad: 15 jun 2018 Redigerad: 15 jun 2018
  1. n!n=14 = 33 tryck (123412314231243121342132413214321)
AlvinB 3043
Postad: 16 jun 2018 Redigerad: 16 jun 2018

Angående tvåan:

Det finns ju totalt 10 00010\ 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 00310\ 003 siffror eftersom den ska innehålla 10 00010\ 000 separata fyrsiffriga koder.

En optimal sekvens skulle alltså innehålla 10 00310\ 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 44 med alfabetslängd 1010, B(10,4)B(10, 4). Enda skillnaden är att längden på en de Bruijn-sekvens är 10 00010\ 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 00310\ 003.

Enligt Wikipedias formel finns det

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

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

Lindehaven 206
Postad: 19 jun 2018

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.

SeriousCephalopod 1783
Postad: 19 sep 2018 Redigerad: 19 sep 2018

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

Svara Avbryt
Close