81 lines
5.4 KiB
Text
81 lines
5.4 KiB
Text
{{DISPLAYTITLE:de Bruijn sequences}}
|
|
The sequences are named after the Dutch mathematician Nicolaas Govert de Bruijn.
|
|
|
|
|
|
A note on Dutch capitalization: Nicolaas' last name is '''de Bruijn''', the '''de''' isn't normally capitalized
|
|
unless it's the first word in a sentence. Rosetta Code (more or less by default or by fiat) requires the first word in the task name to be
|
|
capitalized.
|
|
|
|
|
|
In combinatorial mathematics, a '''de Bruijn sequence''' of order <big> ''n'' </big> on
|
|
a <big> size-''k'' </big> alphabet (computer science) <big> ''A'' </big> is a cyclic sequence in which every
|
|
possible <big> length-''n'' </big> string (computer science, formal theory) on <big> ''A'' </big> occurs
|
|
exactly once as a contiguous substring.
|
|
<!--
|
|
──────────────────────────────────────────────────────────────────────────────────────────────────────────
|
|
Yeah, I know, it's a pretty big mouthful, but it's what Wikipedia uses, so I went with that definition.
|
|
──────────────────────────────────────────────────────────────────────────────────────────────────────────
|
|
!-->
|
|
|
|
Such a sequence is denoted by <big> ''B''(''k'', ''n'') </big> and has
|
|
length <big>''k''<sup>''n''</sup></big>, which is also the number of distinct substrings of
|
|
length <big>''n''</big> on <big>''A''</big>;
|
|
<br>de Bruijn sequences are therefore optimally short.
|
|
|
|
<!--
|
|
──────────────────────────────────────────────────────────────────────────────────────────────────────────
|
|
Expressing the (below) equation with a <math> HTML tag causes it to "blow up" on Rosetta Code's version.
|
|
──────────────────────────────────────────────────────────────────────────────────────────────────────────
|
|
!-->
|
|
There are:
|
|
<big><big><big>(k!)<sup>k<sup>(n-1)</sup></sup> <big><b>÷</b></big> k<sup>n</sup></big></big></big>
|
|
distinct de Bruijn sequences <big> ''B''(''k'', ''n''). </big>
|
|
|
|
|
|
;Task:
|
|
For this Rosetta Code task, a '''de Bruijn''' sequence is to be generated that can be used to shorten a brute-force attack on
|
|
a [[wp:Personal_Identification_Number|PIN]]-like code lock that does not have an "enter"
|
|
key and accepts the last <big> ''n'' </big> digits entered.
|
|
|
|
|
|
Note: [[wp:Automated_teller_machine|automated teller machines (ATMs)]] used to work like
|
|
this, but their software has been updated to not allow a brute-force attack.
|
|
|
|
|
|
;Example:
|
|
A [[wp:digital_door_lock|digital door lock]] with a 4-digit code would
|
|
have ''B'' (10, 4) solutions, with a length of '''10,000''' (digits).
|
|
|
|
Therefore, only at most '''10,000 + 3''' (as the solutions are cyclic or ''wrap-around'') presses are needed to
|
|
open the lock.
|
|
|
|
Trying all 4-digit codes separately would require '''4 × 10,000''' or '''40,000''' presses.
|
|
|
|
|
|
;Task requirements:
|
|
:* Generate a de Bruijn sequence for a 4-digit (decimal) PIN code.
|
|
:::* Show the length of the generated de Bruijn sequence.
|
|
:::* (There are many possible de Bruijn sequences that solve this task, one solution is shown on the ''discussion'' page).
|
|
:::* Show the first and last '''130''' digits of the de Bruijn sequence.
|
|
:* Verify that all four-digit (decimal) '''1,000''' PIN codes are contained within the de Bruijn sequence.
|
|
:::* 0000, 0001, 0002, 0003, ... 9996, 9997, 9998, 9999 (note the leading zeros).
|
|
:* Reverse the de Bruijn sequence.
|
|
:* Again, perform the (above) verification test.
|
|
:* Replace the 4,444<sup>th</sup> digit with a period (.) in the original de Bruijn sequence.
|
|
:::* Perform the verification test (again). There should be four PIN codes missing.
|
|
|
|
|
|
(The last requirement is to ensure that the verification tests performs correctly. The verification processes should list
|
|
any and all missing PIN codes.)
|
|
|
|
Show all output here, on this page.
|
|
|
|
{{Template:Strings}}
|
|
|
|
|
|
;References:
|
|
:* Wikipedia entry: [[wp:De_Bruijn_sequence|de Bruijn sequence]].
|
|
:* MathWorld entry: [http://mathworld.wolfram.com/deBruijnSequence.html de Bruijn sequence].
|
|
:* An OEIS entry: [[oeis:A166315|A166315 lexicographically earliest binary de Bruijn sequences, B(2,n)]] --- Not B(10,4), but possibly relevant.
|
|
<br><br>
|
|
|