De Bruijn sequences: Difference between revisions

Content added Content deleted

Inline

Revision as of 14:26, 2 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 kⁿ, 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)}   ÷   kⁿ

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,444^th 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

Works with: Rakudo version 2019.07.1

Deviates very slightly from the task spec. Generates a randomized de Bruijn sequence and replaces the 4444th digit with a the digit plus 1 mod 10 rather than a '.', mostly so it can demonstrate detection of extra PINs as well as missing ones.

<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 ^..^ 100 {
       next if .fmt('%02d').substr(1,1) <= $a.substr(0,1);
       $seq ~= sprintf "%s%02d", $a, $_ ;
   }

}

$seq = $seq.comb.list.rotate((^10000).pick).join;

$seq ~= $seq.substr(0,3);

sub check ($seq) {

   my %chk;
   for ^($seq.chars) { %chk{$seq.substr( $_, 4 )}++ }
   put 'Missing: ', (^9999).grep( { not %chk{ .fmt: '%04d' } } ).fmt: '%04d';
   put 'Extra:   ', %chk.grep( *.value > 1 )».key.sort.fmt: '%04d';

}

1. 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 );

put "\nIncorrect 4 digit PINs in this sequence:"; check $seq;

put "\nIncorrect 4 digit PINs in the reversed sequence:"; check $seq.flip;

my $digit = $seq.substr(4443,1); put "\nReplacing the 4444th digit, ($digit) with { ($digit += 1) %= 10 }"; put "Incorrect 4 digit PINs in the revised sequence:"; $seq.substr-rw(4443,1) = $digit; check $seq;</lang>

Sample output:

de Bruijn sequence length: 10003

First 130 characters:
4558455945654566456745684569457545764577457845794585458645874588458945954596459745984599464647464846494655465646574658465946654666

Last 130 characters:
5445644574458445944654466446744684469447544764477447844794485448644874488448944954496449744984499454546454745484549455545564557455

Incorrect 4 digit PINs in this sequence:
Missing: 
Extra:   

Incorrect 4 digit PINs in the reversed sequence:
Missing: 
Extra:   

Replacing the 4444th digit, (1) with 2
Incorrect 4 digit PINs in the revised sequence:
Missing: 0961 1096 6109 9610
Extra:   0962 2096 6209 9620

REXX

The de Bruijn sequence generated by these REXX programs are identical to the sequence shown on the discussion page (1^st 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 5^th 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 1^st REXX version.

zkl

Translation of: Perl6

<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 digit in the sequence: ", seqText[4443]); dbSeq[4443]="."; println("Setting the 4444th digit 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 digit in the sequence: 4
Setting the 4444th digit and reruning checks: 1459 4591 5814 8145