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 n on
a size-k alphabet (computer science) A is a cyclic sequence in which every
possible length-n string (computer science, formal theory) on A occurs
exactly once as a contiguous substring.
Such a sequence is denoted by B(k, n) and has
length kn, which is also the number of distinct substrings of
length n on A;
de Bruijn sequences are therefore optimally short.
There are:
(k!)k(n-1) ÷ kn
distinct de Bruijn sequences B(k, n).
- 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 PIN-like code lock that does not have an "enter" key and accepts the last n digits entered.
Note: automated tell machines (ATMs) used to work like
this, but their software has been updated to not allow a brute-force attack.
- Example
A 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,444th digit with a period (.) in the original de Bruijn sequence.
- Perform the verification test (again). There should be several 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.
- References
-
- Wikipedia entry: de Bruijn sequence.
- MathWorld entry: de Bruijn sequence.
- An OEIS entry: A166315 lexicographically earliest binary de Bruijn sequences, B(2,n) --- Not B(10,4), but possibly relevant.
REXX
The de Bruijn sequence generated by these REXX programs are identical to the sequence shown on the discussion page (1st topic).
hard-coded node to be removed
<lang rexx>/*REXX pgm calculates the de Bruijn sequence for all pin numbers (4 digit decimals). */ $= /*initialize the de Bruijn sequence. */
- =10; lastNode= (#-2)(#-2)(#-1)(#-2) /*this number is formed when this # ···*/
/* ··· is skipped near the cycle end. */ do j=0 for 10; $= $ || j; jj= j || j /*compose the left half of the numbers.*/ /* [↓] " right " " " " */ do k=jj+1 to 99; z= jj || right(k, 2, 0) if z==lastNode then iterate /*the last node skipped.*/ if pos(z, $)\==0 then iterate /*# in sequence? Skip it*/ $= $ || z /* ◄─────────────────────────────────┐ */ end /*k*/ /*append a number to the sequence──◄─┘ */
do r= jj to (j || 9); b= right(r, 2, 0) /*compose the left half of the numbers.*/ if b==jj then iterate $= $ || right(b, 2, 0) /* [↓] " right " " " " */ do k= b+1 to 99; z= right(b, 2, 0) || right(k, 2, 0) if pos(z, $)\==0 then iterate /*# in sequence? Skip it*/ $= $ || z /* ◄─────────────────────────────────┐ */ end /*k*/ /*append a number to the sequence──◄─┘ */ end /*r*/ end /*j*/ @deB= 'de Bruijn sequence' /*literal used in some SAY instructions*/
$= $ || left($, 3) /*append 000*/ /*simulate "wrap-around" de Bruijn seq.*/
say 'length of the' @deB " is " length($) /*display the length of de Bruijn seq.*/
say; say 'first 130 digits of the' @deB":" /*display the title for the next line. */
say left($, 130) /*display 130 left-most digits of seq. */
say; say ' last 130 digits of the' @deB":" /*display the title for the next line. */
say right($, 130) /*display 130 right-most digits of seq.*/
say /*display a blank line. */ call val $ /*call the VAL sub for verification. */
@deB= 'reversed' @deB /*next, we'll check on a reversed seq.*/
$$= reverse($) /*do what a mirror does, reversify it.*/ call val $$ /*call the VAL sub for verification. */ $= overlay(., $, 4444) /*replace 4,444th digit with a period. */
@deB= 'overlaid' subword(@deB, 2) /* [↑] this'll cause a validation barf.*/
call val $ /*call the VAL sub for verification. */ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ val: parse arg $$$; e= 0; _= copies('─',8) /*count of errors (missing PINs) so far*/
say; say _ 'validating the' @deB"." /*display what's happening in the pgm. */ do pin=0 for 1e4; pin4= right(pin,4,0) /* [↓] maybe add leading zeros to pin.*/ if pos(pin4, $$$)\==0 then iterate /*Was number found? Just as expected. */ say 'PIN number ' pin " wasn't found in" @deb'.' e= e + 1 /*bump the counter for number of errors*/ end /*pin*/ /* [↑] validate all 10,000 pin numbers*/ if e==0 then e= 'No' /*Gooder English (sic) the error count.*/ say _ e 'errors found.' /*display the number of errors found. */ return</lang>
- output:
length of the de Bruijn sequence is 10003 first 130 digits of the de Bruijn sequence: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 last 130 digits of the de Bruijn sequence: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 ──────── validating the de Bruijn sequence. ──────── No errors found. ──────── validating the reversed de Bruijn sequence. ──────── No errors found. ──────── validating the overlaid de Bruijn sequence. PIN number 1459 wasn't found in overlaid de Bruijn sequence. PIN number 4591 wasn't found in overlaid de Bruijn sequence. PIN number 5814 wasn't found in overlaid de Bruijn sequence. PIN number 8145 wasn't found in overlaid de Bruijn sequence. ──────── 4 errors found.
programmatically removing of a node
Programming note: instead of hardcoding the lastNode (that is elided from the sequence), the 5th to the last node could simply be deleted.
This method slightly bloats the program and slows execution. <lang rexx>/*REXX pgm calculates the de Bruijn sequence for all pin numbers (4 digit decimals). */ $= /*initialize the de Bruijn sequence. */
/* ··· is skipped near the cycle end. */ do j=0 for 10; $= $ j; jj= j || j /*compose the left half of the numbers.*/ $$= space($, 0) /* [↓] " right " " " " */ do k=jj+1 to 99; z= jj || right(k, 2, 0) if pos(z, $$)\==0 then iterate /*# in sequence? Skip it*/ $= $ z /* ◄─────────────────────────────────┐ */ end /*k*/ /*append a number to the sequence──◄─┘ */ $$= space($, 0) do r= jj to (j || 9); b= right(r, 2, 0) /*compose the left half of the numbers.*/ if b==jj then iterate $= $ right(b, 2, 0) /* [↓] " right " " " " */ $$= space($, 0); do k= b+1 to 99; z= right(b, 2, 0) || right(k, 2, 0) if pos(z, $$)\==0 then iterate /*# in sequence? Skip it*/ $= $ z /* ◄─────────────────────────────────┐ */ end /*k*/ /*append a number to the sequence──◄─┘ */ $$= space($, 0) end /*r*/ end /*j*/
$= delword($, words($)-4, 1) /*delete 5th from the last word in $. */ $= space($, 0)
@deB= 'de Bruijn sequence' /*literal used in some SAY instructions*/
$= $ || left($, 3) /*append 000*/ /*simulate "wrap-around" de Bruijn seq.*/
say 'length of the' @deB " is " length($) /*display the length of de Bruijn seq.*/
say; say 'first 130 digits of the' @deB":" /*display the title for the next line. */
say left($, 130) /*display 130 left-most digits of seq. */
say; say ' last 130 digits of the' @deB":" /*display the title for the next line. */
say right($, 130) /*display 130 right-most digits of seq.*/
call val $ /*call the VAL sub for verification. */
@deB= 'reversed' @deB /*next, we'll check on a reversed seq.*/
$r= reverse($) /*do what a mirror does, reversify it.*/ call val $r /*call the VAL sub for verification. */ $= overlay(., $, 4444) /*replace 4,444th digit with a period. */
@deB= 'overlaid' subword(@deB, 2) /* [↑] this'll cause a validation barf.*/
call val $ /*call the VAL sub for verification. */ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ val: parse arg $$$; e= 0; _= copies('─',8) /*count of errors (missing PINs) so far*/
say; say _ 'validating the' @deB"." /*display what's happening in the pgm. */ do pin=0 for 1e4; pin4= right(pin,4,0) /* [↓] maybe add leading zeros to pin.*/ if pos(pin4, $$$)\==0 then iterate /*Was number found? Just as expected. */ say 'PIN number ' pin " wasn't found in" @deb'.' e= e + 1 /*bump the counter for number of errors*/ end /*pin*/ /* [↑] validate all 10,000 pin numbers*/ if e==0 then e= 'No' /*Gooder English (sic) the error count.*/ say _ e 'errors found.' /*display the number of errors found. */ return</lang>
- output is identical to the 1st REXX version.