De Bruijn sequences: Difference between revisions
Thundergnat (talk | contribs) m →{{header|Perl 6}}: Fix off-by-one error. Thanks Purefox! |
m →{{header|zkl}}: minor rewrite |
||
Line 434: | Line 434: | ||
chk:=Dictionary(); |
chk:=Dictionary(); |
||
foreach n in ([0..seqText.len()-1]){ chk[seqText[n,4]]=True } |
foreach n in ([0..seqText.len()-1]){ chk[seqText[n,4]]=True } |
||
(9999).pump(List,"%04d".fmt,'wrap(k){ if(chk.holds(k)) Void.Skip else k }) |
|||
foreach n in ([0..9999]){ |
|||
k:="%04d".fmt(n); |
|||
if(not chk.find(k)) print(k," ") |
|||
} |
|||
println(); |
|||
} |
} |
||
println("\nMissing 4 digit PINs in this sequence:"); |
println("\nMissing 4 digit PINs in this sequence: ", chk(seqText).concat(" ")); |
||
⚫ | |||
chk(seqText); |
|||
⚫ | |||
chk(seqText.reverse()); |
|||
println("\n4444th character in the sequence: ", seqText[4444]); |
println("\n4444th character in the sequence: ", seqText[4444]); |
||
println("Adding 1 to the 4444th character and reruning checks:"); |
|||
dbSeq[4444]+=1; |
dbSeq[4444]+=1; |
||
chk(dbSeq.text);</lang> |
println("Adding 1 to the 4444th character and reruning checks: ",chk(dbSeq.text).concat(" "));</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 459: | Line 452: | ||
6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 |
6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 |
||
Missing 4 digit PINs in this sequence: |
Missing 4 digit PINs in this sequence: |
||
⚫ | |||
⚫ | |||
4444th character in the sequence: 5 |
4444th character in the sequence: 5 |
||
Adding 1 to the 4444th character and reruning checks: |
Adding 1 to the 4444th character and reruning checks: 1459 4591 5914 8145 |
||
1459 4591 5914 8145 |
|||
</pre> |
</pre> |
Revision as of 23:57, 1 September 2019
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.
Go
<lang go>package main
import (
"bytes" "fmt" "strconv" "strings"
)
const digits = "0123456789"
func deBruijn(k, n int) string {
alphabet := digits[0:k] a := make([]byte, k*n) var seq []byte var db func(int, int) // recursive closure db = func(t, p int) { if t > n { if n%p == 0 { seq = append(seq, a[1:p+1]...) } } else { a[t] = a[t-p] db(t+1, p) for j := int(a[t-p] + 1); j < k; j++ { a[t] = byte(j) db(t+1, t) } } } db(1, 1) var buf bytes.Buffer for _, i := range seq { buf.WriteByte(alphabet[i]) } b := buf.String() return b + b[0:n-1] // as cyclic append first (n-1) digits
}
func allDigits(s string) bool {
for _, b := range s { if b < '0' || b > '9' { return false } } return true
}
func validate(db string) {
le := len(db) found := make([]int, 10000) var errs []string // Check all strings of 4 consecutive digits within 'db' // to see if all 10,000 combinations occur without duplication. for i := 0; i < le-3; i++ { s := db[i : i+4] if allDigits(s) { n, _ := strconv.Atoi(s) found[n]++ } } for i := 0; i < 10000; i++ { if found[i] == 0 { errs = append(errs, fmt.Sprintf(" PIN number %04d missing", i)) } else if found[i] > 1 { errs = append(errs, fmt.Sprintf(" PIN number %04d occurs %d times", i, found[i])) } } lerr := len(errs) if lerr == 0 { fmt.Println(" No errors found") } else { pl := "s" if lerr == 1 { pl = "" } fmt.Printf(" %d error%s found:\n", lerr, pl) fmt.Println(strings.Join(errs, "\n")) }
}
func reverse(s string) string {
bytes := []byte(s) for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 { bytes[i], bytes[j] = bytes[j], bytes[i] } return string(bytes)
}
func main() {
db := deBruijn(10, 4) le := len(db) fmt.Println("The length of the de Bruijn sequence is", le) fmt.Println("\nThe first 130 digits of the de Bruijn sequence are:") fmt.Println(db[0:130]) fmt.Println("\nThe last 130 digits of the de Bruijn sequence are:") fmt.Println(db[le-130:]) fmt.Println("\nValidating the de Bruijn sequence:") validate(db)
fmt.Println("\nValidating the reversed de Bruijn sequence:") dbr := reverse(db) validate(dbr)
bytes := []byte(db) bytes[4443] = '.' db = string(bytes) fmt.Println("\nValidating the overlaid de Bruijn sequence:") validate(db)
}</lang>
- Output:
The length of the de Bruijn sequence is 10003 The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 The last 130 digits of the de Bruijn sequence are: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 Validating the de Bruijn sequence: No errors found Validating the reversed de Bruijn sequence: No errors found Validating the overlaid de Bruijn sequence: 4 errors found: PIN number 1459 missing PIN number 4591 missing PIN number 5814 missing PIN number 8145 missing
Perl 6
<lang perl6># Generate the sequence my $seq;
for ^100 {
my $a = .fmt: '%02d'; next if $a.substr(1,1) < $a.substr(0,1); $seq ~= ($a.substr(0,1) == $a.substr(1,1)) ?? $a.substr(0,1) !! $a; for +$a ^.. 99 { next if .fmt('%02d').substr(1,1) <= $a.substr(0,1); $seq ~= sprintf "%s%02d", $a, $_ ; }
} $seq ~= '000';
- The Task
put "de Bruijn sequence length: " ~ $seq.chars;
put "\nFirst 130 characters:\n" ~ $seq.substr( 0, 130 );
put "\nLast 130 characters:\n" ~ $seq.substr( * - 130 );
my %chk1;
for ^($seq.chars) { %chk1{$seq.substr( $_, 4 )}++ }
put "\nMissing 4 digit PINs in this sequence:"; for 0..9999 { .fmt('%04d').say unless %chk1{ .fmt: '%04d'} }
my $rev-seq = $seq.flip;
my %chk2;
for ^($rev-seq.chars) { %chk2{$rev-seq.substr( $_, 4 )}++ }
put "\nMissing 4 digit PINs in the reversed sequence:"; for 0..9999 { .fmt('%04d').say unless %chk2{ .fmt: '%04d'} }
$seq.substr-rw(4443,1) = '.';
my %chk3;
for ^($seq.chars) { %chk3{$seq.substr( $_, 4 )}++ }
put "\nMissing 4 digit PINs in the revised sequence:"; for 0..9999 { .fmt('%04d').say unless %chk3{ .fmt: '%04d'} }</lang>
- Output:
de Bruijn sequence length: 10003 First 130 characters: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 Last 130 characters: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 Missing 4 digit PINs in this sequence: Missing 4 digit PINs in the reversed sequence: Missing 4 digit PINs in the revised sequence: 1459 4591 5814 8145
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. */
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.
zkl
<lang zkl>dbSeq:=Data(); // a byte/character buffer foreach n in (100){
a,a01,a11 := "%02d".fmt(n), a[0,1], a[1,1]; if(a11<a01) continue; dbSeq.append( if(a01==a11) a01 else a ); foreach m in ([n+1 .. 99]){ if("%02d".fmt(m)[1,1] <= a01) continue; dbSeq.append("%s%02d".fmt(a,m)); }
} dbSeq.append("000");</lang> <lang zkl>seqText:=dbSeq.text; println("de Bruijn sequence length: ",dbSeq.len());
println("\nFirst 130 characters:\n",seqText[0,130]); println("\nLast 130 characters:\n", seqText[-130,*]);
fcn chk(seqText){
chk:=Dictionary(); foreach n in ([0..seqText.len()-1]){ chk[seqText[n,4]]=True } (9999).pump(List,"%04d".fmt,'wrap(k){ if(chk.holds(k)) Void.Skip else k })
} println("\nMissing 4 digit PINs in this sequence: ", chk(seqText).concat(" ")); print("Missing 4 digit PINs in the reversed sequence: ",chk(seqText.reverse()).concat(" "));
println("\n4444th character in the sequence: ", seqText[4444]); dbSeq[4444]+=1; println("Adding 1 to the 4444th character and reruning checks: ",chk(dbSeq.text).concat(" "));</lang>
- Output:
de Bruijn sequence length: 10003 First 130 characters: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 Last 130 characters: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 Missing 4 digit PINs in this sequence: Missing 4 digit PINs in the reversed sequence: 4444th character in the sequence: 5 Adding 1 to the 4444th character and reruning checks: 1459 4591 5914 8145