De Bruijn sequences: Difference between revisions
SqrtNegInf (talk | contribs) m →{{header|Perl}}: Fix link: Perl 6 --> Raku |
|||
(40 intermediate revisions by 19 users not shown) | |||
Line 1: | Line 1: | ||
{{task}} |
{{task}} |
||
{{DISPLAYTITLE:de Bruijn sequences}} |
|||
The sequences are named after the Dutch mathematician Nicolaas Govert de Bruijn. |
The sequences are named after the Dutch mathematician Nicolaas Govert de Bruijn. |
||
Line 36: | Line 36: | ||
;Task: |
;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 |
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 [ |
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. |
key and accepts the last <big> ''n'' </big> digits entered. |
||
Note: [ |
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. |
this, but their software has been updated to not allow a brute-force attack. |
||
;Example: |
;Example: |
||
A [ |
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). |
have ''B'' (10, 4) solutions, with a length of '''10,000''' (digits). |
||
Line 64: | Line 64: | ||
:* Again, perform the (above) verification test. |
:* Again, perform the (above) verification test. |
||
:* Replace the 4,444<sup>th</sup> digit with a period (.) in the original de Bruijn sequence. |
:* 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 |
:::* Perform the verification test (again). There should be four PIN codes missing. |
||
Line 71: | Line 71: | ||
Show all output here, on this page. |
Show all output here, on this page. |
||
{{Template:Strings}} |
|||
;References: |
;References: |
||
:* Wikipedia entry: [ |
:* Wikipedia entry: [[wp:De_Bruijn_sequence|de Bruijn sequence]]. |
||
:* MathWorld entry: [http://mathworld.wolfram.com/deBruijnSequence.html de Bruijn sequence]. |
:* MathWorld entry: [http://mathworld.wolfram.com/deBruijnSequence.html de Bruijn sequence]. |
||
:* An OEIS entry: [ |
:* An OEIS entry: [[oeis:A166315|A166315 lexicographically earliest binary de Bruijn sequences, B(2,n)]] --- Not B(10,4), but possibly relevant. |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|D}} |
|||
<syntaxhighlight lang="11l">V digits = ‘0123456789’ |
|||
F deBruijn(k, n) |
|||
V alphabet = :digits[0 .< k] |
|||
V a = [Byte(0)] * (k * n) |
|||
[Byte] seq |
|||
F db(Int t, Int p) -> Void |
|||
I t > @n |
|||
I @n % p == 0 |
|||
@seq.extend(@a[1 .< p + 1]) |
|||
E |
|||
@a[t] = @a[t - p] |
|||
@db(t + 1, p) |
|||
V j = @a[t - p] + 1 |
|||
L j < @k |
|||
@a[t] = j [&] F'F |
|||
@db(t + 1, t) |
|||
j++ |
|||
db(1, 1) |
|||
V buf = ‘’ |
|||
L(i) seq |
|||
buf ‘’= alphabet[i] |
|||
R buf‘’buf[0 .< n - 1] |
|||
F validate(db) |
|||
V found = [0] * 10'000 |
|||
[String] errs |
|||
L(i) 0 .< db.len - 3 |
|||
V s = db[i .< i + 4] |
|||
I s.is_digit() |
|||
found[Int(s)]++ |
|||
L(i) 10'000 |
|||
I found[i] == 0 |
|||
errs [+]= ‘ PIN number #04 missing’.format(i) |
|||
E I found[i] > 1 |
|||
errs [+]= ‘ PIN number #04 occurs #. times’.format(i, found[i]) |
|||
I errs.empty |
|||
print(‘ No errors found’) |
|||
E |
|||
V pl = I errs.len == 1 {‘’} E ‘s’ |
|||
print(‘ ’String(errs.len)‘ error’pl‘ found:’) |
|||
L(err) errs |
|||
print(err) |
|||
V db = deBruijn(10, 4) |
|||
print(‘The length of the de Bruijn sequence is ’db.len) |
|||
print("\nThe first 130 digits of the de Bruijn sequence are: "db[0.<130]) |
|||
print("\nThe last 130 digits of the de Bruijn sequence are: "db[(len)-130..]) |
|||
print("\nValidating the deBruijn sequence:") |
|||
validate(db) |
|||
print("\nValidating the reversed deBruijn sequence:") |
|||
validate(reversed(db)) |
|||
db[4443] = ‘.’ |
|||
print("\nValidating the overlaid deBruijn sequence:") |
|||
validate(db)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 deBruijn sequence: |
|||
No errors found |
|||
Validating the reversed deBruijn sequence: |
|||
No errors found |
|||
Validating the overlaid deBruijn sequence: |
|||
4 errors found: |
|||
PIN number 1459 missing |
|||
PIN number 4591 missing |
|||
PIN number 5814 missing |
|||
PIN number 8145 missing |
|||
</pre> |
|||
=={{header|8080 Assembly}}== |
|||
<syntaxhighlight lang="8080asm">bdos: equ 5 ; BDOS entry point |
|||
putch: equ 2 ; Write character to console |
|||
puts: equ 9 ; Write string to console |
|||
org 100h |
|||
lhld bdos+1 ; Put stack at highest usable address |
|||
sphl |
|||
;;; Generate de_bruijn(10,4) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
mvi c,40 ; Zero out a[] |
|||
xra a |
|||
lxi d,arr |
|||
zloop: stax d |
|||
inx d |
|||
dcr c |
|||
jnz zloop |
|||
lxi h,seq ; H = start of sequence |
|||
lxi b,0101h ; db(1,1) |
|||
call db_ |
|||
lxi d,seq ; Allow wrap-around by appending first 3 digits |
|||
mvi c,3 |
|||
wrap: ldax d ; get one of first digits |
|||
mov m,a ; store after last digit |
|||
inx d ; advance pointers |
|||
inx h |
|||
dcr c ; do this 3 times |
|||
jnz wrap |
|||
push h ; store end of data |
|||
;;; Print length ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
lxi d,slen ; print "Length: " |
|||
call pstr |
|||
lxi d,-seq ; calculate length (-seq+seqEnd) |
|||
dad d |
|||
call puthl ; print length |
|||
call pnl ; print newline |
|||
;;; Print first and last 130 digits ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
lxi d,sfrst ; print "First 130: " |
|||
call pstr |
|||
lxi h,seq ; print first 130 digits |
|||
call p130 |
|||
call pnl ; print newline |
|||
lxi d,slast ; print "Last 130: " |
|||
call pstr |
|||
pop h ; Get end of sequence |
|||
push h |
|||
lxi d,-130 ; 130th last digit |
|||
dad d |
|||
call p130 ; print last 130 digits |
|||
call pnl |
|||
call verify ; verify that all numbers are there |
|||
;;; Reverse and verify ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
lxi d,srev ; Print "reversing..." |
|||
call pstr |
|||
pop h ; HL = address of last digit |
|||
dcx h |
|||
push h ; stack = address of last digit |
|||
lxi d,seq ; DE = address of first digit |
|||
call rvrs ; Reverse |
|||
call verify ; Verify that all numbers are there |
|||
lxi d,seq ; Then reverse again (restoring it) |
|||
pop h |
|||
call rvrs |
|||
;;; Replace 4444th digit with '.' and verify ;;;;;;;;;;;;;;;;;;;;;; |
|||
lxi d,s4444 |
|||
call pstr |
|||
mvi a,'.' |
|||
sta seq+4444 |
|||
call verify |
|||
rst 0 |
|||
;;; db(t,p); t,p in B,C; end of sequence in HL ;;;;;;;;;;;;;;;;;;;; |
|||
db_: mov a,b ; if t>n (n=4) |
|||
cpi 5 ; t >= n+1 |
|||
jc dbelse |
|||
mov a,c ; 4%p==0, for p in {1,2,3,4}, is false iff p=3 |
|||
cpi 3 |
|||
rz ; stop if p=3, i.e. 4%p<>0 |
|||
lxi d,arr+1 ; copy P elements to seq forom arr[1..] |
|||
dbextn: ldax d ; take from a[] |
|||
mov m,a ; store in sequence |
|||
inx h ; advance pointers |
|||
inx d |
|||
dcr c ; and do this P times |
|||
jnz dbextn |
|||
ret |
|||
dbelse: mov a,b ; t - p |
|||
sub c |
|||
mvi d,arr/256 |
|||
mov e,a ; a[] is page-aligned for easier indexing |
|||
ldax d ; get a[t-p] |
|||
mov e,b ; store in a[t] |
|||
stax d |
|||
push b ; keep T and P |
|||
inr b ; db(t+1, p) |
|||
call db_ |
|||
pop b ; restore T and P |
|||
mov a,b ; get a[t-p] |
|||
sub c |
|||
mvi d,arr/256 |
|||
mov e,a |
|||
ldax d ; j = a[t-p] |
|||
dbloop: inr a ; j++ |
|||
cpi 10 ; reached K = 10? |
|||
rnc ; then stop |
|||
mvi d,arr/256 |
|||
mov e,b |
|||
stax d ; a[t] = j |
|||
push psw ; keep j |
|||
push b ; keep t and p |
|||
mov c,b |
|||
inr b |
|||
call db_ ; db(t+1, t) |
|||
pop b ; restore t and p |
|||
pop psw ; restore j |
|||
jmp dbloop |
|||
;;; Verify that all numbers are there ;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
verify: lxi d,sver ; print "Verifying... " |
|||
call pstr |
|||
mvi d,0 ; Zero out the flag array |
|||
lxi b,10000 |
|||
lxi h,val |
|||
vzero: mov m,d |
|||
inx h |
|||
dcx b |
|||
mov a,b |
|||
ora c |
|||
jnz vzero |
|||
lxi h,seq ; Sequence pointer |
|||
donum: push h ; Store sequence pointer |
|||
push h ; Push two copies |
|||
lxi h,0 ; Current 4-digit number |
|||
mvi c,4 ; Number has 4 digits |
|||
dgtadd: mov d,h ; HL *= 10 |
|||
mov e,l |
|||
dad h |
|||
dad h |
|||
dad d |
|||
dad h |
|||
xthl ; Get sequence pointer |
|||
mov a,m ; Get digit |
|||
inx h ; Advance pointer |
|||
cpi 10 ; Valid digit? |
|||
jnc dinval ; If not, go do next 4-digit number |
|||
xthl ; Back to number |
|||
mov e,a |
|||
mvi d,0 |
|||
dad d ; Add digit to number |
|||
dcr c ; More digits? |
|||
jnz dgtadd ; Then get digit |
|||
lxi d,val ; HL is now the current 4-digit number |
|||
dad d |
|||
inr m ; val[HL]++ (we've seen it) |
|||
dinval: pop h ; Pointer to after last valid digit |
|||
pop h ; Pointer to start of current number |
|||
inx h ; Get 4-digit number that starts at next digit |
|||
mov d,h ; Next pointer in DE |
|||
mov e,l |
|||
lxi b,-(seq+10000) ; Are we there yet? |
|||
dad b |
|||
mov a,h |
|||
ora l |
|||
xchg ; Next pointer back in HL |
|||
jnz donum ; If not done, do next number. |
|||
lxi h,val ; Done - get start of validation array |
|||
mvi b,0 ; B will be set if one is missing |
|||
vnum: mov a,m ; Have we seen HL-val? |
|||
ana a |
|||
jnz vnext ; If so, do the next number |
|||
push h ; Otherwise, keep current address, |
|||
lxi d,-val ; Subtract val (to get the number) |
|||
dad d |
|||
call puthl ; Print this number as being missing |
|||
mvi b,1 ; Set B, |
|||
pop h ; and then restore the address |
|||
vnext: inx h ; Increment the number |
|||
push h |
|||
lxi d,-(val+10000) ; Are we there yet? |
|||
dad d |
|||
mov a,h |
|||
ora l |
|||
pop h |
|||
jnz vnum ; If not, check next number. |
|||
dcr b ; At the end, if B was not set, |
|||
lxi d,snone ; print "none missing", |
|||
jnz pstr |
|||
lxi d,smiss ; otherwise, print "missing" |
|||
jmp pstr |
|||
;;; Subroutines ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
;;; reverse memory starting at DE and ending at HL |
|||
rvrs: mov b,m ; Load [HL] |
|||
ldax d ; Load [DE] |
|||
mov m,a ; [HL] = old [DE] |
|||
mov a,b |
|||
stax d ; [DE] = old [HL] |
|||
inx d ; Move bottom pointer upwards, |
|||
dcx h ; Move top pointer downwards, |
|||
mov a,d ; D<H = not there yet |
|||
cmp h |
|||
jc rvrs |
|||
mov a,e ; E<L = not there yet |
|||
cmp l |
|||
jc rvrs |
|||
ret |
|||
;;; print number in HL, saving registers |
|||
puthl: push h ; save registers |
|||
push d |
|||
push b |
|||
lxi b,nbuf ; number buffer pointer |
|||
push b ; keep it on the stack |
|||
dgt: lxi b,-10 |
|||
lxi d,-1 |
|||
dgtdiv: inx d ; calculate digit |
|||
dad b |
|||
jc dgtdiv |
|||
mvi a,'0'+10 |
|||
add l |
|||
pop h ; get pointer from stack |
|||
dcx h ; go to previous digit |
|||
mov m,a ; store digit |
|||
push h ; put pointer back |
|||
xchg ; are there any more digits? |
|||
mov a,h |
|||
ora l |
|||
jnz dgt ; if so, calculate next digit |
|||
pop d ; otherwise, get pointer to first digit |
|||
jmp pstr_ ; and print the resulting string |
|||
;;; print 130 digits from the sequence, starting at HL |
|||
p130: push h |
|||
push d |
|||
push b |
|||
mvi b,130 ; 130 digits |
|||
p130l: mov a,m ; get current digit |
|||
adi '0' ; make ASCII |
|||
inx h ; advance pointer |
|||
push b ; save pointer and counter |
|||
push h |
|||
mvi c,putch ; print character |
|||
mov e,a |
|||
call bdos |
|||
pop h ; restore pointer and counter |
|||
pop b |
|||
dcr b ; one fewer character left |
|||
jnz p130l ; if characters left, print next |
|||
jmp rsreg ; otherwise, restore registers and return |
|||
;;; print newline |
|||
pnl: lxi d,snl |
|||
;;; print string in DE, saving registers |
|||
pstr: push h ; store registers |
|||
push d |
|||
push b |
|||
pstr_: mvi c,puts ; print string using CP/M |
|||
call bdos |
|||
rsreg: pop b ; restore registers |
|||
pop d |
|||
pop h |
|||
ret |
|||
snl: db 13,10,'$' |
|||
slen: db 'Length: $' |
|||
sfrst: db 'First 130: $' |
|||
slast: db 'Last 130: $' |
|||
srev: db 'Reversing...',13,10,'$' |
|||
s4444: db 'Set seq[4444] to `.`...',13,10,'$' |
|||
sver: db 'Verifying... $' |
|||
snone: db 'none ' |
|||
smiss: db 'missing',13,10,'$' |
|||
db '00000' ; number output buffer |
|||
nbuf: db ' $' |
|||
arr: equ ($/256+1)*256 ; Place to store a[] (page-aligned) |
|||
val: equ arr+40 ; Place to store validation flags |
|||
seq: equ val+10000 ; Place to store De Bruijn sequence</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Length: 10003 |
|||
First 130: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 |
|||
Last 130: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 |
|||
Verifying... none missing |
|||
Reversing... |
|||
Verifying... none missing |
|||
Set seq[4444] to `.`... |
|||
Verifying... 1459 4591 5914 8145 missing</pre> |
|||
=={{header|8086 Assembly}}== |
|||
<syntaxhighlight lang="asm">putch: equ 2 ; Print character |
|||
puts: equ 9 ; Print string |
|||
cpu 8086 |
|||
bits 16 |
|||
section .text |
|||
org 100h |
|||
;;; Calculate de_bruijn(10, 4) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
xor ax,ax ; zero a[] |
|||
mov di,arr |
|||
mov cx,20 ; 20 words = 40 bytes |
|||
rep stosw |
|||
mov di,seq ; start of sequence |
|||
mov dx,0101h ; db(1,1) |
|||
call db_ |
|||
mov si,seq ; Add first 3 to end for wrapping |
|||
mov cx,3 |
|||
rep movsb |
|||
lea bp,[di-1] ; Store pointer to last digit in BP |
|||
;;; Print length ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
mov ah,puts ; Print "Length:" |
|||
mov dx,slen |
|||
int 21h |
|||
mov ax,di ; Length = end - start |
|||
sub ax,seq |
|||
call putax ; Print length |
|||
;;; Print first and last 130 characters and verify ;;;;;;;;;;;;;;;; |
|||
mov ah,puts ; Print "First 130..." |
|||
mov dx,sfrst |
|||
int 21h |
|||
mov si,seq ; print first 130 digits |
|||
call p130 |
|||
mov ah,puts ; Print "Last 130..." |
|||
mov dx,slast |
|||
int 21h |
|||
mov si,di ; print last 130 digit |
|||
sub si,130 |
|||
call p130 |
|||
call verify |
|||
;;;; Reverse the sequence and verify ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
mov ah,puts ; Print "Reversing..." |
|||
mov dx,srev |
|||
int 21h |
|||
mov si,seq ; SI = first digit in sequence |
|||
mov di,bp ; DI = last digit in sequence |
|||
call rvrs ; Reverse |
|||
call verify ; Verify |
|||
mov si,seq ; Reverse again, putting it back |
|||
mov di,bp |
|||
call rvrs |
|||
;;; Set seq[4444] to '.' and verify ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
mov ah,puts ; Print "set seq[4444] to '.'" |
|||
mov dx,s4444 |
|||
int 21h |
|||
mov [seq+4444],byte '.' |
|||
call verify ; Verify |
|||
ret |
|||
;;; db(t, p); t=dh p=dl, di=seq ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
db_: cmp dh,4 ; t>n? (n=4) |
|||
jbe .els |
|||
cmp dl,3 ; for p in {1,2,3,4}, 4%p==0 iff p=3 |
|||
je .out |
|||
mov si,arr+1 ; add DL=P bytes from a[1..] to sequence |
|||
mov cl,dl |
|||
xor ch,ch |
|||
rep movsb |
|||
jmp .out |
|||
.els: xor bh,bh |
|||
mov bl,dh |
|||
sub bl,dl ; t - p |
|||
mov al,[arr+bx] ; al = a[t-p] |
|||
mov bl,dh ; t |
|||
mov [arr+bx],al ; a[t] = al |
|||
push dx ; keep arguments |
|||
inc dh ; db(++t,p) |
|||
call db_ |
|||
pop dx ; restore arguments |
|||
mov bl,dh ; al = a[t-p] |
|||
sub bl,dl |
|||
mov al,[arr+bx] |
|||
.loop: inc al ; al++ |
|||
cmp al,10 ; when al>=k, |
|||
jae .out ; then stop. |
|||
mov bl,dh |
|||
mov [arr+bx],al ; a[t] = j |
|||
push ax ; keep state |
|||
push dx |
|||
mov dl,dh ; db(t+1, t) |
|||
inc dh |
|||
call db_ |
|||
pop dx |
|||
pop ax |
|||
jmp .loop |
|||
.out: ret |
|||
;;; Verify that all numbers are there ;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
verify: mov ah,puts ; Print "verifying..." |
|||
mov dx,sver |
|||
int 21h |
|||
mov di,val ; Zero validation array |
|||
mov cx,5000 ; 10000 bytes = 5000 words |
|||
xor ax,ax |
|||
rep stosw |
|||
mov di,val |
|||
mov si,seq ; Pointer to start of sequence |
|||
mov cx,6409h ; CH=100 (multiplier), CL=9 (highest digit) |
|||
.num: mov ax,[si] ; Read first two digits |
|||
cmp ah,cl ; Check that they are valid |
|||
ja .inval |
|||
cmp al,cl |
|||
ja .inval |
|||
xchg al,ah ; High digit * 10 + low digit |
|||
aad |
|||
mul ch ; Multiply by 100 (to add in next two) |
|||
mov bx,ax |
|||
mov ax,[si+2] ; Read last two digits |
|||
cmp ah,cl ; Check that they are valid |
|||
ja .inval |
|||
cmp al,cl |
|||
ja .inval |
|||
xchg al,ah ; High digit * 10 + low digit |
|||
aad |
|||
add bx,ax ; BX = final 4-digit number |
|||
inc byte [di+bx] ; Mark this 4-digit number as seen |
|||
.inval: inc si ; Next digit |
|||
cmp si,seq+10000 ; Are we at the end yet? |
|||
jne .num ; If not, do next number |
|||
mov si,val ; For each number < 10000, check if it's there |
|||
xor cl,cl ; Will be set if a number is missing |
|||
.test: lodsb ; Do we have this number? |
|||
test al,al |
|||
jnz .tnext ; If so, try next number |
|||
mov ax,si ; Otherwise, print the missing number |
|||
sub ax,val |
|||
call putax |
|||
mov cl,1 ; And set CL |
|||
.tnext: cmp si,val+10000 ; Are we at the end yet? |
|||
jne .test |
|||
test cl,cl |
|||
mov dx,smiss ; Print "... missing" |
|||
jnz .print ; if CL is set |
|||
mov dx,snone ; or "none missing" otherwise. |
|||
.print: mov ah,puts |
|||
int 21h |
|||
ret |
|||
;;; Subroutines ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
;;; Print number in AX |
|||
putax: push ax ; Keep registers we're changing |
|||
push dx |
|||
push bx |
|||
push di |
|||
mov di,numbuf ; Pointer to number buffer |
|||
mov bx,10 ; Divisor |
|||
.digit: xor dx,dx ; Divide AX by 10 |
|||
div bx |
|||
add dl,'0' ; Add '0' to remainder (digit) |
|||
dec di ; Store digit in buffer |
|||
mov [di],dl |
|||
test ax,ax ; Any more digits? |
|||
jnz .digit ; If so, do next digits |
|||
mov dx,di ; At the end, print the string |
|||
mov ah,puts |
|||
int 21h |
|||
pop di ; Restore registers |
|||
pop bx |
|||
pop dx |
|||
pop ax |
|||
ret |
|||
;;; Print 130 digits starting at SI |
|||
p130: mov cx,130 ; 130 characters |
|||
mov ah,putch ; Print characters |
|||
.loop: lodsb ; Get digit |
|||
add al,'0' ; Make ASCII |
|||
mov dl,al ; Print digit |
|||
int 21h |
|||
loop .loop |
|||
ret |
|||
;;; Reverse memory starting at SI and ending at DI |
|||
rvrs: mov al,[si] ; Load [SI], |
|||
mov ah,[di] ; Load [DI], |
|||
mov [di],al ; Set [DI] = old [SI] |
|||
mov [si],ah ; Set [SI] = old [DI] |
|||
inc si ; Increment bottom pointer |
|||
dec di ; Decrement top pointer |
|||
cmp si,di ; If SI >= DI, we're done |
|||
jb rvrs |
|||
ret |
|||
section .data |
|||
slen: db 'Length: $' |
|||
sfrst: db 13,10,'First 130: $' |
|||
slast: db 13,10,'Last 130: $' |
|||
srev: db 13,10,'Reversing... $' |
|||
s4444: db 13,10,'Set seq[4444] to `.`...$' |
|||
sver: db 13,10,'Verifying... $' |
|||
snone: db 'none ' |
|||
smiss: db 'missing.$' |
|||
db '00000' |
|||
numbuf: db ' $' |
|||
section .bss |
|||
arr: resb 40 ; a[] |
|||
val: resb 10000 ; validation array |
|||
seq: equ $</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Length: 10003 |
|||
First 130: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 |
|||
Last 130: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 |
|||
Verifying... none missing. |
|||
Reversing... |
|||
Verifying... none missing. |
|||
Set seq[4444] to `.`... |
|||
Verifying... 1460 4592 5915 8146 missing.</pre> |
|||
=={{header|Ada}}== |
|||
{{trans|D}} |
|||
<syntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO; |
|||
with Ada.Strings.Fixed; use Ada.Strings; |
|||
with Ada.Strings.Unbounded; |
|||
procedure De_Bruijn_Sequences is |
|||
function De_Bruijn (K, N : Positive) return String |
|||
is |
|||
use Ada.Strings.Unbounded; |
|||
Alphabet : constant String := "0123456789"; |
|||
subtype Decimal is Integer range 0 .. 9; |
|||
type Decimal_Array is array (Natural range <>) of Decimal; |
|||
A : Decimal_Array (0 .. K * N - 1) := (others => 0); |
|||
Seq : Unbounded_String; |
|||
procedure Db (T, P : Positive) is |
|||
begin |
|||
if T > N then |
|||
if N mod P = 0 then |
|||
for E of A (1 .. P) loop |
|||
Append (Seq, Alphabet (Alphabet'First + E)); |
|||
end loop; |
|||
end if; |
|||
else |
|||
A (T) := A (T - P); |
|||
Db (T + 1, P); |
|||
for J in A (T - P) + 1 .. K - 1 loop |
|||
A (T) := J; |
|||
Db (T + 1, T); |
|||
end loop; |
|||
end if; |
|||
end Db; |
|||
begin |
|||
Db (1, 1); |
|||
return To_String (Seq) & Slice (Seq, 1, N - 1); |
|||
end De_Bruijn; |
|||
function Image (Value : Integer) return String |
|||
is (Fixed.Trim (Value'Image, Left)); |
|||
function PIN_Image (Value : Integer) return String |
|||
is (Fixed.Tail (Image (Value), Count => 4, Pad => '0')); |
|||
procedure Validate (Db : String) |
|||
is |
|||
Found : array (0 .. 9_999) of Natural := (others => 0); |
|||
Errors : Natural := 0; |
|||
begin |
|||
-- Check all strings of 4 consecutive digits within 'db' |
|||
-- to see if all 10,000 combinations occur without duplication. |
|||
for A in Db'First .. Db'Last - 3 loop |
|||
declare |
|||
PIN : String renames Db (A .. A + 4 - 1); |
|||
begin |
|||
if (for all Char of PIN => Char in '0' .. '9') then |
|||
declare |
|||
N : constant Integer := Integer'Value (PIN); |
|||
F : Natural renames Found (N); |
|||
begin |
|||
F := F + 1; |
|||
end; |
|||
end if; |
|||
end; |
|||
end loop; |
|||
for I in 0_000 .. 9_999 loop |
|||
if Found (I) = 0 then |
|||
Put_Line (" PIN number " & PIN_Image (I) & " missing"); |
|||
Errors := Errors + 1; |
|||
elsif Found (I) > 1 then |
|||
Put_Line (" PIN number " & PIN_Image (I) & " occurs " |
|||
& Image (Found (I)) & " times"); |
|||
Errors := Errors + 1; |
|||
end if; |
|||
end loop; |
|||
case Errors is |
|||
when 0 => Put_Line (" No errors found"); |
|||
when 1 => Put_Line (" 1 error found"); |
|||
when others => |
|||
Put_Line (" " & Image (Errors) & " errors found"); |
|||
end case; |
|||
end Validate; |
|||
function Backwards (S : String) return String is |
|||
R : String (S'Range); |
|||
begin |
|||
for A in 0 .. S'Length - 1 loop |
|||
R (R'Last - A) := S (S'First + A); |
|||
end loop; |
|||
return R; |
|||
end Backwards; |
|||
DB : constant String := De_Bruijn (K => 10, N => 4); |
|||
Rev : constant String := Backwards (DB); |
|||
Ovl : String := DB; |
|||
begin |
|||
Put_Line ("The length of the de Bruijn sequence is " & DB'Length'Image); |
|||
New_Line; |
|||
Put_Line ("The first 130 digits of the de Bruijn sequence are: "); |
|||
Put_Line (" " & Fixed.Head (DB, 130)); |
|||
New_Line; |
|||
Put_Line ("The last 130 digits of the de Bruijn sequence are: "); |
|||
Put_Line (" " & Fixed.Tail (DB, 130)); |
|||
New_Line; |
|||
Put_Line ("Validating the deBruijn sequence:"); |
|||
Validate (DB); |
|||
New_Line; |
|||
Put_Line ("Validating the reversed deBruijn sequence:"); |
|||
Validate (Rev); |
|||
New_Line; |
|||
Ovl (4444) := '.'; |
|||
Put_Line ("Validating the overlaid deBruijn sequence:"); |
|||
Validate (Ovl); |
|||
New_Line; |
|||
end De_Bruijn_Sequences;</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 deBruijn sequence: |
|||
No errors found |
|||
Validating the reversed deBruijn sequence: |
|||
No errors found |
|||
Validating the overlaid deBruijn sequence: |
|||
PIN number 1459 missing |
|||
PIN number 4591 missing |
|||
PIN number 5814 missing |
|||
PIN number 8145 missing |
|||
4 errors found |
|||
</pre> |
|||
=={{header|BASIC}}== |
|||
<syntaxhighlight lang="gwbasic">10 DEFINT A-Z |
|||
20 K = 10: N = 4 |
|||
30 DIM A(K*N), S(K^N+N), T(5), P(5), V(K^N\8) |
|||
40 GOSUB 200 |
|||
50 PRINT "Length: ",S |
|||
60 PRINT "First 130:" |
|||
70 FOR I=0 TO 129: PRINT USING "#";S(I);: NEXT |
|||
80 PRINT: PRINT "Last 130:" |
|||
90 FOR I=S-130 TO S-1: PRINT USING "#";S(I);: NEXT |
|||
100 PRINT |
|||
110 GOSUB 600 |
|||
120 PRINT "Reversing...": GOSUB 500: GOSUB 600: GOSUB 500 |
|||
130 PRINT USING "Replacing 4444'th element (#):";S(4443) |
|||
140 S(4443) = -1 : REM 0-indexed, and using integers |
|||
150 GOSUB 600 |
|||
160 END |
|||
200 REM Generate De Bruijn sequence given K and N |
|||
210 T(R) = 1: P(R) = 1 |
|||
220 IF T(R) > N GOTO 380 |
|||
230 A(T(R)) = A(T(R)-P(R)) |
|||
240 R = R+1 |
|||
250 T(R) = T(R-1)+1 |
|||
260 P(R) = P(R-1) |
|||
270 GOSUB 220 |
|||
280 R = R-1 |
|||
290 FOR J = A(T(R)-P(R))+1 TO K-1 |
|||
300 A(T(R)) = J |
|||
310 R = R+1 |
|||
320 T(R) = T(R-1)+1 |
|||
330 P(R) = T(R-1) |
|||
340 GOSUB 220 |
|||
350 R = R-1 |
|||
355 J = A(T(R)) |
|||
360 NEXT |
|||
370 RETURN |
|||
380 IF N MOD P(R) THEN RETURN |
|||
390 FOR I = 1 TO P(R) |
|||
400 S(S) = A(I) |
|||
410 S = S+1 |
|||
420 NEXT |
|||
430 RETURN |
|||
500 REM Reverse the sequence |
|||
510 FOR I=0 TO S\2 |
|||
520 J = S(I) |
|||
530 S(I) = S(S-I) |
|||
540 S(S-I) = J |
|||
550 NEXT |
|||
560 RETURN |
|||
600 REM Validate the sequence (uses bit packing to save memory) |
|||
610 PRINT "Validating..."; |
|||
620 FOR I=0 TO N-1: S(S+I)=S(I): NEXT |
|||
630 FOR I=0 TO K^N\8-1: V(I)=0: NEXT |
|||
640 FOR I=0 TO S |
|||
650 P=0 |
|||
660 FOR J=0 TO N-1 |
|||
662 D=S(I+J) |
|||
663 IF D<0 GOTO 690 |
|||
665 P=K*P+D |
|||
669 NEXT J |
|||
670 X=P\8 |
|||
680 V(X) = V(X) OR 2^(P AND 7) |
|||
690 NEXT I |
|||
700 M=1 |
|||
710 FOR I=0 TO K^N\8-1 |
|||
720 IF V(I)=255 GOTO 760 |
|||
730 FOR J=0 TO 7 |
|||
740 IF (V(I) AND 2^J)=0 THEN M=0: PRINT USING " ####";I*8+J; |
|||
750 NEXT |
|||
760 NEXT |
|||
770 IF M THEN PRINT " none"; |
|||
780 PRINT " missing." |
|||
790 RETURN</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Length: 10000 |
|||
First 130: |
|||
00001000200030004000500060007000800090011001200130014001500160017001800190021002 |
|||
20023002400250026002700280029003100320033003400350 |
|||
Last 130: |
|||
89768986899696977697869796987698869896997699869997777877797788778977987799787879 |
|||
78887889789878997979887989799879998888988998989999 |
|||
Validating... none missing. |
|||
Reversing... |
|||
Validating... none missing. |
|||
Replacing 4444'th element (4): |
|||
Validating... 1459 4591 5814 8145 missing.</pre> |
|||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
using System.Text; |
using System.Text; |
||
Line 184: | Line 1,011: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The length of the de Bruijn sequence is 10003 |
<pre>The length of the de Bruijn sequence is 10003 |
||
Line 207: | Line 1,034: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{trans|D}} |
{{trans|D}} |
||
< |
<syntaxhighlight lang="cpp">#include <algorithm> |
||
#include <functional> |
#include <functional> |
||
#include <iostream> |
#include <iostream> |
||
Line 321: | Line 1,148: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The length of the de Bruijn sequence is 10003 |
<pre>The length of the de Bruijn sequence is 10003 |
||
Line 341: | Line 1,168: | ||
PIN number 5814 missing |
PIN number 5814 missing |
||
PIN number 8145 missing</pre> |
PIN number 8145 missing</pre> |
||
=={{header|CLU}}== |
|||
<syntaxhighlight lang="clu">% Generate the De Bruijn sequence consisiting of N-digit numbers |
|||
de_bruijn = cluster is generate |
|||
rep = null |
|||
own k: int := 0 |
|||
own n: int := 0 |
|||
own a: array[int] := array[int]$[] |
|||
own seq: array[int] := array[int]$[] |
|||
generate = proc (k_, n_: int) returns (string) |
|||
k := k_ |
|||
n := n_ |
|||
a := array[int]$fill(0, k*n, 0) |
|||
seq := array[int]$[] |
|||
db(1, 1) |
|||
s: stream := stream$create_output() |
|||
for i: int in array[int]$elements(seq) do |
|||
stream$puts(s, int$unparse(i)) |
|||
end |
|||
return(stream$get_contents(s)) |
|||
end generate |
|||
db = proc (t, p: int) |
|||
if t>n then |
|||
if n//p = 0 then |
|||
for i: int in int$from_to(1, p) do |
|||
array[int]$addh(seq, a[i]) |
|||
end |
|||
end |
|||
else |
|||
a[t] := a[t - p] |
|||
db(t+1, p) |
|||
for j: int in int$from_to(a[t - p] + 1, k-1) do |
|||
a[t] := j |
|||
db(t + 1, t) |
|||
end |
|||
end |
|||
end db |
|||
end de_bruijn |
|||
% Reverse a string |
|||
reverse = proc (s: string) returns (string) |
|||
r: array[char] := array[char]$predict(1, string$size(s)) |
|||
for c: char in string$chars(s) do |
|||
array[char]$addl(r, c) |
|||
end |
|||
return(string$ac2s(r)) |
|||
end reverse |
|||
% Find all missing N-digit values |
|||
find_missing = proc (db: string, n: int) returns (sequence[string]) |
|||
db := db || string$substr(db, 1, n) % wrap |
|||
missing: array[string] := array[string]$[] |
|||
s: stream := stream$create_output() |
|||
for i: int in int$from_to(0, 10**n-1) do |
|||
%s: stream := stream$create_output() |
|||
stream$reset(s) |
|||
stream$putzero(s, int$unparse(i), n) |
|||
val: string := stream$get_contents(s) |
|||
if string$indexs(val, db) = 0 then |
|||
array[string]$addh(missing, val) |
|||
end |
|||
end |
|||
return(sequence[string]$a2s(missing)) |
|||
end find_missing |
|||
% Report all missing values, or 'none'. |
|||
validate = proc (s: stream, db: string, n: int) |
|||
stream$puts(s, "Validating...") |
|||
missing: sequence[string] := find_missing(db, n) |
|||
for v: string in sequence[string]$elements(missing) do |
|||
stream$puts(s, " " || v) |
|||
end |
|||
if sequence[string]$size(missing) = 0 then |
|||
stream$puts(s, " none") |
|||
end |
|||
stream$putl(s, " missing.") |
|||
end validate |
|||
start_up = proc () |
|||
po: stream := stream$primary_output() |
|||
% Generate the De Bruijn sequence for 4-digit numbers |
|||
db: string := de_bruijn$generate(10, 4) |
|||
% Report length and first and last digits |
|||
stream$putl(po, "Length: " || int$unparse(string$size(db))) |
|||
stream$putl(po, "First 130 characters:") |
|||
stream$putl(po, string$substr(db, 1, 130)) |
|||
stream$putl(po, "Last 130 characters:") |
|||
stream$putl(po, string$substr(db, string$size(db)-130, 130)) |
|||
% See if there are any missing values in the sequence |
|||
validate(po, db, 4) |
|||
% Reverse and validate again |
|||
stream$putl(po, "Reversing...") |
|||
validate(po, reverse(db), 4) |
|||
% Replace the 4444'th element with '.' and validate again |
|||
stream$putl(po, "Setting the 4444'th character to '.'...") |
|||
db := string$substr(db, 1, 4443) || "." || string$rest(db, 4445) |
|||
validate(po, db, 4) |
|||
end start_up</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Length: 10000 |
|||
First 130 characters: |
|||
0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 |
|||
Last 130 characters: |
|||
6897689868996969776978697969876988698969976998699977778777977887789779877997878797888788978987899797988798979987999888898899898999 |
|||
Validating... none missing. |
|||
Reversing... |
|||
Validating... none missing. |
|||
Setting the 4444'th character to '.'... |
|||
Validating... 1459 4591 5814 8145 missing.</pre> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="d">import std.array; |
||
import std.conv; |
import std.conv; |
||
import std.format; |
import std.format; |
||
Line 440: | Line 1,383: | ||
writeln("\nValidating the overlaid deBruijn sequence:"); |
writeln("\nValidating the overlaid deBruijn sequence:"); |
||
validate(db); |
validate(db); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The length of the de Bruijn sequence is 10003 |
<pre>The length of the de Bruijn sequence is 10003 |
||
Line 460: | Line 1,403: | ||
PIN number 5814 missing |
PIN number 5814 missing |
||
PIN number 8145 missing</pre> |
PIN number 8145 missing</pre> |
||
=={{header|EasyLang}}== |
|||
{{trans|Lua}} |
|||
<syntaxhighlight lang=text> |
|||
global a[] seq[] k n . |
|||
proc db t p . . |
|||
if t > n |
|||
if n mod p = 0 |
|||
for i = 1 to p |
|||
seq[] &= a[i + 1] |
|||
. |
|||
. |
|||
else |
|||
a[t + 1] = a[t - p + 1] |
|||
db t + 1 p |
|||
j = a[t - p + 1] + 1 |
|||
while j < k |
|||
a[t + 1] = j mod 256 |
|||
db t + 1 t |
|||
j += 1 |
|||
. |
|||
. |
|||
. |
|||
func$ debruijn k0 n0 . |
|||
k = k0 |
|||
n = n0 |
|||
a[] = [ ] |
|||
len a[] k * n |
|||
seq[] = [ ] |
|||
db 1 1 |
|||
for v in seq[] |
|||
buf$ &= v |
|||
. |
|||
buf$ &= substr buf$ 1 (n - 1) |
|||
return buf$ |
|||
. |
|||
func alldigits s$ . |
|||
for c$ in strchars s$ |
|||
if strcode c$ < 48 or strcode c$ > 57 |
|||
return 0 |
|||
. |
|||
. |
|||
return 1 |
|||
. |
|||
proc validate db$ . . |
|||
len found[] 10000 |
|||
for i = 1 to len db$ - 3 |
|||
s$ = substr db$ i 4 |
|||
if alldigits s$ = 1 |
|||
n = number s$ |
|||
found[n + 1] += 1 |
|||
. |
|||
. |
|||
for i = 1 to 10000 |
|||
if found[i] = 0 |
|||
errs$[] &= " PIN number " & i - 1 & " missing" |
|||
elif found[i] > 1 |
|||
errs$[] &= " PIN number " & i - 1 & " occurs " & found[i] & " times" |
|||
. |
|||
. |
|||
if len errs$[] = 0 |
|||
print " No errors found" |
|||
else |
|||
for s$ in errs$[] |
|||
print s$ |
|||
. |
|||
. |
|||
. |
|||
proc main . . |
|||
db$ = debruijn 10 4 |
|||
print "The length of the de Bruijn sequence is " & len db$ |
|||
print "" |
|||
write "The first 130 digits of the de Bruijn sequence are: " |
|||
print substr db$ 1 130 |
|||
print "" |
|||
write "The last 130 digits of the de Bruijn sequence are: " |
|||
print substr db$ -130 130 |
|||
print "" |
|||
print "Validating the de Bruijn sequence:" |
|||
validate db$ |
|||
print "" |
|||
print "Validating the reversed de Bruijn sequence:" |
|||
for i = len db$ downto 1 |
|||
dbr$ &= substr db$ i 1 |
|||
. |
|||
validate dbr$ |
|||
print "" |
|||
db$ = substr db$ 1 4443 & "." & substr db$ 4445 (1 / 0) |
|||
print "Validating the overlaid de Bruijn sequence:" |
|||
validate db$ |
|||
print "" |
|||
. |
|||
main |
|||
</syntaxhighlight> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 571: | Line 1,608: | ||
fmt.Println("\nValidating the overlaid de Bruijn sequence:") |
fmt.Println("\nValidating the overlaid de Bruijn sequence:") |
||
validate(db) |
validate(db) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 596: | Line 1,633: | ||
PIN number 8145 missing |
PIN number 8145 missing |
||
</pre> |
</pre> |
||
=={{header|Groovy}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="groovy">import java.util.function.BiConsumer |
|||
class DeBruijn { |
|||
interface Recursable<T, U> { |
|||
void apply(T t, U u, Recursable<T, U> r); |
|||
} |
|||
static <T, U> BiConsumer<T, U> recurse(Recursable<T, U> f) { |
|||
return { t, u -> f.apply(t, u, f) } |
|||
} |
|||
private static String deBruijn(int k, int n) { |
|||
byte[] a = new byte[k * n] |
|||
Arrays.fill(a, (byte) 0) |
|||
List<Byte> seq = new ArrayList<>() |
|||
BiConsumer<Integer, Integer> db = recurse({ int t, int p, f -> |
|||
if (t > n) { |
|||
if (n % p == 0) { |
|||
for (int i = 1; i < p + 1; ++i) { |
|||
seq.add(a[i]) |
|||
} |
|||
} |
|||
} else { |
|||
a[t] = a[t - p] |
|||
f.apply(t + 1, p, f) |
|||
int j = a[t - p] + 1 |
|||
while (j < k) { |
|||
a[t] = (byte) (j & 0xFF) |
|||
f.apply(t + 1, t, f) |
|||
j++ |
|||
} |
|||
} |
|||
}) |
|||
db.accept(1, 1) |
|||
StringBuilder sb = new StringBuilder() |
|||
for (Byte i : seq) { |
|||
sb.append("0123456789".charAt(i)) |
|||
} |
|||
sb.append(sb.subSequence(0, n - 1)) |
|||
return sb.toString() |
|||
} |
|||
private static boolean allDigits(String s) { |
|||
for (int i = 0; i < s.length(); ++i) { |
|||
char c = s.charAt(i) |
|||
if (!Character.isDigit(c)) { |
|||
return false |
|||
} |
|||
} |
|||
return true |
|||
} |
|||
private static void validate(String db) { |
|||
int le = db.length() |
|||
int[] found = new int[10_000] |
|||
Arrays.fill(found, 0) |
|||
List<String> errs = new ArrayList<>() |
|||
// Check all strings of 4 consecutive digits within 'db' |
|||
// to see if all 10,000 combinations occur without duplication. |
|||
for (int i = 0; i < le - 3; ++i) { |
|||
String s = db.substring(i, i + 4) |
|||
if (allDigits(s)) { |
|||
int n = Integer.parseInt(s) |
|||
found[n]++ |
|||
} |
|||
} |
|||
for (int i = 0; i < 10_000; ++i) { |
|||
if (found[i] == 0) { |
|||
errs.add(String.format(" PIN number %d is missing", i)) |
|||
} else if (found[i] > 1) { |
|||
errs.add(String.format(" PIN number %d occurs %d times", i, found[i])) |
|||
} |
|||
} |
|||
if (errs.isEmpty()) { |
|||
System.out.println(" No errors found") |
|||
} else { |
|||
String pl = (errs.size() == 1) ? "" : "s" |
|||
System.out.printf(" %d error%s found:\n", errs.size(), pl) |
|||
errs.forEach(System.out.&println) |
|||
} |
|||
} |
|||
static void main(String[] args) { |
|||
String db = deBruijn(10, 4) |
|||
System.out.printf("The length of the de Bruijn sequence is %d\n\n", db.length()) |
|||
System.out.printf("The first 130 digits of the de Bruijn sequence are: %s\n\n", db.substring(0, 130)) |
|||
System.out.printf("The last 130 digits of the de Bruijn sequence are: %s\n\n", db.substring(db.length() - 130)) |
|||
System.out.println("Validating the de Bruijn sequence:") |
|||
validate(db) |
|||
StringBuilder sb = new StringBuilder(db) |
|||
String rdb = sb.reverse().toString() |
|||
System.out.println() |
|||
System.out.println("Validating the de Bruijn sequence:") |
|||
validate(rdb) |
|||
sb = new StringBuilder(db) |
|||
sb.setCharAt(4443, '.' as char) |
|||
System.out.println() |
|||
System.out.println("Validating the overlaid de Bruijn sequence:") |
|||
validate(sb.toString()) |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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 de Bruijn sequence: |
|||
No errors found |
|||
Validating the overlaid de Bruijn sequence: |
|||
4 errors found: |
|||
PIN number 1459 is missing |
|||
PIN number 4591 is missing |
|||
PIN number 5814 is missing |
|||
PIN number 8145 is missing</pre> |
|||
=={{header|Haskell}}== |
|||
=== Permutation-based === |
|||
Straight-forward implementation of inverse Burrows—Wheeler transform [[wp:De_Bruijn_sequence#Construction|De_Bruijn_sequence#Construction] is reasonably efficient for the task (about a milliseconds for B(10,4) in GHCi). |
|||
<syntaxhighlight lang="haskell">import Data.List |
|||
import Data.Map ((!)) |
|||
import qualified Data.Map as M |
|||
-- represents a permutation in a cycle notation |
|||
cycleForm :: [Int] -> [[Int]] |
|||
cycleForm p = unfoldr getCycle $ M.fromList $ zip [0..] p |
|||
where |
|||
getCycle p |
|||
| M.null p = Nothing |
|||
| otherwise = |
|||
let Just ((x,y), m) = M.minViewWithKey p |
|||
c = if x == y then [] else takeWhile (/= x) (iterate (m !) y) |
|||
in Just (c ++ [x], foldr M.delete m c) |
|||
-- the set of Lyndon words generated by inverse Burrows—Wheeler transform |
|||
lyndonWords :: Ord a => [a] -> Int -> [[a]] |
|||
lyndonWords s n = map (ref !!) <$> cycleForm perm |
|||
where |
|||
ref = concat $ replicate (length s ^ (n - 1)) s |
|||
perm = s >>= (`elemIndices` ref) |
|||
-- returns the de Bruijn sequence of order n for an alphabeth s |
|||
deBruijn :: Ord a => [a] -> Int -> [a] |
|||
deBruijn s n = let lw = concat $ lyndonWords n s |
|||
in lw ++ take (n-1) lw</syntaxhighlight> |
|||
<pre>λ> cycleForm [1,4,3,2,0] |
|||
[[1,4,0],[3,2]] |
|||
λ> lyndonWords "ab" 3 |
|||
["a","aab","abb","b"] |
|||
λ> deBruijn "ab" 3 |
|||
"aaababbbaa"</pre> |
|||
The task. |
|||
<syntaxhighlight lang="haskell">import Control.Monad (replicateM) |
|||
main = do |
|||
let symbols = ['0'..'9'] |
|||
let db = deBruijn symbols 4 |
|||
putStrLn $ "The length of de Bruijn sequence: " ++ show (length db) |
|||
putStrLn $ "The first 130 symbols are:\n" ++ show (take 130 db) |
|||
putStrLn $ "The last 130 symbols are:\n" ++ show (drop (length db - 130) db) |
|||
let words = replicateM 4 symbols |
|||
let validate db = filter (not . (`isInfixOf` db)) words |
|||
putStrLn $ "Words not in the sequence: " ++ unwords (validate db) |
|||
let db' = a ++ ('.': tail b) where (a,b) = splitAt 4444 db |
|||
putStrLn $ "Words not in the corrupted sequence: " ++ unwords (validate db') </syntaxhighlight> |
|||
<pre>λ> main |
|||
The length of de Bruijn sequence: 10003 |
|||
The first 130 symbols are: |
|||
"0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350" |
|||
The last 130 symbols are: |
|||
"6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000" |
|||
Words not in the sequence: |
|||
Words not in the corrupted sequence: 1459 4591 5914 8145</pre> |
|||
=== Array-based === |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="haskell">import Control.Monad.State |
|||
import Data.Array (Array, listArray, (!), (//)) |
|||
import qualified Data.Array as A |
|||
deBruijn :: [a] -> Int -> [a] |
|||
deBruijn s n = |
|||
let |
|||
k = length s |
|||
db :: Int -> Int -> State (Array Int Int) [Int] |
|||
db t p = |
|||
if t > n |
|||
then |
|||
if n `mod` p == 0 |
|||
then get >>= \a -> return [ a ! k | k <- [1 .. p]] |
|||
else return [] |
|||
else do |
|||
a <- get |
|||
x <- setArray t (a ! (t-p)) >> db (t+1) p |
|||
a <- get |
|||
y <- sequence [ setArray t j >> db (t+1) t |
|||
| j <- [a ! (t-p) + 1 .. k - 1] ] |
|||
return $ x ++ concat y |
|||
setArray i x = modify (// [(i, x)]) |
|||
seqn = db 1 1 `evalState` listArray (0, k*n-1) (repeat 0) |
|||
in [ s !! i | i <- seqn ++ take (n-1) seqn ]</syntaxhighlight> |
|||
=={{header|J}}== |
|||
definitions. The C. verb computes the cycles. J's sort is a stable sort. |
|||
<syntaxhighlight lang="j">NB. implement inverse Burrows—Wheeler transform sequence method |
|||
repeat_alphabet=: [: , [: i.&> (^ <:) # [ |
|||
assert 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -: 2 repeat_alphabet 4 |
|||
de_bruijn=: ({~ ([: ; [: C. /:^:2))@:repeat_alphabet NB. K de_bruijn N |
|||
pins=: #&10 #: [: i. 10&^ NB. pins y generates all y digit PINs |
|||
groups=: [ ]\ ] , ({.~ <:)~ NB. length x infixes of sequence y cyclically extended by x-1 |
|||
verify_PINs=: (/:~@:groups -: pins@:[) NB. LENGTH verify_PINs SEQUENCE |
|||
</syntaxhighlight>Task<syntaxhighlight lang="j"> NB. A is the sequence |
|||
A=: 10 de_bruijn 4 |
|||
NB. tally A |
|||
#A |
|||
10000 |
|||
NB. literally the first and final 130 digits |
|||
Num_j_ {~ 130 ({. ,: ({.~ -)~) A |
|||
0000101001101111000210020102110202001210120112111202121200221022012211220222122220003100320030103110321030203120322030300131013201 |
|||
9469956996699769986990799179927993799479957996799779987990899189928993899489958996899789988990999199929993999499959996999799989999 |
|||
NB. verifications. seriously? |
|||
4 verify_PINs A |
|||
1 |
|||
4 (verify_PINs |.) A |
|||
1 |
|||
4 verify_PINs (a.i.'.') (<: 4444)} A |
|||
0 |
|||
</syntaxhighlight> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="java">import java.util.ArrayList; |
||
import java.util.Arrays; |
import java.util.Arrays; |
||
import java.util.List; |
import java.util.List; |
||
Line 713: | Line 2,017: | ||
validate(sb.toString()); |
validate(sb.toString()); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The length of the de Bruijn sequence is 10003 |
<pre>The length of the de Bruijn sequence is 10003 |
||
Line 733: | Line 2,037: | ||
PIN number 5814 is missing |
PIN number 5814 is missing |
||
PIN number 8145 is missing</pre> |
PIN number 8145 is missing</pre> |
||
=={{header|jq}}== |
|||
'''Adapted from [[#Wren|Wren]]''' |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
<syntaxhighlight lang="jq"> |
|||
def allDigits: |
|||
all(explode[]; 48 <= . and . <= 57); |
|||
def lpad($len): tostring | ($len - length) as $l | ("0" * $l) + .; |
|||
def deBruijn: |
|||
{deBruijn: ""} |
|||
| reduce range(0; 100) as $n (.; |
|||
($n|lpad(2)) as $a |
|||
| ($a | explode) as [$a1, $a2] |
|||
| if $a2 >= $a1 |
|||
then .deBruijn += (if ($a1 == $a2) then ([$a1]|implode) else $a end) |
|||
| .m = $n + 1 |
|||
| until(.m > 99; |
|||
(.m|lpad(2)) as $ms |
|||
| if ($ms[1:2]|explode[0]) > $a1 |
|||
then .deBruijn += $a + $ms |
|||
end |
|||
| .m += 1 ) |
|||
end ) |
|||
| .deBruijn + "000" ; |
|||
def describe: |
|||
. as $d |
|||
| "de Bruijn sequence length: \($d|length)", |
|||
"First 130 characters:", |
|||
$d[0:130], |
|||
"Last 130 characters:", |
|||
$d[-130:]; |
|||
def check: |
|||
. as $text |
|||
| { res: [], |
|||
found: [range(0;10000) | 0], |
|||
k: 0 } |
|||
| reduce range( 0; $text|length-3) as $i (.; |
|||
$text[$i : $i+4] as $s |
|||
| if ($s|allDigits) |
|||
then .k = ($s|tonumber) |
|||
| .found[.k] += 1 |
|||
end ) |
|||
| reduce range(0; 10000) as $i (.; |
|||
.k = .found[$i] |
|||
| if .k != 1 |
|||
then (" Pin number \($i) " |
|||
+ (if .k == 0 then "missing" else "occurs \(.k) times" end ) ) as $e |
|||
| .res += [$e] |
|||
end ) |
|||
| .k = (.res|length) |
|||
| if .k == 0 |
|||
then .res = "No errors found" |
|||
else |
|||
(if .k == 1 then "" else "s" end) as $s |
|||
| .res = "\(.k) error\($s) found:\n" + (.res | join("\n")) |
|||
end |
|||
| .res ; |
|||
# The tasks |
|||
deBruijn |
|||
| describe, |
|||
"Missing 4 digit PINs in this sequence: \(check)", |
|||
"Missing 4 digit PINs in the reversed sequence: \(explode|reverse|implode|check)", |
|||
"4,444th digit in the sequence: '\(.[4443])' (setting it to '.')", |
|||
( .[0:4443] + "." + .[4444:] |
|||
| "Re-running checks: \(check)" ) |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
de Bruijn sequence length: 10003 |
|||
First 130 characters: |
|||
0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 |
|||
Last 130 characters: |
|||
6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 |
|||
Missing 4 digit PINs in this sequence: No errors found |
|||
Missing 4 digit PINs in the reversed sequence: No errors found |
|||
4,444th digit in the sequence: '4' (setting it to '.') |
|||
Re-running checks: 4 errors found: |
|||
Pin number 1459 missing |
|||
Pin number 4591 missing |
|||
Pin number 5814 missing |
|||
Pin number 8145 missing |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">function debruijn(k::Integer, n::Integer) |
||
alphabet = b"0123456789abcdefghijklmnopqrstuvwxyz"[1:k] |
alphabet = b"0123456789abcdefghijklmnopqrstuvwxyz"[1:k] |
||
a = zeros(UInt8, k * n) |
a = zeros(UInt8, k * n) |
||
Line 780: | Line 2,173: | ||
print("Testing the reversed sequence: "), verifyallPIN(reverse(s), 10, 4) |
print("Testing the reversed sequence: "), verifyallPIN(reverse(s), 10, 4) |
||
println("\nAfter replacing 4444th digit with \'.\':"), verifyallPIN(s, 10, 4, 4444) |
println("\nAfter replacing 4444th digit with \'.\':"), verifyallPIN(s, 10, 4, 4444) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
The length of the sequence is 10003. The first 130 digits are: |
The length of the sequence is 10003. The first 130 digits are: |
||
Line 799: | Line 2,192: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="scala">const val digits = "0123456789" |
||
fun deBruijn(k: Int, n: Int): String { |
fun deBruijn(k: Int, n: Int): String { |
||
Line 892: | Line 2,285: | ||
println("\nValidating the overlaid deBruijn sequence:") |
println("\nValidating the overlaid deBruijn sequence:") |
||
validate(db) |
validate(db) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The length of the de Bruijn sequence is 10003 |
<pre>The length of the de Bruijn sequence is 10003 |
||
Line 912: | Line 2,305: | ||
PIN number 5814 missing |
PIN number 5814 missing |
||
PIN number 8145 missing</pre> |
PIN number 8145 missing</pre> |
||
=={{header|Lua}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="lua">function tprint(tbl) |
|||
for i,v in pairs(tbl) do |
|||
print(v) |
|||
end |
|||
end |
|||
function deBruijn(k, n) |
|||
local a = {} |
|||
for i=1, k*n do |
|||
table.insert(a, 0) |
|||
end |
|||
local seq = {} |
|||
function db(t, p) |
|||
if t > n then |
|||
if n % p == 0 then |
|||
for i=1, p do |
|||
table.insert(seq, a[i + 1]) |
|||
end |
|||
end |
|||
else |
|||
a[t + 1] = a[t - p + 1] |
|||
db(t + 1, p) |
|||
local j = a[t - p + 1] + 1 |
|||
while j < k do |
|||
a[t + 1] = j % 256 |
|||
db(t + 1, t) |
|||
j = j + 1 |
|||
end |
|||
end |
|||
end |
|||
db(1, 1) |
|||
local buf = "" |
|||
for i,v in pairs(seq) do |
|||
buf = buf .. tostring(v) |
|||
end |
|||
return buf .. buf:sub(1, n - 1) |
|||
end |
|||
function allDigits(s) |
|||
return s:match('[0-9]+') == s |
|||
end |
|||
function validate(db) |
|||
local le = string.len(db) |
|||
local found = {} |
|||
local errs = {} |
|||
for i=1, 10000 do |
|||
table.insert(found, 0) |
|||
end |
|||
-- Check all strings of 4 consecutive digits within 'db' |
|||
-- to see if all 10,000 combinations occur without duplication. |
|||
for i=1, le - 3 do |
|||
local s = db:sub(i, i + 3) |
|||
if allDigits(s) then |
|||
local n = tonumber(s) |
|||
found[n + 1] = found[n + 1] + 1 |
|||
end |
|||
end |
|||
local count = 0 |
|||
for i=1, 10000 do |
|||
if found[i] == 0 then |
|||
table.insert(errs, " PIN number " .. (i - 1) .. " missing") |
|||
count = count + 1 |
|||
elseif found[i] > 1 then |
|||
table.insert(errs, " PIN number " .. (i - 1) .. " occurs " .. found[i] .. " times") |
|||
count = count + 1 |
|||
end |
|||
end |
|||
if count == 0 then |
|||
print(" No errors found") |
|||
else |
|||
tprint(errs) |
|||
end |
|||
end |
|||
function main() |
|||
local db = deBruijn(10,4) |
|||
print("The length of the de Bruijn sequence is " .. string.len(db)) |
|||
print() |
|||
io.write("The first 130 digits of the de Bruijn sequence are: ") |
|||
print(db:sub(0, 130)) |
|||
print() |
|||
io.write("The last 130 digits of the de Bruijn sequence are: ") |
|||
print(db:sub(-130)) |
|||
print() |
|||
print("Validating the de Bruijn sequence:") |
|||
validate(db) |
|||
print() |
|||
print("Validating the reversed de Bruijn sequence:") |
|||
validate(db:reverse()) |
|||
print() |
|||
db = db:sub(1,4443) .. "." .. db:sub(4445) |
|||
print("Validating the overlaid de Bruijn sequence:") |
|||
validate(db) |
|||
print() |
|||
end |
|||
main()</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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: |
|||
PIN number 1459 missing |
|||
PIN number 4591 missing |
|||
PIN number 5814 missing |
|||
PIN number 8145 missing</pre> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">seq = DeBruijnSequence[Range[0, 9], 4]; |
|||
seq = seq~Join~Take[seq, 3]; |
|||
Length[seq] |
|||
{seq[[;; 130]], seq[[-130 ;;]]} |
|||
Complement[ |
|||
StringDrop[ToString[NumberForm[#, 4, NumberPadding -> {"0", "0"}]], |
|||
1] & /@ Range[0, 9999], |
|||
Union[StringJoin /@ Partition[ToString /@ seq, 4, 1]]] |
|||
seq = Reverse[seq]; |
|||
Complement[ |
|||
StringDrop[ToString[NumberForm[#, 4, NumberPadding -> {"0", "0"}]], |
|||
1] & /@ Range[0, 9999], |
|||
Union[StringJoin /@ Partition[ToString /@ seq, 4, 1]]] |
|||
seq[[4444]] = "."; |
|||
Complement[ |
|||
StringDrop[ToString[NumberForm[#, 4, NumberPadding -> {"0", "0"}]], |
|||
1] & /@ Range[0, 9999], |
|||
Union[StringJoin /@ Partition[ToString /@ seq, 4, 1]]]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>10003 |
|||
{{0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 4, 0, 0, 0, 5, 0, 0, |
|||
0, 6, 0, 0, 0, 7, 0, 0, 0, 8, 0, 0, 0, 9, 0, 0, 1, 1, 0, 0, 1, 2, |
|||
0, 0, 1, 3, 0, 0, 1, 4, 0, 0, 1, 5, 0, 0, 1, 6, 0, 0, 1, 7, 0, 0, 1, |
|||
8, 0, 0, 1, 9, 0, 0, 2, 1, 0, 0, 2, 2, 0, 0, 2, 3, 0, 0, 2, 4, 0, |
|||
0, 2, 5, 0, 0, 2, 6, 0, 0, 2, 7, 0, 0, 2, 8, 0, 0, 2, 9, 0, 0, 3, 1, |
|||
0, 0, 3, 2, 0, 0, 3, 3, 0, 0, 3, 4, 0, 0, 3, 5, 0}, {6, 8, 9, 8, 6, |
|||
8, 9, 9, 6, 9, 6, 9, 7, 7, 6, 9, 7, 8, 6, 9, 7, 9, 6, 9, 8, 7, 6, |
|||
9, 8, 8, 6, 9, 8, 9, 6, 9, 9, 7, 6, 9, 9, 8, 6, 9, 9, 9, 7, 7, 7, 7, |
|||
8, 7, 7, 7, 9, 7, 7, 8, 8, 7, 7, 8, 9, 7, 7, 9, 8, 7, 7, 9, 9, 7, |
|||
8, 7, 8, 7, 9, 7, 8, 8, 8, 7, 8, 8, 9, 7, 8, 9, 8, 7, 8, 9, 9, 7, 9, |
|||
7, 9, 8, 8, 7, 9, 8, 9, 7, 9, 9, 8, 7, 9, 9, 9, 8, 8, 8, 8, 9, 8, |
|||
8, 9, 9, 8, 9, 8, 9, 9, 9, 9, 0, 0, 0}} |
|||
{} |
|||
{} |
|||
{"1478", "4781", "7813", "8137"}</pre> |
|||
=={{header|Nim}}== |
|||
{{trans|D}} |
|||
<syntaxhighlight lang="nim">import algorithm, parseutils, strformat, strutils |
|||
const Digits = "0123456789" |
|||
#--------------------------------------------------------------------------------------------------- |
|||
func deBruijn(k, n: int): string = |
|||
let alphabet = Digits[0..<k] |
|||
var a = newSeq[byte](k * n) |
|||
var sequence: seq[byte] |
|||
#................................................................................................. |
|||
func db(t, p: int) = |
|||
if t > n: |
|||
if n mod p == 0: |
|||
sequence &= a[1..p] |
|||
else: |
|||
a[t] = a[t - p] |
|||
db(t + 1, p) |
|||
var j = a[t - p] + 1 |
|||
while j < k.uint: |
|||
a[t] = j |
|||
db(t + 1, t) |
|||
inc j |
|||
#............................................................................................... |
|||
db(1, 1) |
|||
for i in sequence: |
|||
result &= alphabet[i] |
|||
result &= result[0..(n-2)] |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc validate(db: string) = |
|||
var found: array[10_000, int] |
|||
var errs: seq[string] |
|||
## Check all strings of 4 consecutive digits within 'db' |
|||
## to see if all 10,000 combinations occur without duplication. |
|||
for i in 0..(db.len - 4): |
|||
let s = db[i..(i+3)] |
|||
var n: int |
|||
if s.parseInt(n) == 4: |
|||
inc found[n] |
|||
for n, count in found: |
|||
if count == 0: |
|||
errs &= fmt" PIN number {n:04d} missing" |
|||
elif count > 1: |
|||
errs &= fmt" PIN number {n:04d} occurs {count} times" |
|||
if errs.len == 0: |
|||
echo " No errors found" |
|||
else: |
|||
let plural = if errs.len == 1: "" else: "s" |
|||
echo fmt" {errs.len} error{plural} found" |
|||
for err in errs: echo err |
|||
#——————————————————————————————————————————————————————————————————————————————————————————————————— |
|||
var db = deBruijn(10, 4) |
|||
echo fmt"The length of the de Bruijn sequence is {db.len}" |
|||
echo "" |
|||
echo fmt"The first 130 digits of the de Bruijn sequence are: {db[0..129]}" |
|||
echo "" |
|||
echo fmt"The last 130 digits of the de Bruijn sequence are: {db[^130..^1]}" |
|||
echo "" |
|||
echo "Validating the deBruijn sequence:" |
|||
db.validate() |
|||
echo "" |
|||
echo "Validating the reversed deBruijn sequence:" |
|||
reversed(db).join().validate() |
|||
echo "" |
|||
db[4443] = '.' |
|||
echo "Validating the overlaid deBruijn sequence:" |
|||
db.validate()</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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 deBruijn sequence: |
|||
No errors found |
|||
Validating the reversed deBruijn sequence: |
|||
No errors found |
|||
Validating the overlaid deBruijn sequence: |
|||
4 errors found |
|||
PIN number 1459 missing |
|||
PIN number 4591 missing |
|||
PIN number 5814 missing |
|||
PIN number 8145 missing</pre> |
|||
=={{header|Pascal}}== |
|||
A console application in Free Pascal, created with the Lazarus IDE. |
|||
For a given word length n, constructs a de Bruijn sequence by concatenating, in lexicographic order, all the Lyndon words whose length divides n. (See Wikipedia article "de Bruijn sequence", section "Construction".) |
|||
<syntaxhighlight lang="pascal"> |
|||
program deBruijnSequence; |
|||
uses SysUtils; |
|||
// Create a de Bruijn sequence for the given word length and alphabet. |
|||
function deBruijn( const n : integer; // word length |
|||
const alphabet : string) : string; |
|||
var |
|||
d, k, m, s, t, seqLen : integer; |
|||
w : array of integer; |
|||
begin |
|||
k := Length( alphabet); |
|||
// de Bruijn sequence will have length k^n |
|||
seqLen := 1; |
|||
for t := 1 to n do seqLen := seqLen*k; |
|||
SetLength( result, seqLen); |
|||
d := 0; // index into de Bruijn sequence (will be pre-inc'd) |
|||
// Work through Lyndon words of length <= n, in lexicographic order. |
|||
SetLength( w, n); // w holds array of indices into the alphabet |
|||
w[0] := 1; // first Lyndon word |
|||
m := 1; // m = length of Lyndon word |
|||
repeat |
|||
// If m divides n, append the current Lyndon word to the output |
|||
if (m = n) or (m = 1) or (n mod m = 0) then begin |
|||
for t := 0 to m - 1 do begin |
|||
inc(d); |
|||
result[d] := alphabet[w[t]]; |
|||
end; |
|||
end; |
|||
// Get next Lyndon word using Duval's algorithm: |
|||
// (1) Fill w with repetitions of current word |
|||
s := 0; t := m; |
|||
while (t < n) do begin |
|||
w[t] := w[s]; |
|||
inc(t); inc(s); |
|||
if s = m then s := 0; |
|||
end; |
|||
// (2) Repeatedly delete highest index k from end of w, if present |
|||
m := n; |
|||
while (m > 0) and (w[m - 1] = k) do dec(m); |
|||
// (3) If word is now null, stop; else increment end value |
|||
if m > 0 then inc( w[m - 1]); |
|||
until m = 0; |
|||
Assert( d = seqLen); // check that the sequence is exactly filled in |
|||
end; |
|||
// Check a de Bruijn sequence, assuming that its alphabet consists |
|||
// of the digits '0'..'9' (in any order); |
|||
procedure CheckDecimal( const n : integer; // word length |
|||
const deB : string); |
|||
var |
|||
count : array of integer; |
|||
j, L, pin, nrErrors : integer; |
|||
wrap : string; |
|||
begin |
|||
L := Length( deB); |
|||
// The de Bruijn sequence is cyclic; make an array to handle wrapround. |
|||
SetLength( wrap, 2*n - 2); |
|||
for j := 1 to n - 1 do wrap[j] := deB[L + j - n + 1]; |
|||
for j := n to 2*n - 2 do wrap[j] := deB[j - n + 1]; |
|||
// Count occurrences of each PIN. |
|||
// PIN = -1 if character is not a decimal digit. |
|||
SetLength( count, L); |
|||
for j := 0 to L - 1 do count[L] := 0; |
|||
for j := 1 to L - n + 1 do begin |
|||
pin := SysUtils.StrToIntDef( Copy( deB, j, n), -1); |
|||
if pin >= 0 then inc( count[pin]); |
|||
end; |
|||
for j := 1 to n - 1 do begin |
|||
pin := SysUtils.StrToIntDef( Copy( wrap, j, n), -1); |
|||
if pin >= 0 then inc( count[pin]); |
|||
end; |
|||
// Check that all counts are 1 |
|||
nrErrors := 0; |
|||
for j := 0 to L - 1 do begin |
|||
if count[j] <> 1 then begin |
|||
inc( nrErrors); |
|||
WriteLn( SysUtils.Format( ' PIN %d has count %d', [j, count[j]])); |
|||
end; |
|||
end; |
|||
WriteLn( SysUtils.Format( ' Number of errors = %d', [nrErrors])); |
|||
end; |
|||
// Main routine |
|||
var |
|||
deB, rev : string; |
|||
L, j : integer; |
|||
begin |
|||
deB := deBruijn( 4, '0123456789'); |
|||
// deB := deBruijn( 4, '7368290514'); // any permutation would do |
|||
L := Length( deB); |
|||
WriteLn( SysUtils.Format( 'Length of de Bruijn sequence = %d', [L])); |
|||
if L >= 260 then begin |
|||
WriteLn; |
|||
WriteLn( 'First and last 130 characters are:'); |
|||
WriteLn( Copy( deB, 1, 65)); |
|||
WriteLn( Copy( deb, 66, 65)); |
|||
WriteLn( '...'); |
|||
WriteLn( Copy( deB, L - 129, 65)); |
|||
WriteLn( Copy( deB, L - 64, 65)); |
|||
end; |
|||
WriteLn; |
|||
WriteLn( 'Checking de Bruijn sequence:'); |
|||
CheckDecimal( 4, deB); |
|||
// Check reversed sequence |
|||
SetLength( rev, L); |
|||
for j := 1 to L do rev[j] := deB[L + 1 - j]; |
|||
WriteLn( 'Checking reversed sequence:'); |
|||
CheckDecimal( 4, rev); |
|||
// Check sequence with '.' instad of decimal digit |
|||
if L >= 4444 then begin |
|||
deB[4444] := '.'; |
|||
WriteLn( 'Checking vandalized sequence:'); |
|||
CheckDecimal( 4, deB); |
|||
end; |
|||
end. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Length of de Bruijn sequence = 10000 |
|||
First and last 130 characters are: |
|||
00001000200030004000500060007000800090011001200130014001500160017 |
|||
00180019002100220023002400250026002700280029003100320033003400350 |
|||
... |
|||
89768986899696977697869796987698869896997699869997777877797788778 |
|||
97798779978787978887889789878997979887989799879998888988998989999 |
|||
Checking de Bruijn sequence: |
|||
Number of errors = 0 |
|||
Checking reversed sequence: |
|||
Number of errors = 0 |
|||
Checking vandalized sequence: |
|||
PIN 1459 has count 0 |
|||
PIN 4591 has count 0 |
|||
PIN 5814 has count 0 |
|||
PIN 8145 has count 0 |
|||
Number of errors = 4 |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use feature 'say'; |
use feature 'say'; |
||
Line 952: | Line 2,765: | ||
substr $seq, 4443, 1, 5; |
substr $seq, 4443, 1, 5; |
||
say "Incorrect 4 digit PINs in the revised sequence:"; |
say "Incorrect 4 digit PINs in the revised sequence:"; |
||
check $seq;</ |
check $seq;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>de Bruijn sequence length: 10003 |
<pre>de Bruijn sequence length: 10003 |
||
Line 978: | Line 2,791: | ||
{{trans|zkl}} |
{{trans|zkl}} |
||
{{trans|Go}} |
{{trans|Go}} |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>string deBruijn = "" |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">deBruijn</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span> |
|||
for n=0 to 99 do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">99</span> <span style="color: #008080;">do</span> |
|||
string a = sprintf("%02d",n) |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%02d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
integer {a1,a2} = a |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">a1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> |
|||
if a2>=a1 then |
|||
<span style="color: #000000;">a2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> |
|||
deBruijn &= iff(a1=a2?a1:a) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">a2</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">a1</span> <span style="color: #008080;">then</span> |
|||
for m=n+1 to 99 do |
|||
<span style="color: #000000;">deBruijn</span> <span style="color: #0000FF;">&=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a1</span><span style="color: #0000FF;">=</span><span style="color: #000000;">a2</span><span style="color: #0000FF;">?</span><span style="color: #000000;">a1</span><span style="color: #0000FF;">:</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
string ms = sprintf("%02d",m) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">99</span> <span style="color: #008080;">do</span> |
|||
if ms[2]>a1 then |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">ms</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%02d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> |
|||
deBruijn &= a&ms |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">ms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]></span><span style="color: #000000;">a1</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #000000;">deBruijn</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">&</span><span style="color: #000000;">ms</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
deBruijn &= "000" |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
printf(1,"de Bruijn sequence length: %d\n\n",length(deBruijn)) |
|||
<span style="color: #000000;">deBruijn</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">"000"</span> |
|||
printf(1,"First 130 characters:\n%s\n\n",deBruijn[1..130]) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"de Bruijn sequence length: %d\n\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">deBruijn</span><span style="color: #0000FF;">))</span> |
|||
printf(1,"Last 130 characters:\n%s\n\n",deBruijn[-130..-1]) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"First 130 characters:\n%s\n\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">deBruijn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">130</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Last 130 characters:\n%s\n\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">deBruijn</span><span style="color: #0000FF;">[-</span><span style="color: #000000;">130</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> |
|||
function check(string text) |
|||
sequence res = {} |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">check</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">text</span><span style="color: #0000FF;">)</span> |
|||
sequence found = repeat(0,10000) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
integer k |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10000</span><span style="color: #0000FF;">)</span> |
|||
for i=1 to length(text)-3 do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> |
|||
k = to_integer(text[i..i+3],-1)+1 |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">text</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">3</span> <span style="color: #008080;">do</span> |
|||
if k!=0 then found[k] += 1 end if |
|||
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">to_integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">text</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">3</span><span style="color: #0000FF;">],-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span> |
|||
end for |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">found</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
for i=1 to 10000 do |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
k = found[i] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10000</span> <span style="color: #008080;">do</span> |
|||
if k!=1 then |
|||
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">found</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
string e = sprintf("Pin number %04d ",i-1) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
|||
e &= iff(k=0?"missing":sprintf("occurs %d times",k)) |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"Pin number %04d "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
res = append(res,e) |
|||
<span style="color: #000000;">e</span> <span style="color: #0000FF;">&=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"missing"</span><span style="color: #0000FF;">:</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"occurs %d times"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">))</span> |
|||
end if |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
k = length(res) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
if k=0 then |
|||
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> |
|||
res = "No errors found" |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
else |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"No errors found"</span> |
|||
string s = iff(k=1?"":"s") |
|||
<span style="color: #008080;">else</span> |
|||
res = sprintf("%d error%s found:\n ",{k,s})&join(res,"\n ") |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #008000;">""</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"s"</span><span style="color: #0000FF;">)</span> |
|||
end if |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d error%s found:\n "</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">})&</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n "</span><span style="color: #0000FF;">)</span> |
|||
return res |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
printf(1,"Missing 4 digit PINs in this sequence: %s\n", check(deBruijn)) |
|||
printf(1,"Missing 4 digit PINs in the reversed sequence: %s\n",check(reverse(deBruijn))) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Missing 4 digit PINs in this sequence: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">check</span><span style="color: #0000FF;">(</span><span style="color: #000000;">deBruijn</span><span style="color: #0000FF;">))</span> |
|||
printf(1,"4444th digit in the sequence: %c (setting it to .)\n", deBruijn[4444]) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Missing 4 digit PINs in the reversed sequence: %s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">check</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">deBruijn</span><span style="color: #0000FF;">)))</span> |
|||
deBruijn[4444] = '.' |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"4444th digit in the sequence: %c (setting it to .)\n"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">deBruijn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">4444</span><span style="color: #0000FF;">])</span> |
|||
printf(1,"Re-running checks: %s\n",check(deBruijn))</lang> |
|||
<span style="color: #000000;">deBruijn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">4444</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'.'</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Re-running checks: %s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">check</span><span style="color: #0000FF;">(</span><span style="color: #000000;">deBruijn</span><span style="color: #0000FF;">))</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,049: | Line 2,865: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python"> |
||
# from https://en.wikipedia.org/wiki/De_Bruijn_sequence |
# from https://en.wikipedia.org/wiki/De_Bruijn_sequence |
||
Line 1,141: | Line 2,957: | ||
print("Validating the overlaid deBruijn sequence:") |
print("Validating the overlaid deBruijn sequence:") |
||
validate(dboverlaid) |
validate(dboverlaid) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,168: | Line 2,984: | ||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(define (de-bruijn k n) |
(define (de-bruijn k n) |
||
Line 1,213: | Line 3,029: | ||
(validate "" seq) |
(validate "" seq) |
||
(validate "reversed " (reverse seq)) |
(validate "reversed " (reverse seq)) |
||
(validate "overlaid " (list-update seq 4443 add1))</ |
(validate "overlaid " (list-update seq 4443 add1))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,244: | Line 3,060: | ||
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. |
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 |
<syntaxhighlight lang="raku" line># Generate the sequence |
||
my $seq; |
my $seq; |
||
Line 1,285: | Line 3,101: | ||
put "Incorrect 4 digit PINs in the revised sequence:"; |
put "Incorrect 4 digit PINs in the revised sequence:"; |
||
$seq.substr-rw(4443,1) = $digit; |
$seq.substr-rw(4443,1) = $digit; |
||
check $seq;</ |
check $seq;</syntaxhighlight> |
||
{{out|Sample output}} |
{{out|Sample output}} |
||
<pre>de Bruijn sequence length: 10003 |
<pre>de Bruijn sequence length: 10003 |
||
Line 1,311: | Line 3,127: | ||
The de Bruijn sequence generated by these REXX programs are identical to the sequence shown on the ''discussion'' page (1<sup>st</sup> topic). |
The de Bruijn sequence generated by these REXX programs are identical to the sequence shown on the ''discussion'' page (1<sup>st</sup> topic). |
||
=== hard-coded node to be removed === |
=== hard-coded node to be removed === |
||
< |
<syntaxhighlight lang="rexx">/*REXX pgm calculates the de Bruijn sequence for all pin numbers (4 digit decimals). */ |
||
$= /*initialize the de Bruijn sequence. */ |
$= /*initialize the de Bruijn sequence. */ |
||
#=10; lastNode= (#-2)(#-2)(#-1)(#-2) /*this number is formed when this # ···*/ |
#=10; lastNode= (#-2)(#-2)(#-1)(#-2) /*this number is formed when this # ···*/ |
||
Line 1,358: | Line 3,174: | ||
if e==0 then e= 'No' /*Gooder English (sic) the error count.*/ |
if e==0 then e= 'No' /*Gooder English (sic) the error count.*/ |
||
say _ e 'errors found.' /*display the number of errors found. */ |
say _ e 'errors found.' /*display the number of errors found. */ |
||
return</ |
return</syntaxhighlight> |
||
{{out|output}} |
{{out|output}} |
||
<pre> |
<pre> |
||
Line 1,387: | Line 3,203: | ||
This method slightly bloats the program and slows execution. |
This method slightly bloats the program and slows execution. |
||
< |
<syntaxhighlight lang="rexx">/*REXX pgm calculates the de Bruijn sequence for all pin numbers (4 digit decimals). */ |
||
$= /*initialize the de Bruijn sequence. */ |
$= /*initialize the de Bruijn sequence. */ |
||
do j=0 for 10; $= $ j; jj= j || j /*compose the left half of the numbers.*/ |
do j=0 for 10; $= $ j; jj= j || j /*compose the left half of the numbers.*/ |
||
Line 1,434: | Line 3,250: | ||
if e==0 then e= 'No' /*Gooder English (sic) the error count.*/ |
if e==0 then e= 'No' /*Gooder English (sic) the error count.*/ |
||
say _ e 'errors found.' /*display the number of errors found. */ |
say _ e 'errors found.' /*display the number of errors found. */ |
||
return</ |
return</syntaxhighlight> |
||
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br> |
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br> |
||
=={{header|Ruby}}== |
|||
{{trans|D}} |
|||
<syntaxhighlight lang="ruby">def deBruijn(k, n) |
|||
alphabet = "0123456789" |
|||
@a = Array.new(k * n, 0) |
|||
@seq = [] |
|||
def db(k, n, t, p) |
|||
if t > n then |
|||
if n % p == 0 then |
|||
temp = @a[1 .. p] |
|||
@seq.concat temp |
|||
end |
|||
else |
|||
@a[t] = @a[t - p] |
|||
db(k, n, t + 1, p) |
|||
j = @a[t - p] + 1 |
|||
while j < k do |
|||
@a[t] = j # & 0xFF |
|||
db(k, n, t + 1, t) |
|||
j = j + 1 |
|||
end |
|||
end |
|||
end |
|||
db(k, n, 1, 1) |
|||
buf = "" |
|||
for i in @seq |
|||
buf <<= alphabet[i] |
|||
end |
|||
return buf + buf[0 .. n-2] |
|||
end |
|||
def validate(db) |
|||
le = db.length |
|||
found = Array.new(10000, 0) |
|||
errs = [] |
|||
# Check all strings of 4 consecutive digits within 'db' |
|||
# to see if all 10,000 combinations occur without duplication. |
|||
for i in 0 .. le-4 |
|||
s = db[i .. i+3] |
|||
if s.scan(/\D/).empty? then |
|||
found[s.to_i] += 1 |
|||
end |
|||
end |
|||
for i in 0 .. found.length - 1 |
|||
if found[i] == 0 then |
|||
errs <<= (" PIN number %04d missing" % [i]) |
|||
elsif found[i] > 1 then |
|||
errs <<= (" PIN number %04d occurs %d times" % [i, found[i]]) |
|||
end |
|||
end |
|||
if errs.length == 0 then |
|||
print " No errors found\n" |
|||
else |
|||
pl = (errs.length == 1) ? "" : "s" |
|||
print " ", errs.length, " error", pl, " found:\n" |
|||
for err in errs |
|||
print err, "\n" |
|||
end |
|||
end |
|||
end |
|||
db = deBruijn(10, 4) |
|||
print "The length of the de Bruijn sequence is ", db.length, "\n\n" |
|||
print "The first 130 digits of the de Bruijn sequence are: ", db[0 .. 129], "\n\n" |
|||
print "The last 130 digits of the de Bruijn sequence are: ", db[-130 .. db.length], "\n\n" |
|||
print "Validating the de Bruijn sequence:\n" |
|||
validate(db) |
|||
print "\n" |
|||
db[4443] = '.' |
|||
print "Validating the overlaid de Bruijn sequence:\n" |
|||
validate(db)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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 overlaid de Bruijn sequence: |
|||
4 errors found: |
|||
PIN number 1459 missing |
|||
PIN number 4591 missing |
|||
PIN number 5814 missing |
|||
PIN number 8145 missing</pre> |
|||
=={{header|Scala}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="Scala"> |
|||
import scala.collection.mutable.ListBuffer |
|||
object DeBruijn { |
|||
def deBruijn(k: Int, n: Int): String = { |
|||
val a = Array.fill[Byte](k * n)(0) |
|||
val seq = new ListBuffer[Byte]() |
|||
def db(t: Int, p: Int): Unit = { |
|||
if (t > n) { |
|||
if (n % p == 0) { |
|||
seq ++= a.slice(1, p + 1) |
|||
} |
|||
} else { |
|||
a(t) = a(t - p) |
|||
db(t + 1, p) |
|||
for (j <- (a(t - p) + 1).until(k)) { |
|||
a(t) = j.toByte |
|||
db(t + 1, t) |
|||
} |
|||
} |
|||
} |
|||
db(1, 1) |
|||
val sb = new StringBuilder |
|||
seq.foreach(i => sb.append("0123456789".charAt(i))) |
|||
sb.append(sb.subSequence(0, n - 1)).toString |
|||
} |
|||
private def allDigits(s: String): Boolean = s.forall(_.isDigit) |
|||
private def validate(db: String): Unit = { |
|||
val found = Array.fill(10000)(0) |
|||
val errs = ListBuffer[String]() |
|||
for (i <- 0 until db.length - 3) { |
|||
val s = db.substring(i, i + 4) |
|||
if (allDigits(s)) { |
|||
val n = s.toInt |
|||
found(n) += 1 |
|||
} |
|||
} |
|||
for (i <- found.indices) { |
|||
if (found(i) == 0) errs += s" PIN number $i is missing" |
|||
else if (found(i) > 1) errs += s" PIN number $i occurs ${found(i)} times" |
|||
} |
|||
if (errs.isEmpty) println(" No errors found") |
|||
else { |
|||
val pl = if (errs.size == 1) "" else "s" |
|||
println(s" ${errs.size} error$pl found:") |
|||
errs.foreach(println) |
|||
} |
|||
} |
|||
def main(args: Array[String]): Unit = { |
|||
val db = deBruijn(10, 4) |
|||
println(s"The length of the de Bruijn sequence is ${db.length}\n") |
|||
println(s"The first 130 digits of the de Bruijn sequence are: ${db.take(130)}\n") |
|||
println(s"The last 130 digits of the de Bruijn sequence are: ${db.takeRight(130)}\n") |
|||
println("Validating the de Bruijn sequence:") |
|||
validate(db) |
|||
println() |
|||
println("Validating the reversed de Bruijn sequence:") |
|||
validate(db.reverse) |
|||
val overlaidDb = db.updated(4443, '.') |
|||
println() |
|||
println("Validating the overlaid de Bruijn sequence:") |
|||
validate(overlaidDb) |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 is missing |
|||
PIN number 4591 is missing |
|||
PIN number 5814 is missing |
|||
PIN number 8145 is missing |
|||
</pre> |
|||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="vbnet">Imports System.Text |
||
Module Module1 |
Module Module1 |
||
Line 1,542: | Line 3,555: | ||
End Sub |
End Sub |
||
End Module</ |
End Module</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 |
<pre>The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 |
||
Line 1,560: | Line 3,573: | ||
PIN number 5814 missing |
PIN number 5814 missing |
||
PIN number 8145 missing</pre> |
PIN number 8145 missing</pre> |
||
=={{header|Wren}}== |
|||
{{trans|Phix}} |
|||
{{libheader|Wren-fmt}} |
|||
{{libheader|Wren-str}} |
|||
<syntaxhighlight lang="wren">import "./fmt" for Fmt |
|||
import "./str" for Str |
|||
var deBruijn = "" |
|||
for (n in 0..99) { |
|||
var a = Fmt.rjust(2, n, "0") |
|||
var a1 = a[0].bytes[0] |
|||
var a2 = a[1].bytes[0] |
|||
if (a2 >= a1) { |
|||
deBruijn = deBruijn + ((a1 == a2) ? String.fromByte(a1): a) |
|||
var m = n + 1 |
|||
while (m <= 99) { |
|||
var ms = Fmt.rjust(2, m, "0") |
|||
if (ms[1].bytes[0] > a1) deBruijn = deBruijn + a + ms |
|||
m = m + 1 |
|||
} |
|||
} |
|||
} |
|||
deBruijn = deBruijn + "000" |
|||
System.print("de Bruijn sequence length: %(deBruijn.count)\n") |
|||
System.print("First 130 characters:\n%(deBruijn[0...130])\n") |
|||
System.print("Last 130 characters:\n%(deBruijn[-130..-1])\n") |
|||
var check = Fn.new { |text| |
|||
var res = [] |
|||
var found = List.filled(10000, 0) |
|||
var k = 0 |
|||
for (i in 0...(text.count-3)) { |
|||
var s = text[i..i+3] |
|||
if (Str.allDigits(s)) { |
|||
k = Num.fromString(s) |
|||
found[k] = found[k] + 1 |
|||
} |
|||
} |
|||
for (i in 0...10000) { |
|||
k = found[i] |
|||
if (k != 1) { |
|||
var e = " Pin number %(Fmt.dz(4, i)) " |
|||
e = e + ((k == 0) ? "missing" : "occurs %(k) times") |
|||
res.add(e) |
|||
} |
|||
} |
|||
k = res.count |
|||
if (k == 0) { |
|||
res = "No errors found" |
|||
} else { |
|||
var s = (k == 1) ? "" : "s" |
|||
res = "%(k) error%(s) found:\n" + res.join("\n") |
|||
} |
|||
return res |
|||
} |
|||
System.print("Missing 4 digit PINs in this sequence: %(check.call(deBruijn))") |
|||
System.print("Missing 4 digit PINs in the reversed sequence: %(check.call(deBruijn[-1..0]))") |
|||
System.print("\n4,444th digit in the sequence: '%(deBruijn[4443])' (setting it to '.')") |
|||
deBruijn = deBruijn[0..4442] + "." + deBruijn[4444..-1] |
|||
System.print("Re-running checks: %(check.call(deBruijn))")</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
de Bruijn sequence length: 10003 |
|||
First 130 characters: |
|||
0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 |
|||
Last 130 characters: |
|||
6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 |
|||
Missing 4 digit PINs in this sequence: No errors found |
|||
Missing 4 digit PINs in the reversed sequence: No errors found |
|||
4,444th digit in the sequence: '4' (setting it to '.') |
|||
Re-running checks: 4 errors found: |
|||
Pin number 1459 missing |
|||
Pin number 4591 missing |
|||
Pin number 5814 missing |
|||
Pin number 8145 missing |
|||
</pre> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans| |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="zkl">dbSeq:=Data(); // a byte/character buffer |
||
foreach n in (100){ |
foreach n in (100){ |
||
a,a01,a11 := "%02d".fmt(n), a[0,1], a[1,1]; |
a,a01,a11 := "%02d".fmt(n), a[0,1], a[1,1]; |
||
Line 1,573: | Line 3,671: | ||
} |
} |
||
} |
} |
||
dbSeq.append("000");</ |
dbSeq.append("000");</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">seqText:=dbSeq.text; |
||
println("de Bruijn sequence length: ",dbSeq.len()); |
println("de Bruijn sequence length: ",dbSeq.len()); |
||
Line 1,590: | Line 3,688: | ||
println("\n4444th digit in the sequence: ", seqText[4443]); |
println("\n4444th digit in the sequence: ", seqText[4443]); |
||
dbSeq[4443]="."; |
dbSeq[4443]="."; |
||
println("Setting the 4444th digit and reruning checks: ",chk(dbSeq.text).concat(" "));</ |
println("Setting the 4444th digit and reruning checks: ",chk(dbSeq.text).concat(" "));</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Latest revision as of 05:07, 23 July 2024
You are encouraged to solve this task according to the task description, using any language you may know.
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 teller 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 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.
- Metrics
- Counting
- Word frequency
- Letter frequency
- Jewels and stones
- I before E except after C
- Bioinformatics/base count
- Count occurrences of a substring
- Count how many vowels and consonants occur in a string
- Remove/replace
- XXXX redacted
- Conjugate a Latin verb
- Remove vowels from a string
- String interpolation (included)
- Strip block comments
- Strip comments from a string
- Strip a set of characters from a string
- Strip whitespace from a string -- top and tail
- Strip control codes and extended characters from a string
- Anagrams/Derangements/shuffling
- Word wheel
- ABC problem
- Sattolo cycle
- Knuth shuffle
- Ordered words
- Superpermutation minimisation
- Textonyms (using a phone text pad)
- Anagrams
- Anagrams/Deranged anagrams
- Permutations/Derangements
- Find/Search/Determine
- ABC words
- Odd words
- Word ladder
- Semordnilap
- Word search
- Wordiff (game)
- String matching
- Tea cup rim text
- Alternade words
- Changeable words
- State name puzzle
- String comparison
- Unique characters
- Unique characters in each string
- Extract file extension
- Levenshtein distance
- Palindrome detection
- Common list elements
- Longest common suffix
- Longest common prefix
- Compare a list of strings
- Longest common substring
- Find common directory path
- Words from neighbour ones
- Change e letters to i in words
- Non-continuous subsequences
- Longest common subsequence
- Longest palindromic substrings
- Longest increasing subsequence
- Words containing "the" substring
- Sum of the digits of n is substring of n
- Determine if a string is numeric
- Determine if a string is collapsible
- Determine if a string is squeezable
- Determine if a string has all unique characters
- Determine if a string has all the same characters
- Longest substrings without repeating characters
- Find words which contains all the vowels
- Find words which contain the most consonants
- Find words which contains more than 3 vowels
- Find words whose first and last three letters are equal
- Find words with alternating vowels and consonants
- Formatting
- Substring
- Rep-string
- Word wrap
- String case
- Align columns
- Literals/String
- Repeat a string
- Brace expansion
- Brace expansion using ranges
- Reverse a string
- Phrase reversals
- Comma quibbling
- Special characters
- String concatenation
- Substring/Top and tail
- Commatizing numbers
- Reverse words in a string
- Suffixation of decimal numbers
- Long literals, with continuations
- Numerical and alphabetical suffixes
- Abbreviations, easy
- Abbreviations, simple
- Abbreviations, automatic
- Song lyrics/poems/Mad Libs/phrases
- Mad Libs
- Magic 8-ball
- 99 bottles of beer
- The Name Game (a song)
- The Old lady swallowed a fly
- The Twelve Days of Christmas
- Tokenize
- Text between
- Tokenize a string
- Word break problem
- Tokenize a string with escaping
- Split a character string based on change of character
- Sequences
- 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.
11l
V digits = ‘0123456789’
F deBruijn(k, n)
V alphabet = :digits[0 .< k]
V a = [Byte(0)] * (k * n)
[Byte] seq
F db(Int t, Int p) -> Void
I t > @n
I @n % p == 0
@seq.extend(@a[1 .< p + 1])
E
@a[t] = @a[t - p]
@db(t + 1, p)
V j = @a[t - p] + 1
L j < @k
@a[t] = j [&] F'F
@db(t + 1, t)
j++
db(1, 1)
V buf = ‘’
L(i) seq
buf ‘’= alphabet[i]
R buf‘’buf[0 .< n - 1]
F validate(db)
V found = [0] * 10'000
[String] errs
L(i) 0 .< db.len - 3
V s = db[i .< i + 4]
I s.is_digit()
found[Int(s)]++
L(i) 10'000
I found[i] == 0
errs [+]= ‘ PIN number #04 missing’.format(i)
E I found[i] > 1
errs [+]= ‘ PIN number #04 occurs #. times’.format(i, found[i])
I errs.empty
print(‘ No errors found’)
E
V pl = I errs.len == 1 {‘’} E ‘s’
print(‘ ’String(errs.len)‘ error’pl‘ found:’)
L(err) errs
print(err)
V db = deBruijn(10, 4)
print(‘The length of the de Bruijn sequence is ’db.len)
print("\nThe first 130 digits of the de Bruijn sequence are: "db[0.<130])
print("\nThe last 130 digits of the de Bruijn sequence are: "db[(len)-130..])
print("\nValidating the deBruijn sequence:")
validate(db)
print("\nValidating the reversed deBruijn sequence:")
validate(reversed(db))
db[4443] = ‘.’
print("\nValidating the overlaid deBruijn sequence:")
validate(db)
- 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 deBruijn sequence: No errors found Validating the reversed deBruijn sequence: No errors found Validating the overlaid deBruijn sequence: 4 errors found: PIN number 1459 missing PIN number 4591 missing PIN number 5814 missing PIN number 8145 missing
8080 Assembly
bdos: equ 5 ; BDOS entry point
putch: equ 2 ; Write character to console
puts: equ 9 ; Write string to console
org 100h
lhld bdos+1 ; Put stack at highest usable address
sphl
;;; Generate de_bruijn(10,4) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
mvi c,40 ; Zero out a[]
xra a
lxi d,arr
zloop: stax d
inx d
dcr c
jnz zloop
lxi h,seq ; H = start of sequence
lxi b,0101h ; db(1,1)
call db_
lxi d,seq ; Allow wrap-around by appending first 3 digits
mvi c,3
wrap: ldax d ; get one of first digits
mov m,a ; store after last digit
inx d ; advance pointers
inx h
dcr c ; do this 3 times
jnz wrap
push h ; store end of data
;;; Print length ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
lxi d,slen ; print "Length: "
call pstr
lxi d,-seq ; calculate length (-seq+seqEnd)
dad d
call puthl ; print length
call pnl ; print newline
;;; Print first and last 130 digits ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
lxi d,sfrst ; print "First 130: "
call pstr
lxi h,seq ; print first 130 digits
call p130
call pnl ; print newline
lxi d,slast ; print "Last 130: "
call pstr
pop h ; Get end of sequence
push h
lxi d,-130 ; 130th last digit
dad d
call p130 ; print last 130 digits
call pnl
call verify ; verify that all numbers are there
;;; Reverse and verify ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
lxi d,srev ; Print "reversing..."
call pstr
pop h ; HL = address of last digit
dcx h
push h ; stack = address of last digit
lxi d,seq ; DE = address of first digit
call rvrs ; Reverse
call verify ; Verify that all numbers are there
lxi d,seq ; Then reverse again (restoring it)
pop h
call rvrs
;;; Replace 4444th digit with '.' and verify ;;;;;;;;;;;;;;;;;;;;;;
lxi d,s4444
call pstr
mvi a,'.'
sta seq+4444
call verify
rst 0
;;; db(t,p); t,p in B,C; end of sequence in HL ;;;;;;;;;;;;;;;;;;;;
db_: mov a,b ; if t>n (n=4)
cpi 5 ; t >= n+1
jc dbelse
mov a,c ; 4%p==0, for p in {1,2,3,4}, is false iff p=3
cpi 3
rz ; stop if p=3, i.e. 4%p<>0
lxi d,arr+1 ; copy P elements to seq forom arr[1..]
dbextn: ldax d ; take from a[]
mov m,a ; store in sequence
inx h ; advance pointers
inx d
dcr c ; and do this P times
jnz dbextn
ret
dbelse: mov a,b ; t - p
sub c
mvi d,arr/256
mov e,a ; a[] is page-aligned for easier indexing
ldax d ; get a[t-p]
mov e,b ; store in a[t]
stax d
push b ; keep T and P
inr b ; db(t+1, p)
call db_
pop b ; restore T and P
mov a,b ; get a[t-p]
sub c
mvi d,arr/256
mov e,a
ldax d ; j = a[t-p]
dbloop: inr a ; j++
cpi 10 ; reached K = 10?
rnc ; then stop
mvi d,arr/256
mov e,b
stax d ; a[t] = j
push psw ; keep j
push b ; keep t and p
mov c,b
inr b
call db_ ; db(t+1, t)
pop b ; restore t and p
pop psw ; restore j
jmp dbloop
;;; Verify that all numbers are there ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
verify: lxi d,sver ; print "Verifying... "
call pstr
mvi d,0 ; Zero out the flag array
lxi b,10000
lxi h,val
vzero: mov m,d
inx h
dcx b
mov a,b
ora c
jnz vzero
lxi h,seq ; Sequence pointer
donum: push h ; Store sequence pointer
push h ; Push two copies
lxi h,0 ; Current 4-digit number
mvi c,4 ; Number has 4 digits
dgtadd: mov d,h ; HL *= 10
mov e,l
dad h
dad h
dad d
dad h
xthl ; Get sequence pointer
mov a,m ; Get digit
inx h ; Advance pointer
cpi 10 ; Valid digit?
jnc dinval ; If not, go do next 4-digit number
xthl ; Back to number
mov e,a
mvi d,0
dad d ; Add digit to number
dcr c ; More digits?
jnz dgtadd ; Then get digit
lxi d,val ; HL is now the current 4-digit number
dad d
inr m ; val[HL]++ (we've seen it)
dinval: pop h ; Pointer to after last valid digit
pop h ; Pointer to start of current number
inx h ; Get 4-digit number that starts at next digit
mov d,h ; Next pointer in DE
mov e,l
lxi b,-(seq+10000) ; Are we there yet?
dad b
mov a,h
ora l
xchg ; Next pointer back in HL
jnz donum ; If not done, do next number.
lxi h,val ; Done - get start of validation array
mvi b,0 ; B will be set if one is missing
vnum: mov a,m ; Have we seen HL-val?
ana a
jnz vnext ; If so, do the next number
push h ; Otherwise, keep current address,
lxi d,-val ; Subtract val (to get the number)
dad d
call puthl ; Print this number as being missing
mvi b,1 ; Set B,
pop h ; and then restore the address
vnext: inx h ; Increment the number
push h
lxi d,-(val+10000) ; Are we there yet?
dad d
mov a,h
ora l
pop h
jnz vnum ; If not, check next number.
dcr b ; At the end, if B was not set,
lxi d,snone ; print "none missing",
jnz pstr
lxi d,smiss ; otherwise, print "missing"
jmp pstr
;;; Subroutines ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; reverse memory starting at DE and ending at HL
rvrs: mov b,m ; Load [HL]
ldax d ; Load [DE]
mov m,a ; [HL] = old [DE]
mov a,b
stax d ; [DE] = old [HL]
inx d ; Move bottom pointer upwards,
dcx h ; Move top pointer downwards,
mov a,d ; D<H = not there yet
cmp h
jc rvrs
mov a,e ; E<L = not there yet
cmp l
jc rvrs
ret
;;; print number in HL, saving registers
puthl: push h ; save registers
push d
push b
lxi b,nbuf ; number buffer pointer
push b ; keep it on the stack
dgt: lxi b,-10
lxi d,-1
dgtdiv: inx d ; calculate digit
dad b
jc dgtdiv
mvi a,'0'+10
add l
pop h ; get pointer from stack
dcx h ; go to previous digit
mov m,a ; store digit
push h ; put pointer back
xchg ; are there any more digits?
mov a,h
ora l
jnz dgt ; if so, calculate next digit
pop d ; otherwise, get pointer to first digit
jmp pstr_ ; and print the resulting string
;;; print 130 digits from the sequence, starting at HL
p130: push h
push d
push b
mvi b,130 ; 130 digits
p130l: mov a,m ; get current digit
adi '0' ; make ASCII
inx h ; advance pointer
push b ; save pointer and counter
push h
mvi c,putch ; print character
mov e,a
call bdos
pop h ; restore pointer and counter
pop b
dcr b ; one fewer character left
jnz p130l ; if characters left, print next
jmp rsreg ; otherwise, restore registers and return
;;; print newline
pnl: lxi d,snl
;;; print string in DE, saving registers
pstr: push h ; store registers
push d
push b
pstr_: mvi c,puts ; print string using CP/M
call bdos
rsreg: pop b ; restore registers
pop d
pop h
ret
snl: db 13,10,'$'
slen: db 'Length: $'
sfrst: db 'First 130: $'
slast: db 'Last 130: $'
srev: db 'Reversing...',13,10,'$'
s4444: db 'Set seq[4444] to `.`...',13,10,'$'
sver: db 'Verifying... $'
snone: db 'none '
smiss: db 'missing',13,10,'$'
db '00000' ; number output buffer
nbuf: db ' $'
arr: equ ($/256+1)*256 ; Place to store a[] (page-aligned)
val: equ arr+40 ; Place to store validation flags
seq: equ val+10000 ; Place to store De Bruijn sequence
- Output:
Length: 10003 First 130: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 Last 130: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 Verifying... none missing Reversing... Verifying... none missing Set seq[4444] to `.`... Verifying... 1459 4591 5914 8145 missing
8086 Assembly
putch: equ 2 ; Print character
puts: equ 9 ; Print string
cpu 8086
bits 16
section .text
org 100h
;;; Calculate de_bruijn(10, 4) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
xor ax,ax ; zero a[]
mov di,arr
mov cx,20 ; 20 words = 40 bytes
rep stosw
mov di,seq ; start of sequence
mov dx,0101h ; db(1,1)
call db_
mov si,seq ; Add first 3 to end for wrapping
mov cx,3
rep movsb
lea bp,[di-1] ; Store pointer to last digit in BP
;;; Print length ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
mov ah,puts ; Print "Length:"
mov dx,slen
int 21h
mov ax,di ; Length = end - start
sub ax,seq
call putax ; Print length
;;; Print first and last 130 characters and verify ;;;;;;;;;;;;;;;;
mov ah,puts ; Print "First 130..."
mov dx,sfrst
int 21h
mov si,seq ; print first 130 digits
call p130
mov ah,puts ; Print "Last 130..."
mov dx,slast
int 21h
mov si,di ; print last 130 digit
sub si,130
call p130
call verify
;;;; Reverse the sequence and verify ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
mov ah,puts ; Print "Reversing..."
mov dx,srev
int 21h
mov si,seq ; SI = first digit in sequence
mov di,bp ; DI = last digit in sequence
call rvrs ; Reverse
call verify ; Verify
mov si,seq ; Reverse again, putting it back
mov di,bp
call rvrs
;;; Set seq[4444] to '.' and verify ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
mov ah,puts ; Print "set seq[4444] to '.'"
mov dx,s4444
int 21h
mov [seq+4444],byte '.'
call verify ; Verify
ret
;;; db(t, p); t=dh p=dl, di=seq ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
db_: cmp dh,4 ; t>n? (n=4)
jbe .els
cmp dl,3 ; for p in {1,2,3,4}, 4%p==0 iff p=3
je .out
mov si,arr+1 ; add DL=P bytes from a[1..] to sequence
mov cl,dl
xor ch,ch
rep movsb
jmp .out
.els: xor bh,bh
mov bl,dh
sub bl,dl ; t - p
mov al,[arr+bx] ; al = a[t-p]
mov bl,dh ; t
mov [arr+bx],al ; a[t] = al
push dx ; keep arguments
inc dh ; db(++t,p)
call db_
pop dx ; restore arguments
mov bl,dh ; al = a[t-p]
sub bl,dl
mov al,[arr+bx]
.loop: inc al ; al++
cmp al,10 ; when al>=k,
jae .out ; then stop.
mov bl,dh
mov [arr+bx],al ; a[t] = j
push ax ; keep state
push dx
mov dl,dh ; db(t+1, t)
inc dh
call db_
pop dx
pop ax
jmp .loop
.out: ret
;;; Verify that all numbers are there ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
verify: mov ah,puts ; Print "verifying..."
mov dx,sver
int 21h
mov di,val ; Zero validation array
mov cx,5000 ; 10000 bytes = 5000 words
xor ax,ax
rep stosw
mov di,val
mov si,seq ; Pointer to start of sequence
mov cx,6409h ; CH=100 (multiplier), CL=9 (highest digit)
.num: mov ax,[si] ; Read first two digits
cmp ah,cl ; Check that they are valid
ja .inval
cmp al,cl
ja .inval
xchg al,ah ; High digit * 10 + low digit
aad
mul ch ; Multiply by 100 (to add in next two)
mov bx,ax
mov ax,[si+2] ; Read last two digits
cmp ah,cl ; Check that they are valid
ja .inval
cmp al,cl
ja .inval
xchg al,ah ; High digit * 10 + low digit
aad
add bx,ax ; BX = final 4-digit number
inc byte [di+bx] ; Mark this 4-digit number as seen
.inval: inc si ; Next digit
cmp si,seq+10000 ; Are we at the end yet?
jne .num ; If not, do next number
mov si,val ; For each number < 10000, check if it's there
xor cl,cl ; Will be set if a number is missing
.test: lodsb ; Do we have this number?
test al,al
jnz .tnext ; If so, try next number
mov ax,si ; Otherwise, print the missing number
sub ax,val
call putax
mov cl,1 ; And set CL
.tnext: cmp si,val+10000 ; Are we at the end yet?
jne .test
test cl,cl
mov dx,smiss ; Print "... missing"
jnz .print ; if CL is set
mov dx,snone ; or "none missing" otherwise.
.print: mov ah,puts
int 21h
ret
;;; Subroutines ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Print number in AX
putax: push ax ; Keep registers we're changing
push dx
push bx
push di
mov di,numbuf ; Pointer to number buffer
mov bx,10 ; Divisor
.digit: xor dx,dx ; Divide AX by 10
div bx
add dl,'0' ; Add '0' to remainder (digit)
dec di ; Store digit in buffer
mov [di],dl
test ax,ax ; Any more digits?
jnz .digit ; If so, do next digits
mov dx,di ; At the end, print the string
mov ah,puts
int 21h
pop di ; Restore registers
pop bx
pop dx
pop ax
ret
;;; Print 130 digits starting at SI
p130: mov cx,130 ; 130 characters
mov ah,putch ; Print characters
.loop: lodsb ; Get digit
add al,'0' ; Make ASCII
mov dl,al ; Print digit
int 21h
loop .loop
ret
;;; Reverse memory starting at SI and ending at DI
rvrs: mov al,[si] ; Load [SI],
mov ah,[di] ; Load [DI],
mov [di],al ; Set [DI] = old [SI]
mov [si],ah ; Set [SI] = old [DI]
inc si ; Increment bottom pointer
dec di ; Decrement top pointer
cmp si,di ; If SI >= DI, we're done
jb rvrs
ret
section .data
slen: db 'Length: $'
sfrst: db 13,10,'First 130: $'
slast: db 13,10,'Last 130: $'
srev: db 13,10,'Reversing... $'
s4444: db 13,10,'Set seq[4444] to `.`...$'
sver: db 13,10,'Verifying... $'
snone: db 'none '
smiss: db 'missing.$'
db '00000'
numbuf: db ' $'
section .bss
arr: resb 40 ; a[]
val: resb 10000 ; validation array
seq: equ $
- Output:
Length: 10003 First 130: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 Last 130: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 Verifying... none missing. Reversing... Verifying... none missing. Set seq[4444] to `.`... Verifying... 1460 4592 5915 8146 missing.
Ada
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Strings.Fixed; use Ada.Strings;
with Ada.Strings.Unbounded;
procedure De_Bruijn_Sequences is
function De_Bruijn (K, N : Positive) return String
is
use Ada.Strings.Unbounded;
Alphabet : constant String := "0123456789";
subtype Decimal is Integer range 0 .. 9;
type Decimal_Array is array (Natural range <>) of Decimal;
A : Decimal_Array (0 .. K * N - 1) := (others => 0);
Seq : Unbounded_String;
procedure Db (T, P : Positive) is
begin
if T > N then
if N mod P = 0 then
for E of A (1 .. P) loop
Append (Seq, Alphabet (Alphabet'First + E));
end loop;
end if;
else
A (T) := A (T - P);
Db (T + 1, P);
for J in A (T - P) + 1 .. K - 1 loop
A (T) := J;
Db (T + 1, T);
end loop;
end if;
end Db;
begin
Db (1, 1);
return To_String (Seq) & Slice (Seq, 1, N - 1);
end De_Bruijn;
function Image (Value : Integer) return String
is (Fixed.Trim (Value'Image, Left));
function PIN_Image (Value : Integer) return String
is (Fixed.Tail (Image (Value), Count => 4, Pad => '0'));
procedure Validate (Db : String)
is
Found : array (0 .. 9_999) of Natural := (others => 0);
Errors : Natural := 0;
begin
-- Check all strings of 4 consecutive digits within 'db'
-- to see if all 10,000 combinations occur without duplication.
for A in Db'First .. Db'Last - 3 loop
declare
PIN : String renames Db (A .. A + 4 - 1);
begin
if (for all Char of PIN => Char in '0' .. '9') then
declare
N : constant Integer := Integer'Value (PIN);
F : Natural renames Found (N);
begin
F := F + 1;
end;
end if;
end;
end loop;
for I in 0_000 .. 9_999 loop
if Found (I) = 0 then
Put_Line (" PIN number " & PIN_Image (I) & " missing");
Errors := Errors + 1;
elsif Found (I) > 1 then
Put_Line (" PIN number " & PIN_Image (I) & " occurs "
& Image (Found (I)) & " times");
Errors := Errors + 1;
end if;
end loop;
case Errors is
when 0 => Put_Line (" No errors found");
when 1 => Put_Line (" 1 error found");
when others =>
Put_Line (" " & Image (Errors) & " errors found");
end case;
end Validate;
function Backwards (S : String) return String is
R : String (S'Range);
begin
for A in 0 .. S'Length - 1 loop
R (R'Last - A) := S (S'First + A);
end loop;
return R;
end Backwards;
DB : constant String := De_Bruijn (K => 10, N => 4);
Rev : constant String := Backwards (DB);
Ovl : String := DB;
begin
Put_Line ("The length of the de Bruijn sequence is " & DB'Length'Image);
New_Line;
Put_Line ("The first 130 digits of the de Bruijn sequence are: ");
Put_Line (" " & Fixed.Head (DB, 130));
New_Line;
Put_Line ("The last 130 digits of the de Bruijn sequence are: ");
Put_Line (" " & Fixed.Tail (DB, 130));
New_Line;
Put_Line ("Validating the deBruijn sequence:");
Validate (DB);
New_Line;
Put_Line ("Validating the reversed deBruijn sequence:");
Validate (Rev);
New_Line;
Ovl (4444) := '.';
Put_Line ("Validating the overlaid deBruijn sequence:");
Validate (Ovl);
New_Line;
end De_Bruijn_Sequences;
- 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 deBruijn sequence: No errors found Validating the reversed deBruijn sequence: No errors found Validating the overlaid deBruijn sequence: PIN number 1459 missing PIN number 4591 missing PIN number 5814 missing PIN number 8145 missing 4 errors found
BASIC
10 DEFINT A-Z
20 K = 10: N = 4
30 DIM A(K*N), S(K^N+N), T(5), P(5), V(K^N\8)
40 GOSUB 200
50 PRINT "Length: ",S
60 PRINT "First 130:"
70 FOR I=0 TO 129: PRINT USING "#";S(I);: NEXT
80 PRINT: PRINT "Last 130:"
90 FOR I=S-130 TO S-1: PRINT USING "#";S(I);: NEXT
100 PRINT
110 GOSUB 600
120 PRINT "Reversing...": GOSUB 500: GOSUB 600: GOSUB 500
130 PRINT USING "Replacing 4444'th element (#):";S(4443)
140 S(4443) = -1 : REM 0-indexed, and using integers
150 GOSUB 600
160 END
200 REM Generate De Bruijn sequence given K and N
210 T(R) = 1: P(R) = 1
220 IF T(R) > N GOTO 380
230 A(T(R)) = A(T(R)-P(R))
240 R = R+1
250 T(R) = T(R-1)+1
260 P(R) = P(R-1)
270 GOSUB 220
280 R = R-1
290 FOR J = A(T(R)-P(R))+1 TO K-1
300 A(T(R)) = J
310 R = R+1
320 T(R) = T(R-1)+1
330 P(R) = T(R-1)
340 GOSUB 220
350 R = R-1
355 J = A(T(R))
360 NEXT
370 RETURN
380 IF N MOD P(R) THEN RETURN
390 FOR I = 1 TO P(R)
400 S(S) = A(I)
410 S = S+1
420 NEXT
430 RETURN
500 REM Reverse the sequence
510 FOR I=0 TO S\2
520 J = S(I)
530 S(I) = S(S-I)
540 S(S-I) = J
550 NEXT
560 RETURN
600 REM Validate the sequence (uses bit packing to save memory)
610 PRINT "Validating...";
620 FOR I=0 TO N-1: S(S+I)=S(I): NEXT
630 FOR I=0 TO K^N\8-1: V(I)=0: NEXT
640 FOR I=0 TO S
650 P=0
660 FOR J=0 TO N-1
662 D=S(I+J)
663 IF D<0 GOTO 690
665 P=K*P+D
669 NEXT J
670 X=P\8
680 V(X) = V(X) OR 2^(P AND 7)
690 NEXT I
700 M=1
710 FOR I=0 TO K^N\8-1
720 IF V(I)=255 GOTO 760
730 FOR J=0 TO 7
740 IF (V(I) AND 2^J)=0 THEN M=0: PRINT USING " ####";I*8+J;
750 NEXT
760 NEXT
770 IF M THEN PRINT " none";
780 PRINT " missing."
790 RETURN
- Output:
Length: 10000 First 130: 00001000200030004000500060007000800090011001200130014001500160017001800190021002 20023002400250026002700280029003100320033003400350 Last 130: 89768986899696977697869796987698869896997699869997777877797788778977987799787879 78887889789878997979887989799879998888988998989999 Validating... none missing. Reversing... Validating... none missing. Replacing 4444'th element (4): Validating... 1459 4591 5814 8145 missing.
C#
using System;
using System.Collections.Generic;
using System.Text;
namespace DeBruijn {
class Program {
const string digits = "0123456789";
static string DeBruijn(int k, int n) {
var alphabet = digits.Substring(0, k);
var a = new byte[k * n];
var seq = new List<byte>();
void db(int t, int p) {
if (t > n) {
if (n % p == 0) {
seq.AddRange(new ArraySegment<byte>(a, 1, p));
}
} else {
a[t] = a[t - p];
db(t + 1, p);
var j = a[t - p] + 1;
while (j < k) {
a[t] = (byte)j;
db(t + 1, t);
j++;
}
}
}
db(1, 1);
var buf = new StringBuilder();
foreach (var i in seq) {
buf.Append(alphabet[i]);
}
var b = buf.ToString();
return b + b.Substring(0, n - 1);
}
static bool AllDigits(string s) {
foreach (var c in s) {
if (c < '0' || '9' < c) {
return false;
}
}
return true;
}
static void Validate(string db) {
var le = db.Length;
var found = new int[10_000];
var errs = new List<string>();
// Check all strings of 4 consecutive digits within 'db'
// to see if all 10,000 combinations occur without duplication.
for (int i = 0; i < le - 3; i++) {
var s = db.Substring(i, 4);
if (AllDigits(s)) {
int.TryParse(s, out int n);
found[n]++;
}
}
for (int i = 0; i < 10_000; i++) {
if (found[i] == 0) {
errs.Add(string.Format(" PIN number {0,4} missing", i));
} else if (found[i] > 1) {
errs.Add(string.Format(" PIN number {0,4} occurs {1} times", i, found[i]));
}
}
var lerr = errs.Count;
if (lerr == 0) {
Console.WriteLine(" No errors found");
} else {
var pl = lerr == 1 ? "" : "s";
Console.WriteLine(" {0} error{1} found:", lerr, pl);
errs.ForEach(Console.WriteLine);
}
}
static string Reverse(string s) {
char[] arr = s.ToCharArray();
Array.Reverse(arr);
return new string(arr);
}
static void Main() {
var db = DeBruijn(10, 4);
var le = db.Length;
Console.WriteLine("The length of the de Bruijn sequence is {0}", le);
Console.WriteLine("\nThe first 130 digits of the de Bruijn sequence are: {0}", db.Substring(0, 130));
Console.WriteLine("\nThe last 130 digits of the de Bruijn sequence are: {0}", db.Substring(le - 130, 130));
Console.WriteLine("\nValidating the deBruijn sequence:");
Validate(db);
Console.WriteLine("\nValidating the reversed deBruijn sequence:");
Validate(Reverse(db));
var bytes = db.ToCharArray();
bytes[4443] = '.';
db = new string(bytes);
Console.WriteLine("\nValidating the overlaid deBruijn sequence:");
Validate(db);
}
}
}
- 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 deBruijn sequence: No errors found Validating the reversed deBruijn sequence: No errors found Validating the overlaid deBruijn sequence: 4 errors found: PIN number 1459 missing PIN number 4591 missing PIN number 5814 missing PIN number 8145 missing
C++
#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <string>
#include <sstream>
#include <vector>
typedef unsigned char byte;
std::string deBruijn(int k, int n) {
std::vector<byte> a(k * n, 0);
std::vector<byte> seq;
std::function<void(int, int)> db;
db = [&](int t, int p) {
if (t > n) {
if (n % p == 0) {
for (int i = 1; i < p + 1; i++) {
seq.push_back(a[i]);
}
}
} else {
a[t] = a[t - p];
db(t + 1, p);
auto j = a[t - p] + 1;
while (j < k) {
a[t] = j & 0xFF;
db(t + 1, t);
j++;
}
}
};
db(1, 1);
std::string buf;
for (auto i : seq) {
buf.push_back('0' + i);
}
return buf + buf.substr(0, n - 1);
}
bool allDigits(std::string s) {
for (auto c : s) {
if (c < '0' || '9' < c) {
return false;
}
}
return true;
}
void validate(std::string db) {
auto le = db.size();
std::vector<int> found(10000, 0);
std::vector<std::string> errs;
// Check all strings of 4 consecutive digits within 'db'
// to see if all 10,000 combinations occur without duplication.
for (size_t i = 0; i < le - 3; i++) {
auto s = db.substr(i, 4);
if (allDigits(s)) {
auto n = stoi(s);
found[n]++;
}
}
for (int i = 0; i < 10000; i++) {
if (found[i] == 0) {
std::stringstream ss;
ss << " PIN number " << i << " missing";
errs.push_back(ss.str());
} else if (found[i] > 1) {
std::stringstream ss;
ss << " PIN number " << i << " occurs " << found[i] << " times";
errs.push_back(ss.str());
}
}
if (errs.empty()) {
std::cout << " No errors found\n";
} else {
auto pl = (errs.size() == 1) ? "" : "s";
std::cout << " " << errs.size() << " error" << pl << " found:\n";
for (auto e : errs) {
std::cout << e << '\n';
}
}
}
int main() {
std::ostream_iterator<byte> oi(std::cout, "");
auto db = deBruijn(10, 4);
std::cout << "The length of the de Bruijn sequence is " << db.size() << "\n\n";
std::cout << "The first 130 digits of the de Bruijn sequence are: ";
std::copy_n(db.cbegin(), 130, oi);
std::cout << "\n\nThe last 130 digits of the de Bruijn sequence are: ";
std::copy(db.cbegin() + (db.size() - 130), db.cend(), oi);
std::cout << "\n";
std::cout << "\nValidating the de Bruijn sequence:\n";
validate(db);
std::cout << "\nValidating the reversed de Bruijn sequence:\n";
auto rdb = db;
std::reverse(rdb.begin(), rdb.end());
validate(rdb);
auto by = db;
by[4443] = '.';
std::cout << "\nValidating the overlaid de Bruijn sequence:\n";
validate(by);
return 0;
}
- 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
CLU
% Generate the De Bruijn sequence consisiting of N-digit numbers
de_bruijn = cluster is generate
rep = null
own k: int := 0
own n: int := 0
own a: array[int] := array[int]$[]
own seq: array[int] := array[int]$[]
generate = proc (k_, n_: int) returns (string)
k := k_
n := n_
a := array[int]$fill(0, k*n, 0)
seq := array[int]$[]
db(1, 1)
s: stream := stream$create_output()
for i: int in array[int]$elements(seq) do
stream$puts(s, int$unparse(i))
end
return(stream$get_contents(s))
end generate
db = proc (t, p: int)
if t>n then
if n//p = 0 then
for i: int in int$from_to(1, p) do
array[int]$addh(seq, a[i])
end
end
else
a[t] := a[t - p]
db(t+1, p)
for j: int in int$from_to(a[t - p] + 1, k-1) do
a[t] := j
db(t + 1, t)
end
end
end db
end de_bruijn
% Reverse a string
reverse = proc (s: string) returns (string)
r: array[char] := array[char]$predict(1, string$size(s))
for c: char in string$chars(s) do
array[char]$addl(r, c)
end
return(string$ac2s(r))
end reverse
% Find all missing N-digit values
find_missing = proc (db: string, n: int) returns (sequence[string])
db := db || string$substr(db, 1, n) % wrap
missing: array[string] := array[string]$[]
s: stream := stream$create_output()
for i: int in int$from_to(0, 10**n-1) do
%s: stream := stream$create_output()
stream$reset(s)
stream$putzero(s, int$unparse(i), n)
val: string := stream$get_contents(s)
if string$indexs(val, db) = 0 then
array[string]$addh(missing, val)
end
end
return(sequence[string]$a2s(missing))
end find_missing
% Report all missing values, or 'none'.
validate = proc (s: stream, db: string, n: int)
stream$puts(s, "Validating...")
missing: sequence[string] := find_missing(db, n)
for v: string in sequence[string]$elements(missing) do
stream$puts(s, " " || v)
end
if sequence[string]$size(missing) = 0 then
stream$puts(s, " none")
end
stream$putl(s, " missing.")
end validate
start_up = proc ()
po: stream := stream$primary_output()
% Generate the De Bruijn sequence for 4-digit numbers
db: string := de_bruijn$generate(10, 4)
% Report length and first and last digits
stream$putl(po, "Length: " || int$unparse(string$size(db)))
stream$putl(po, "First 130 characters:")
stream$putl(po, string$substr(db, 1, 130))
stream$putl(po, "Last 130 characters:")
stream$putl(po, string$substr(db, string$size(db)-130, 130))
% See if there are any missing values in the sequence
validate(po, db, 4)
% Reverse and validate again
stream$putl(po, "Reversing...")
validate(po, reverse(db), 4)
% Replace the 4444'th element with '.' and validate again
stream$putl(po, "Setting the 4444'th character to '.'...")
db := string$substr(db, 1, 4443) || "." || string$rest(db, 4445)
validate(po, db, 4)
end start_up
- Output:
Length: 10000 First 130 characters: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 Last 130 characters: 6897689868996969776978697969876988698969976998699977778777977887789779877997878797888788978987899797988798979987999888898899898999 Validating... none missing. Reversing... Validating... none missing. Setting the 4444'th character to '.'... Validating... 1459 4591 5814 8145 missing.
D
import std.array;
import std.conv;
import std.format;
import std.range;
import std.stdio;
immutable DIGITS = "0123456789";
string deBruijn(int k, int n) {
auto alphabet = DIGITS[0..k];
byte[] a;
a.length = k * n;
byte[] seq;
void db(int t, int p) {
if (t > n) {
if (n % p == 0) {
auto temp = a[1..p + 1];
seq ~= temp;
}
} else {
a[t] = a[t - p];
db(t + 1, p);
auto j = a[t - p] + 1;
while (j < k) {
a[t] = cast(byte)(j & 0xFF);
db(t + 1, t);
j++;
}
}
}
db(1, 1);
string buf;
foreach (i; seq) {
buf ~= alphabet[i];
}
return buf ~ buf[0 .. n - 1];
}
bool allDigits(string s) {
foreach (c; s) {
if (c < '0' || '9' < c) {
return false;
}
}
return true;
}
void validate(string db) {
auto le = db.length;
int[10_000] found;
string[] errs;
// Check all strings of 4 consecutive digits within 'db'
// to see if all 10,000 combinations occur without duplication.
foreach (i; 0 .. le - 3) {
auto s = db[i .. i + 4];
if (allDigits(s)) {
auto n = s.to!int;
found[n]++;
}
}
foreach (i; 0 .. 10_000) {
if (found[i] == 0) {
errs ~= format(" PIN number %04d missing", i);
} else if (found[i] > 1) {
errs ~= format(" PIN number %04d occurs %d times", i, found[i]);
}
}
if (errs.empty) {
writeln(" No errors found");
} else {
auto pl = (errs.length == 1) ? "" : "s";
writeln(" ", errs.length, " error", pl, " found:");
writefln("%-(%s\n%)", errs);
}
}
void main() {
auto db = deBruijn(10, 4);
writeln("The length of the de Bruijn sequence is ", db.length);
writeln("\nThe first 130 digits of the de Bruijn sequence are: ", db[0 .. 130]);
writeln("\nThe last 130 digits of the de Bruijn sequence are: ", db[$ - 130 .. $]);
writeln("\nValidating the deBruijn sequence:");
validate(db);
writeln("\nValidating the reversed deBruijn sequence:");
validate(db.retro.to!string);
auto by = db.dup;
by[4443] = '.';
db = by.idup;
writeln("\nValidating the overlaid deBruijn sequence:");
validate(db);
}
- 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 deBruijn sequence: No errors found Validating the reversed deBruijn sequence: No errors found Validating the overlaid deBruijn sequence: 4 errors found: PIN number 1459 missing PIN number 4591 missing PIN number 5814 missing PIN number 8145 missing
EasyLang
global a[] seq[] k n .
proc db t p . .
if t > n
if n mod p = 0
for i = 1 to p
seq[] &= a[i + 1]
.
.
else
a[t + 1] = a[t - p + 1]
db t + 1 p
j = a[t - p + 1] + 1
while j < k
a[t + 1] = j mod 256
db t + 1 t
j += 1
.
.
.
func$ debruijn k0 n0 .
k = k0
n = n0
a[] = [ ]
len a[] k * n
seq[] = [ ]
db 1 1
for v in seq[]
buf$ &= v
.
buf$ &= substr buf$ 1 (n - 1)
return buf$
.
func alldigits s$ .
for c$ in strchars s$
if strcode c$ < 48 or strcode c$ > 57
return 0
.
.
return 1
.
proc validate db$ . .
len found[] 10000
for i = 1 to len db$ - 3
s$ = substr db$ i 4
if alldigits s$ = 1
n = number s$
found[n + 1] += 1
.
.
for i = 1 to 10000
if found[i] = 0
errs$[] &= " PIN number " & i - 1 & " missing"
elif found[i] > 1
errs$[] &= " PIN number " & i - 1 & " occurs " & found[i] & " times"
.
.
if len errs$[] = 0
print " No errors found"
else
for s$ in errs$[]
print s$
.
.
.
proc main . .
db$ = debruijn 10 4
print "The length of the de Bruijn sequence is " & len db$
print ""
write "The first 130 digits of the de Bruijn sequence are: "
print substr db$ 1 130
print ""
write "The last 130 digits of the de Bruijn sequence are: "
print substr db$ -130 130
print ""
print "Validating the de Bruijn sequence:"
validate db$
print ""
print "Validating the reversed de Bruijn sequence:"
for i = len db$ downto 1
dbr$ &= substr db$ i 1
.
validate dbr$
print ""
db$ = substr db$ 1 4443 & "." & substr db$ 4445 (1 / 0)
print "Validating the overlaid de Bruijn sequence:"
validate db$
print ""
.
main
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)
}
- 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
Groovy
import java.util.function.BiConsumer
class DeBruijn {
interface Recursable<T, U> {
void apply(T t, U u, Recursable<T, U> r);
}
static <T, U> BiConsumer<T, U> recurse(Recursable<T, U> f) {
return { t, u -> f.apply(t, u, f) }
}
private static String deBruijn(int k, int n) {
byte[] a = new byte[k * n]
Arrays.fill(a, (byte) 0)
List<Byte> seq = new ArrayList<>()
BiConsumer<Integer, Integer> db = recurse({ int t, int p, f ->
if (t > n) {
if (n % p == 0) {
for (int i = 1; i < p + 1; ++i) {
seq.add(a[i])
}
}
} else {
a[t] = a[t - p]
f.apply(t + 1, p, f)
int j = a[t - p] + 1
while (j < k) {
a[t] = (byte) (j & 0xFF)
f.apply(t + 1, t, f)
j++
}
}
})
db.accept(1, 1)
StringBuilder sb = new StringBuilder()
for (Byte i : seq) {
sb.append("0123456789".charAt(i))
}
sb.append(sb.subSequence(0, n - 1))
return sb.toString()
}
private static boolean allDigits(String s) {
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i)
if (!Character.isDigit(c)) {
return false
}
}
return true
}
private static void validate(String db) {
int le = db.length()
int[] found = new int[10_000]
Arrays.fill(found, 0)
List<String> errs = new ArrayList<>()
// Check all strings of 4 consecutive digits within 'db'
// to see if all 10,000 combinations occur without duplication.
for (int i = 0; i < le - 3; ++i) {
String s = db.substring(i, i + 4)
if (allDigits(s)) {
int n = Integer.parseInt(s)
found[n]++
}
}
for (int i = 0; i < 10_000; ++i) {
if (found[i] == 0) {
errs.add(String.format(" PIN number %d is missing", i))
} else if (found[i] > 1) {
errs.add(String.format(" PIN number %d occurs %d times", i, found[i]))
}
}
if (errs.isEmpty()) {
System.out.println(" No errors found")
} else {
String pl = (errs.size() == 1) ? "" : "s"
System.out.printf(" %d error%s found:\n", errs.size(), pl)
errs.forEach(System.out.&println)
}
}
static void main(String[] args) {
String db = deBruijn(10, 4)
System.out.printf("The length of the de Bruijn sequence is %d\n\n", db.length())
System.out.printf("The first 130 digits of the de Bruijn sequence are: %s\n\n", db.substring(0, 130))
System.out.printf("The last 130 digits of the de Bruijn sequence are: %s\n\n", db.substring(db.length() - 130))
System.out.println("Validating the de Bruijn sequence:")
validate(db)
StringBuilder sb = new StringBuilder(db)
String rdb = sb.reverse().toString()
System.out.println()
System.out.println("Validating the de Bruijn sequence:")
validate(rdb)
sb = new StringBuilder(db)
sb.setCharAt(4443, '.' as char)
System.out.println()
System.out.println("Validating the overlaid de Bruijn sequence:")
validate(sb.toString())
}
}
- 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 de Bruijn sequence: No errors found Validating the overlaid de Bruijn sequence: 4 errors found: PIN number 1459 is missing PIN number 4591 is missing PIN number 5814 is missing PIN number 8145 is missing
Haskell
Permutation-based
Straight-forward implementation of inverse Burrows—Wheeler transform [[wp:De_Bruijn_sequence#Construction|De_Bruijn_sequence#Construction] is reasonably efficient for the task (about a milliseconds for B(10,4) in GHCi).
import Data.List
import Data.Map ((!))
import qualified Data.Map as M
-- represents a permutation in a cycle notation
cycleForm :: [Int] -> [[Int]]
cycleForm p = unfoldr getCycle $ M.fromList $ zip [0..] p
where
getCycle p
| M.null p = Nothing
| otherwise =
let Just ((x,y), m) = M.minViewWithKey p
c = if x == y then [] else takeWhile (/= x) (iterate (m !) y)
in Just (c ++ [x], foldr M.delete m c)
-- the set of Lyndon words generated by inverse Burrows—Wheeler transform
lyndonWords :: Ord a => [a] -> Int -> [[a]]
lyndonWords s n = map (ref !!) <$> cycleForm perm
where
ref = concat $ replicate (length s ^ (n - 1)) s
perm = s >>= (`elemIndices` ref)
-- returns the de Bruijn sequence of order n for an alphabeth s
deBruijn :: Ord a => [a] -> Int -> [a]
deBruijn s n = let lw = concat $ lyndonWords n s
in lw ++ take (n-1) lw
λ> cycleForm [1,4,3,2,0] [[1,4,0],[3,2]] λ> lyndonWords "ab" 3 ["a","aab","abb","b"] λ> deBruijn "ab" 3 "aaababbbaa"
The task.
import Control.Monad (replicateM)
main = do
let symbols = ['0'..'9']
let db = deBruijn symbols 4
putStrLn $ "The length of de Bruijn sequence: " ++ show (length db)
putStrLn $ "The first 130 symbols are:\n" ++ show (take 130 db)
putStrLn $ "The last 130 symbols are:\n" ++ show (drop (length db - 130) db)
let words = replicateM 4 symbols
let validate db = filter (not . (`isInfixOf` db)) words
putStrLn $ "Words not in the sequence: " ++ unwords (validate db)
let db' = a ++ ('.': tail b) where (a,b) = splitAt 4444 db
putStrLn $ "Words not in the corrupted sequence: " ++ unwords (validate db')
λ> main The length of de Bruijn sequence: 10003 The first 130 symbols are: "0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350" The last 130 symbols are: "6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000" Words not in the sequence: Words not in the corrupted sequence: 1459 4591 5914 8145
Array-based
import Control.Monad.State
import Data.Array (Array, listArray, (!), (//))
import qualified Data.Array as A
deBruijn :: [a] -> Int -> [a]
deBruijn s n =
let
k = length s
db :: Int -> Int -> State (Array Int Int) [Int]
db t p =
if t > n
then
if n `mod` p == 0
then get >>= \a -> return [ a ! k | k <- [1 .. p]]
else return []
else do
a <- get
x <- setArray t (a ! (t-p)) >> db (t+1) p
a <- get
y <- sequence [ setArray t j >> db (t+1) t
| j <- [a ! (t-p) + 1 .. k - 1] ]
return $ x ++ concat y
setArray i x = modify (// [(i, x)])
seqn = db 1 1 `evalState` listArray (0, k*n-1) (repeat 0)
in [ s !! i | i <- seqn ++ take (n-1) seqn ]
J
definitions. The C. verb computes the cycles. J's sort is a stable sort.
NB. implement inverse Burrows—Wheeler transform sequence method
repeat_alphabet=: [: , [: i.&> (^ <:) # [
assert 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -: 2 repeat_alphabet 4
de_bruijn=: ({~ ([: ; [: C. /:^:2))@:repeat_alphabet NB. K de_bruijn N
pins=: #&10 #: [: i. 10&^ NB. pins y generates all y digit PINs
groups=: [ ]\ ] , ({.~ <:)~ NB. length x infixes of sequence y cyclically extended by x-1
verify_PINs=: (/:~@:groups -: pins@:[) NB. LENGTH verify_PINs SEQUENCE
Task
NB. A is the sequence
A=: 10 de_bruijn 4
NB. tally A
#A
10000
NB. literally the first and final 130 digits
Num_j_ {~ 130 ({. ,: ({.~ -)~) A
0000101001101111000210020102110202001210120112111202121200221022012211220222122220003100320030103110321030203120322030300131013201
9469956996699769986990799179927993799479957996799779987990899189928993899489958996899789988990999199929993999499959996999799989999
NB. verifications. seriously?
4 verify_PINs A
1
4 (verify_PINs |.) A
1
4 verify_PINs (a.i.'.') (<: 4444)} A
0
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.BiConsumer;
public class DeBruijn {
public interface Recursable<T, U> {
void apply(T t, U u, Recursable<T, U> r);
}
public static <T, U> BiConsumer<T, U> recurse(Recursable<T, U> f) {
return (t, u) -> f.apply(t, u, f);
}
private static String deBruijn(int k, int n) {
byte[] a = new byte[k * n];
Arrays.fill(a, (byte) 0);
List<Byte> seq = new ArrayList<>();
BiConsumer<Integer, Integer> db = recurse((t, p, f) -> {
if (t > n) {
if (n % p == 0) {
for (int i = 1; i < p + 1; ++i) {
seq.add(a[i]);
}
}
} else {
a[t] = a[t - p];
f.apply(t + 1, p, f);
int j = a[t - p] + 1;
while (j < k) {
a[t] = (byte) (j & 0xFF);
f.apply(t + 1, t, f);
j++;
}
}
});
db.accept(1, 1);
StringBuilder sb = new StringBuilder();
for (Byte i : seq) {
sb.append("0123456789".charAt(i));
}
sb.append(sb.subSequence(0, n - 1));
return sb.toString();
}
private static boolean allDigits(String s) {
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (!Character.isDigit(c)) {
return false;
}
}
return true;
}
private static void validate(String db) {
int le = db.length();
int[] found = new int[10_000];
Arrays.fill(found, 0);
List<String> errs = new ArrayList<>();
// Check all strings of 4 consecutive digits within 'db'
// to see if all 10,000 combinations occur without duplication.
for (int i = 0; i < le - 3; ++i) {
String s = db.substring(i, i + 4);
if (allDigits(s)) {
int n = Integer.parseInt(s);
found[n]++;
}
}
for (int i = 0; i < 10_000; ++i) {
if (found[i] == 0) {
errs.add(String.format(" PIN number %d is missing", i));
} else if (found[i] > 1) {
errs.add(String.format(" PIN number %d occurs %d times", i, found[i]));
}
}
if (errs.isEmpty()) {
System.out.println(" No errors found");
} else {
String pl = (errs.size() == 1) ? "" : "s";
System.out.printf(" %d error%s found:\n", errs.size(), pl);
errs.forEach(System.out::println);
}
}
public static void main(String[] args) {
String db = deBruijn(10, 4);
System.out.printf("The length of the de Bruijn sequence is %d\n\n", db.length());
System.out.printf("The first 130 digits of the de Bruijn sequence are: %s\n\n", db.substring(0, 130));
System.out.printf("The last 130 digits of the de Bruijn sequence are: %s\n\n", db.substring(db.length() - 130));
System.out.println("Validating the de Bruijn sequence:");
validate(db);
StringBuilder sb = new StringBuilder(db);
String rdb = sb.reverse().toString();
System.out.println();
System.out.println("Validating the de Bruijn sequence:");
validate(rdb);
sb = new StringBuilder(db);
sb.setCharAt(4443, '.');
System.out.println();
System.out.println("Validating the overlaid de Bruijn sequence:");
validate(sb.toString());
}
}
- 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 de Bruijn sequence: No errors found Validating the overlaid de Bruijn sequence: 4 errors found: PIN number 1459 is missing PIN number 4591 is missing PIN number 5814 is missing PIN number 8145 is missing
jq
Adapted from Wren
Works with gojq, the Go implementation of jq
def allDigits:
all(explode[]; 48 <= . and . <= 57);
def lpad($len): tostring | ($len - length) as $l | ("0" * $l) + .;
def deBruijn:
{deBruijn: ""}
| reduce range(0; 100) as $n (.;
($n|lpad(2)) as $a
| ($a | explode) as [$a1, $a2]
| if $a2 >= $a1
then .deBruijn += (if ($a1 == $a2) then ([$a1]|implode) else $a end)
| .m = $n + 1
| until(.m > 99;
(.m|lpad(2)) as $ms
| if ($ms[1:2]|explode[0]) > $a1
then .deBruijn += $a + $ms
end
| .m += 1 )
end )
| .deBruijn + "000" ;
def describe:
. as $d
| "de Bruijn sequence length: \($d|length)",
"First 130 characters:",
$d[0:130],
"Last 130 characters:",
$d[-130:];
def check:
. as $text
| { res: [],
found: [range(0;10000) | 0],
k: 0 }
| reduce range( 0; $text|length-3) as $i (.;
$text[$i : $i+4] as $s
| if ($s|allDigits)
then .k = ($s|tonumber)
| .found[.k] += 1
end )
| reduce range(0; 10000) as $i (.;
.k = .found[$i]
| if .k != 1
then (" Pin number \($i) "
+ (if .k == 0 then "missing" else "occurs \(.k) times" end ) ) as $e
| .res += [$e]
end )
| .k = (.res|length)
| if .k == 0
then .res = "No errors found"
else
(if .k == 1 then "" else "s" end) as $s
| .res = "\(.k) error\($s) found:\n" + (.res | join("\n"))
end
| .res ;
# The tasks
deBruijn
| describe,
"Missing 4 digit PINs in this sequence: \(check)",
"Missing 4 digit PINs in the reversed sequence: \(explode|reverse|implode|check)",
"4,444th digit in the sequence: '\(.[4443])' (setting it to '.')",
( .[0:4443] + "." + .[4444:]
| "Re-running checks: \(check)" )
- Output:
de Bruijn sequence length: 10003 First 130 characters: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 Last 130 characters: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 Missing 4 digit PINs in this sequence: No errors found Missing 4 digit PINs in the reversed sequence: No errors found 4,444th digit in the sequence: '4' (setting it to '.') Re-running checks: 4 errors found: Pin number 1459 missing Pin number 4591 missing Pin number 5814 missing Pin number 8145 missing
Julia
function debruijn(k::Integer, n::Integer)
alphabet = b"0123456789abcdefghijklmnopqrstuvwxyz"[1:k]
a = zeros(UInt8, k * n)
seq = UInt8[]
function db(t, p)
if t > n
if n % p == 0
append!(seq, a[2:p+1])
end
else
a[t + 1] = a[t - p + 1]
db(t + 1, p)
for j in a[t-p+1]+1:k-1
a[t + 1] = j
db(t + 1, t)
end
end
end
db(1, 1)
return String([alphabet[i + 1] for i in vcat(seq, seq[1:n-1])])
end
function verifyallPIN(str, k, n, deltaposition=0)
if deltaposition != 0
str = str[1:deltaposition-1] * "." * str[deltaposition+1:end]
end
result = true
for i in 1:k^n-1
pin = string(i, pad=n)
if !occursin(pin, str)
println("PIN $pin does not occur in the sequence.")
result = false
end
end
println("The sequence does ", result ? "" : "not ", "contain all PINs.")
end
const s = debruijn(10, 4)
println("The length of the sequence is $(length(s)). The first 130 digits are:\n",
s[1:130], "\nand the last 130 digits are:\n", s[end-130:end])
print("Testing sequence: "), verifyallPIN(s, 10, 4)
print("Testing the reversed sequence: "), verifyallPIN(reverse(s), 10, 4)
println("\nAfter replacing 4444th digit with \'.\':"), verifyallPIN(s, 10, 4, 4444)
- Output:
The length of the sequence is 10003. The first 130 digits are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 and the last 130 digits are: 76898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 Testing sequence: The sequence does contain all PINs. Testing the reversed sequence: The sequence does contain all PINs. After replacing 4444th digit with '.': PIN 1459 does not occur in the sequence. PIN 4591 does not occur in the sequence. PIN 5814 does not occur in the sequence. PIN 8145 does not occur in the sequence. The sequence does not contain all PINs.
Kotlin
const val digits = "0123456789"
fun deBruijn(k: Int, n: Int): String {
val alphabet = digits.substring(0, k)
val a = ByteArray(k * n)
val seq = mutableListOf<Byte>()
fun db(t: Int, p: Int) {
if (t > n) {
if (n % p == 0) {
seq.addAll(a.sliceArray(1..p).asList())
}
} else {
a[t] = a[t - p]
db(t + 1, p)
var j = a[t - p] + 1
while (j < k) {
a[t] = j.toByte()
db(t + 1, t)
j++
}
}
}
db(1, 1)
val buf = StringBuilder()
for (i in seq) {
buf.append(alphabet[i.toInt()])
}
val b = buf.toString()
return b + b.subSequence(0, n - 1)
}
fun allDigits(s: String): Boolean {
for (c in s) {
if (c < '0' || '9' < c) {
return false
}
}
return true
}
fun validate(db: String) {
val le = db.length
val found = MutableList(10_000) { 0 }
val errs = mutableListOf<String>()
// Check all strings of 4 consecutive digits within 'db'
// to see if all 10,000 combinations occur without duplication.
for (i in 0 until le - 3) {
val s = db.substring(i, i + 4)
if (allDigits(s)) {
val n = s.toInt()
found[n]++
}
}
for (i in 0 until 10_000) {
if (found[i] == 0) {
errs.add(" PIN number %04d missing".format(i))
} else if (found[i] > 1) {
errs.add(" PIN number %04d occurs %d times".format(i, found[i]))
}
}
val lerr = errs.size
if (lerr == 0) {
println(" No errors found")
} else {
val pl = if (lerr == 1) {
""
} else {
"s"
}
println(" $lerr error$pl found:")
println(errs.joinToString("\n"))
}
}
fun main() {
var db = deBruijn(10, 4)
val le = db.length
println("The length of the de Bruijn sequence is $le")
println("\nThe first 130 digits of the de Bruijn sequence are: ${db.subSequence(0, 130)}")
println("\nThe last 130 digits of the de Bruijn sequence are: ${db.subSequence(le - 130, le)}")
println("\nValidating the deBruijn sequence:")
validate(db)
println("\nValidating the reversed deBruijn sequence:")
validate(db.reversed())
val bytes = db.toCharArray()
bytes[4443] = '.'
db = String(bytes)
println("\nValidating the overlaid deBruijn sequence:")
validate(db)
}
- 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 deBruijn sequence: No errors found Validating the reversed deBruijn sequence: No errors found Validating the overlaid deBruijn sequence: 4 errors found: PIN number 1459 missing PIN number 4591 missing PIN number 5814 missing PIN number 8145 missing
Lua
function tprint(tbl)
for i,v in pairs(tbl) do
print(v)
end
end
function deBruijn(k, n)
local a = {}
for i=1, k*n do
table.insert(a, 0)
end
local seq = {}
function db(t, p)
if t > n then
if n % p == 0 then
for i=1, p do
table.insert(seq, a[i + 1])
end
end
else
a[t + 1] = a[t - p + 1]
db(t + 1, p)
local j = a[t - p + 1] + 1
while j < k do
a[t + 1] = j % 256
db(t + 1, t)
j = j + 1
end
end
end
db(1, 1)
local buf = ""
for i,v in pairs(seq) do
buf = buf .. tostring(v)
end
return buf .. buf:sub(1, n - 1)
end
function allDigits(s)
return s:match('[0-9]+') == s
end
function validate(db)
local le = string.len(db)
local found = {}
local errs = {}
for i=1, 10000 do
table.insert(found, 0)
end
-- Check all strings of 4 consecutive digits within 'db'
-- to see if all 10,000 combinations occur without duplication.
for i=1, le - 3 do
local s = db:sub(i, i + 3)
if allDigits(s) then
local n = tonumber(s)
found[n + 1] = found[n + 1] + 1
end
end
local count = 0
for i=1, 10000 do
if found[i] == 0 then
table.insert(errs, " PIN number " .. (i - 1) .. " missing")
count = count + 1
elseif found[i] > 1 then
table.insert(errs, " PIN number " .. (i - 1) .. " occurs " .. found[i] .. " times")
count = count + 1
end
end
if count == 0 then
print(" No errors found")
else
tprint(errs)
end
end
function main()
local db = deBruijn(10,4)
print("The length of the de Bruijn sequence is " .. string.len(db))
print()
io.write("The first 130 digits of the de Bruijn sequence are: ")
print(db:sub(0, 130))
print()
io.write("The last 130 digits of the de Bruijn sequence are: ")
print(db:sub(-130))
print()
print("Validating the de Bruijn sequence:")
validate(db)
print()
print("Validating the reversed de Bruijn sequence:")
validate(db:reverse())
print()
db = db:sub(1,4443) .. "." .. db:sub(4445)
print("Validating the overlaid de Bruijn sequence:")
validate(db)
print()
end
main()
- 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: PIN number 1459 missing PIN number 4591 missing PIN number 5814 missing PIN number 8145 missing
Mathematica /Wolfram Language
seq = DeBruijnSequence[Range[0, 9], 4];
seq = seq~Join~Take[seq, 3];
Length[seq]
{seq[[;; 130]], seq[[-130 ;;]]}
Complement[
StringDrop[ToString[NumberForm[#, 4, NumberPadding -> {"0", "0"}]],
1] & /@ Range[0, 9999],
Union[StringJoin /@ Partition[ToString /@ seq, 4, 1]]]
seq = Reverse[seq];
Complement[
StringDrop[ToString[NumberForm[#, 4, NumberPadding -> {"0", "0"}]],
1] & /@ Range[0, 9999],
Union[StringJoin /@ Partition[ToString /@ seq, 4, 1]]]
seq[[4444]] = ".";
Complement[
StringDrop[ToString[NumberForm[#, 4, NumberPadding -> {"0", "0"}]],
1] & /@ Range[0, 9999],
Union[StringJoin /@ Partition[ToString /@ seq, 4, 1]]]
- Output:
10003 {{0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 4, 0, 0, 0, 5, 0, 0, 0, 6, 0, 0, 0, 7, 0, 0, 0, 8, 0, 0, 0, 9, 0, 0, 1, 1, 0, 0, 1, 2, 0, 0, 1, 3, 0, 0, 1, 4, 0, 0, 1, 5, 0, 0, 1, 6, 0, 0, 1, 7, 0, 0, 1, 8, 0, 0, 1, 9, 0, 0, 2, 1, 0, 0, 2, 2, 0, 0, 2, 3, 0, 0, 2, 4, 0, 0, 2, 5, 0, 0, 2, 6, 0, 0, 2, 7, 0, 0, 2, 8, 0, 0, 2, 9, 0, 0, 3, 1, 0, 0, 3, 2, 0, 0, 3, 3, 0, 0, 3, 4, 0, 0, 3, 5, 0}, {6, 8, 9, 8, 6, 8, 9, 9, 6, 9, 6, 9, 7, 7, 6, 9, 7, 8, 6, 9, 7, 9, 6, 9, 8, 7, 6, 9, 8, 8, 6, 9, 8, 9, 6, 9, 9, 7, 6, 9, 9, 8, 6, 9, 9, 9, 7, 7, 7, 7, 8, 7, 7, 7, 9, 7, 7, 8, 8, 7, 7, 8, 9, 7, 7, 9, 8, 7, 7, 9, 9, 7, 8, 7, 8, 7, 9, 7, 8, 8, 8, 7, 8, 8, 9, 7, 8, 9, 8, 7, 8, 9, 9, 7, 9, 7, 9, 8, 8, 7, 9, 8, 9, 7, 9, 9, 8, 7, 9, 9, 9, 8, 8, 8, 8, 9, 8, 8, 9, 9, 8, 9, 8, 9, 9, 9, 9, 0, 0, 0}} {} {} {"1478", "4781", "7813", "8137"}
Nim
import algorithm, parseutils, strformat, strutils
const Digits = "0123456789"
#---------------------------------------------------------------------------------------------------
func deBruijn(k, n: int): string =
let alphabet = Digits[0..<k]
var a = newSeq[byte](k * n)
var sequence: seq[byte]
#.................................................................................................
func db(t, p: int) =
if t > n:
if n mod p == 0:
sequence &= a[1..p]
else:
a[t] = a[t - p]
db(t + 1, p)
var j = a[t - p] + 1
while j < k.uint:
a[t] = j
db(t + 1, t)
inc j
#...............................................................................................
db(1, 1)
for i in sequence:
result &= alphabet[i]
result &= result[0..(n-2)]
#---------------------------------------------------------------------------------------------------
proc validate(db: string) =
var found: array[10_000, int]
var errs: seq[string]
## Check all strings of 4 consecutive digits within 'db'
## to see if all 10,000 combinations occur without duplication.
for i in 0..(db.len - 4):
let s = db[i..(i+3)]
var n: int
if s.parseInt(n) == 4:
inc found[n]
for n, count in found:
if count == 0:
errs &= fmt" PIN number {n:04d} missing"
elif count > 1:
errs &= fmt" PIN number {n:04d} occurs {count} times"
if errs.len == 0:
echo " No errors found"
else:
let plural = if errs.len == 1: "" else: "s"
echo fmt" {errs.len} error{plural} found"
for err in errs: echo err
#———————————————————————————————————————————————————————————————————————————————————————————————————
var db = deBruijn(10, 4)
echo fmt"The length of the de Bruijn sequence is {db.len}"
echo ""
echo fmt"The first 130 digits of the de Bruijn sequence are: {db[0..129]}"
echo ""
echo fmt"The last 130 digits of the de Bruijn sequence are: {db[^130..^1]}"
echo ""
echo "Validating the deBruijn sequence:"
db.validate()
echo ""
echo "Validating the reversed deBruijn sequence:"
reversed(db).join().validate()
echo ""
db[4443] = '.'
echo "Validating the overlaid deBruijn sequence:"
db.validate()
- 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 deBruijn sequence: No errors found Validating the reversed deBruijn sequence: No errors found Validating the overlaid deBruijn sequence: 4 errors found PIN number 1459 missing PIN number 4591 missing PIN number 5814 missing PIN number 8145 missing
Pascal
A console application in Free Pascal, created with the Lazarus IDE.
For a given word length n, constructs a de Bruijn sequence by concatenating, in lexicographic order, all the Lyndon words whose length divides n. (See Wikipedia article "de Bruijn sequence", section "Construction".)
program deBruijnSequence;
uses SysUtils;
// Create a de Bruijn sequence for the given word length and alphabet.
function deBruijn( const n : integer; // word length
const alphabet : string) : string;
var
d, k, m, s, t, seqLen : integer;
w : array of integer;
begin
k := Length( alphabet);
// de Bruijn sequence will have length k^n
seqLen := 1;
for t := 1 to n do seqLen := seqLen*k;
SetLength( result, seqLen);
d := 0; // index into de Bruijn sequence (will be pre-inc'd)
// Work through Lyndon words of length <= n, in lexicographic order.
SetLength( w, n); // w holds array of indices into the alphabet
w[0] := 1; // first Lyndon word
m := 1; // m = length of Lyndon word
repeat
// If m divides n, append the current Lyndon word to the output
if (m = n) or (m = 1) or (n mod m = 0) then begin
for t := 0 to m - 1 do begin
inc(d);
result[d] := alphabet[w[t]];
end;
end;
// Get next Lyndon word using Duval's algorithm:
// (1) Fill w with repetitions of current word
s := 0; t := m;
while (t < n) do begin
w[t] := w[s];
inc(t); inc(s);
if s = m then s := 0;
end;
// (2) Repeatedly delete highest index k from end of w, if present
m := n;
while (m > 0) and (w[m - 1] = k) do dec(m);
// (3) If word is now null, stop; else increment end value
if m > 0 then inc( w[m - 1]);
until m = 0;
Assert( d = seqLen); // check that the sequence is exactly filled in
end;
// Check a de Bruijn sequence, assuming that its alphabet consists
// of the digits '0'..'9' (in any order);
procedure CheckDecimal( const n : integer; // word length
const deB : string);
var
count : array of integer;
j, L, pin, nrErrors : integer;
wrap : string;
begin
L := Length( deB);
// The de Bruijn sequence is cyclic; make an array to handle wrapround.
SetLength( wrap, 2*n - 2);
for j := 1 to n - 1 do wrap[j] := deB[L + j - n + 1];
for j := n to 2*n - 2 do wrap[j] := deB[j - n + 1];
// Count occurrences of each PIN.
// PIN = -1 if character is not a decimal digit.
SetLength( count, L);
for j := 0 to L - 1 do count[L] := 0;
for j := 1 to L - n + 1 do begin
pin := SysUtils.StrToIntDef( Copy( deB, j, n), -1);
if pin >= 0 then inc( count[pin]);
end;
for j := 1 to n - 1 do begin
pin := SysUtils.StrToIntDef( Copy( wrap, j, n), -1);
if pin >= 0 then inc( count[pin]);
end;
// Check that all counts are 1
nrErrors := 0;
for j := 0 to L - 1 do begin
if count[j] <> 1 then begin
inc( nrErrors);
WriteLn( SysUtils.Format( ' PIN %d has count %d', [j, count[j]]));
end;
end;
WriteLn( SysUtils.Format( ' Number of errors = %d', [nrErrors]));
end;
// Main routine
var
deB, rev : string;
L, j : integer;
begin
deB := deBruijn( 4, '0123456789');
// deB := deBruijn( 4, '7368290514'); // any permutation would do
L := Length( deB);
WriteLn( SysUtils.Format( 'Length of de Bruijn sequence = %d', [L]));
if L >= 260 then begin
WriteLn;
WriteLn( 'First and last 130 characters are:');
WriteLn( Copy( deB, 1, 65));
WriteLn( Copy( deb, 66, 65));
WriteLn( '...');
WriteLn( Copy( deB, L - 129, 65));
WriteLn( Copy( deB, L - 64, 65));
end;
WriteLn;
WriteLn( 'Checking de Bruijn sequence:');
CheckDecimal( 4, deB);
// Check reversed sequence
SetLength( rev, L);
for j := 1 to L do rev[j] := deB[L + 1 - j];
WriteLn( 'Checking reversed sequence:');
CheckDecimal( 4, rev);
// Check sequence with '.' instad of decimal digit
if L >= 4444 then begin
deB[4444] := '.';
WriteLn( 'Checking vandalized sequence:');
CheckDecimal( 4, deB);
end;
end.
- Output:
Length of de Bruijn sequence = 10000 First and last 130 characters are: 00001000200030004000500060007000800090011001200130014001500160017 00180019002100220023002400250026002700280029003100320033003400350 ... 89768986899696977697869796987698869896997699869997777877797788778 97798779978787978887889789878997979887989799879998888988998989999 Checking de Bruijn sequence: Number of errors = 0 Checking reversed sequence: Number of errors = 0 Checking vandalized sequence: PIN 1459 has count 0 PIN 4591 has count 0 PIN 5814 has count 0 PIN 8145 has count 0 Number of errors = 4
Perl
use strict;
use warnings;
use feature 'say';
my $seq;
for my $x (0..99) {
my $a = sprintf '%02d', $x;
next if substr($a,1,1) < substr($a,0,1);
$seq .= (substr($a,0,1) == substr($a,1,1)) ? substr($a,0,1) : $a;
for ($a+1 .. 99) {
next if substr(sprintf('%02d', $_), 1,1) <= substr($a,0,1);
$seq .= sprintf "%s%02d", $a, $_;
}
}
$seq .= '000';
sub check {
my($seq) = @_;
my %chk;
for (0.. -1 + length $seq) { $chk{substr($seq, $_, 4)}++ }
say 'Missing: ' . join ' ', grep { ! $chk{ sprintf('%04d',$_) } } 0..9999;
say 'Extra: ' . join ' ', sort grep { $chk{$_} > 1 } keys %chk;
}
my $n = 130;
say "de Bruijn sequence length: " . length $seq;
say "\nFirst $n characters:\n" . substr($seq, 0, $n );
say "\nLast $n characters:\n" . substr($seq, -$n, $n);
say "\nIncorrect 4 digit PINs in this sequence:";
check $seq;
say "\nIncorrect 4 digit PINs in the reversed sequence:";
check(reverse $seq);
say "\nReplacing the 4444th digit, '@{[substr($seq,4443,1)]}', with '5'";
substr $seq, 4443, 1, 5;
say "Incorrect 4 digit PINs in the revised sequence:";
check $seq;
- Output:
de Bruijn sequence length: 10003 First 130 characters: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 Last 130 characters: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 Incorrect 4 digit PINs in this sequence: Missing: Extra: Incorrect 4 digit PINs in the reversed sequence: Missing: Extra: Replacing the 4444th digit, '4', with '5' Incorrect 4 digit PINs in the revised sequence: Missing: 1459 4591 5814 8145 Extra: 1559 5591 5815 8155
Phix
string deBruijn = "" for n=0 to 99 do string a = sprintf("%02d",n) integer a1 = a[1], a2 = a[2] if a2>=a1 then deBruijn &= iff(a1=a2?a1:a) for m=n+1 to 99 do string ms = sprintf("%02d",m) if ms[2]>a1 then deBruijn &= a&ms end if end for end if end for deBruijn &= "000" printf(1,"de Bruijn sequence length: %d\n\n",length(deBruijn)) printf(1,"First 130 characters:\n%s\n\n",deBruijn[1..130]) printf(1,"Last 130 characters:\n%s\n\n",deBruijn[-130..-1]) function check(string text) sequence res = {} sequence found = repeat(0,10000) integer k for i=1 to length(text)-3 do k = to_integer(text[i..i+3],-1)+1 if k!=0 then found[k] += 1 end if end for for i=1 to 10000 do k = found[i] if k!=1 then string e = sprintf("Pin number %04d ",i-1) e &= iff(k=0?"missing":sprintf("occurs %d times",k)) res = append(res,e) end if end for k = length(res) if k=0 then res = "No errors found" else string s = iff(k=1?"":"s") res = sprintf("%d error%s found:\n ",{k,s})&join(res,"\n ") end if return res end function printf(1,"Missing 4 digit PINs in this sequence: %s\n", check(deBruijn)) printf(1,"Missing 4 digit PINs in the reversed sequence: %s\n",check(reverse(deBruijn))) printf(1,"4444th digit in the sequence: %c (setting it to .)\n", deBruijn[4444]) deBruijn[4444] = '.' printf(1,"Re-running checks: %s\n",check(deBruijn))
- Output:
de Bruijn sequence length: 10003 First 130 characters: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 Last 130 characters: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 Missing 4 digit PINs in this sequence: No errors found Missing 4 digit PINs in the reversed sequence: No errors found 4444th digit in the sequence: 4 (setting it to .) Re-running checks: 4 errors found: Pin number 1459 missing Pin number 4591 missing Pin number 5814 missing Pin number 8145 missing
Python
# from https://en.wikipedia.org/wiki/De_Bruijn_sequence
def de_bruijn(k, n):
"""
de Bruijn sequence for alphabet k
and subsequences of length n.
"""
try:
# let's see if k can be cast to an integer;
# if so, make our alphabet a list
_ = int(k)
alphabet = list(map(str, range(k)))
except (ValueError, TypeError):
alphabet = k
k = len(k)
a = [0] * k * n
sequence = []
def db(t, p):
if t > n:
if n % p == 0:
sequence.extend(a[1:p + 1])
else:
a[t] = a[t - p]
db(t + 1, p)
for j in range(a[t - p] + 1, k):
a[t] = j
db(t + 1, t)
db(1, 1)
return "".join(alphabet[i] for i in sequence)
def validate(db):
"""
Check that all 10,000 combinations of 0-9 are present in
De Bruijn string db.
Validating the reversed deBruijn sequence:
No errors found
Validating the overlaid deBruijn sequence:
4 errors found:
PIN number 1459 missing
PIN number 4591 missing
PIN number 5814 missing
PIN number 8145 missing
"""
dbwithwrap = db+db[0:3]
digits = '0123456789'
errorstrings = []
for d1 in digits:
for d2 in digits:
for d3 in digits:
for d4 in digits:
teststring = d1+d2+d3+d4
if teststring not in dbwithwrap:
errorstrings.append(teststring)
if len(errorstrings) > 0:
print(" "+str(len(errorstrings))+" errors found:")
for e in errorstrings:
print(" PIN number "+e+" missing")
else:
print(" No errors found")
db = de_bruijn(10, 4)
print(" ")
print("The length of the de Bruijn sequence is ", str(len(db)))
print(" ")
print("The first 130 digits of the de Bruijn sequence are: "+db[0:130])
print(" ")
print("The last 130 digits of the de Bruijn sequence are: "+db[-130:])
print(" ")
print("Validating the deBruijn sequence:")
validate(db)
dbreversed = db[::-1]
print(" ")
print("Validating the reversed deBruijn sequence:")
validate(dbreversed)
dboverlaid = db[0:4443]+'.'+db[4444:]
print(" ")
print("Validating the overlaid deBruijn sequence:")
validate(dboverlaid)
- Output:
The length of the de Bruijn sequence is 10000 The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 The last 130 digits of the de Bruijn sequence are: 8976898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999 Validating the deBruijn sequence: No errors found Validating the reversed deBruijn sequence: No errors found Validating the overlaid deBruijn sequence: 4 errors found: PIN number 1459 missing PIN number 4591 missing PIN number 5814 missing PIN number 8145 missing
Racket
#lang racket
(define (de-bruijn k n)
(define a (make-vector (* k n) 0))
(define seq '())
(define (db t p)
(cond
[(> t n) (when (= (modulo n p) 0)
(set! seq (cons (call-with-values
(thunk (vector->values a 1 (add1 p)))
list)
seq)))]
[else (vector-set! a t (vector-ref a (- t p)))
(db (add1 t) p)
(for ([j (in-range (add1 (vector-ref a (- t p))) k)])
(vector-set! a t j)
(db (add1 t) t))]))
(db 1 1)
(define seq* (append* (reverse seq)))
(append seq* (take seq* (sub1 n))))
(define seq (de-bruijn 10 4))
(printf "The length of the de Bruijn sequence is ~a\n\n" (length seq))
(printf "The first 130 digits of the de Bruijn sequence are:\n~a\n\n"
(take seq 130))
(printf "The last 130 digits of the de Bruijn sequence are:\n~a\n\n"
(take-right seq 130))
(define (validate name seq)
(printf "Validating the ~ade Bruijn sequence:\n" name)
(define expected (for/set ([i (in-range 0 10000)]) i))
(define actual (for/set ([a (in-list seq)]
[b (in-list (rest seq))]
[c (in-list (rest (rest seq)))]
[d (in-list (rest (rest (rest seq))))])
(+ (* 1000 a) (* 100 b) (* 10 c) d)))
(define diff (set-subtract expected actual))
(cond
[(set-empty? diff) (printf " No errors found\n")]
[else (for ([n (in-set diff)])
(printf " ~a is missing\n" (~a n #:width 4 #:pad-string "0")))])
(newline))
(validate "" seq)
(validate "reversed " (reverse seq))
(validate "overlaid " (list-update seq 4443 add1))
- Output:
The length of the de Bruijn sequence is 10003 The first 130 digits of the de Bruijn sequence are: (0 0 0 0 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5 0 0 0 6 0 0 0 7 0 0 0 8 0 0 0 9 0 0 1 1 0 0 1 2 0 0 1 3 0 0 1 4 0 0 1 5 0 0 1 6 0 0 1 7 0 0 1 8 0 0 1 9 0 0 2 1 0 0 2 2 0 0 2 3 0 0 2 4 0 0 2 5 0 0 2 6 0 0 2 7 0 0 2 8 0 0 2 9 0 0 3 1 0 0 3 2 0 0 3 3 0 0 3 4 0 0 3 5 0) The last 130 digits of the de Bruijn sequence are: (6 8 9 8 6 8 9 9 6 9 6 9 7 7 6 9 7 8 6 9 7 9 6 9 8 7 6 9 8 8 6 9 8 9 6 9 9 7 6 9 9 8 6 9 9 9 7 7 7 7 8 7 7 7 9 7 7 8 8 7 7 8 9 7 7 9 8 7 7 9 9 7 8 7 8 7 9 7 8 8 8 7 8 8 9 7 8 9 8 7 8 9 9 7 9 7 9 8 8 7 9 8 9 7 9 9 8 7 9 9 9 8 8 8 8 9 8 8 9 9 8 9 8 9 9 9 9 0 0 0) Validating the de Bruijn sequence: No errors found Validating the reversed de Bruijn sequence: No errors found Validating the overlaid de Bruijn sequence: 1459 is missing 4591 is missing 8145 is missing 5814 is missing
Raku
(formerly Perl 6)
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.
# 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';
}
## 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;
- 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 (1st topic).
hard-coded node to be removed
/*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
- 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.
/*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
- output is identical to the 1st REXX version.
Ruby
def deBruijn(k, n)
alphabet = "0123456789"
@a = Array.new(k * n, 0)
@seq = []
def db(k, n, t, p)
if t > n then
if n % p == 0 then
temp = @a[1 .. p]
@seq.concat temp
end
else
@a[t] = @a[t - p]
db(k, n, t + 1, p)
j = @a[t - p] + 1
while j < k do
@a[t] = j # & 0xFF
db(k, n, t + 1, t)
j = j + 1
end
end
end
db(k, n, 1, 1)
buf = ""
for i in @seq
buf <<= alphabet[i]
end
return buf + buf[0 .. n-2]
end
def validate(db)
le = db.length
found = Array.new(10000, 0)
errs = []
# Check all strings of 4 consecutive digits within 'db'
# to see if all 10,000 combinations occur without duplication.
for i in 0 .. le-4
s = db[i .. i+3]
if s.scan(/\D/).empty? then
found[s.to_i] += 1
end
end
for i in 0 .. found.length - 1
if found[i] == 0 then
errs <<= (" PIN number %04d missing" % [i])
elsif found[i] > 1 then
errs <<= (" PIN number %04d occurs %d times" % [i, found[i]])
end
end
if errs.length == 0 then
print " No errors found\n"
else
pl = (errs.length == 1) ? "" : "s"
print " ", errs.length, " error", pl, " found:\n"
for err in errs
print err, "\n"
end
end
end
db = deBruijn(10, 4)
print "The length of the de Bruijn sequence is ", db.length, "\n\n"
print "The first 130 digits of the de Bruijn sequence are: ", db[0 .. 129], "\n\n"
print "The last 130 digits of the de Bruijn sequence are: ", db[-130 .. db.length], "\n\n"
print "Validating the de Bruijn sequence:\n"
validate(db)
print "\n"
db[4443] = '.'
print "Validating the overlaid de Bruijn sequence:\n"
validate(db)
- 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 overlaid de Bruijn sequence: 4 errors found: PIN number 1459 missing PIN number 4591 missing PIN number 5814 missing PIN number 8145 missing
Scala
import scala.collection.mutable.ListBuffer
object DeBruijn {
def deBruijn(k: Int, n: Int): String = {
val a = Array.fill[Byte](k * n)(0)
val seq = new ListBuffer[Byte]()
def db(t: Int, p: Int): Unit = {
if (t > n) {
if (n % p == 0) {
seq ++= a.slice(1, p + 1)
}
} else {
a(t) = a(t - p)
db(t + 1, p)
for (j <- (a(t - p) + 1).until(k)) {
a(t) = j.toByte
db(t + 1, t)
}
}
}
db(1, 1)
val sb = new StringBuilder
seq.foreach(i => sb.append("0123456789".charAt(i)))
sb.append(sb.subSequence(0, n - 1)).toString
}
private def allDigits(s: String): Boolean = s.forall(_.isDigit)
private def validate(db: String): Unit = {
val found = Array.fill(10000)(0)
val errs = ListBuffer[String]()
for (i <- 0 until db.length - 3) {
val s = db.substring(i, i + 4)
if (allDigits(s)) {
val n = s.toInt
found(n) += 1
}
}
for (i <- found.indices) {
if (found(i) == 0) errs += s" PIN number $i is missing"
else if (found(i) > 1) errs += s" PIN number $i occurs ${found(i)} times"
}
if (errs.isEmpty) println(" No errors found")
else {
val pl = if (errs.size == 1) "" else "s"
println(s" ${errs.size} error$pl found:")
errs.foreach(println)
}
}
def main(args: Array[String]): Unit = {
val db = deBruijn(10, 4)
println(s"The length of the de Bruijn sequence is ${db.length}\n")
println(s"The first 130 digits of the de Bruijn sequence are: ${db.take(130)}\n")
println(s"The last 130 digits of the de Bruijn sequence are: ${db.takeRight(130)}\n")
println("Validating the de Bruijn sequence:")
validate(db)
println()
println("Validating the reversed de Bruijn sequence:")
validate(db.reverse)
val overlaidDb = db.updated(4443, '.')
println()
println("Validating the overlaid de Bruijn sequence:")
validate(overlaidDb)
}
}
- 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 is missing PIN number 4591 is missing PIN number 5814 is missing PIN number 8145 is missing
Visual Basic .NET
Imports System.Text
Module Module1
ReadOnly DIGITS As String = "0123456789"
Function DeBruijn(k As Integer, n As Integer) As String
Dim alphabet = DIGITS.Substring(0, k)
Dim a(k * n) As Byte
Dim seq As New List(Of Byte)
Dim db As Action(Of Integer, Integer) = Sub(t As Integer, p As Integer)
If t > n Then
If n Mod p = 0 Then
Dim seg = New ArraySegment(Of Byte)(a, 1, p)
seq.AddRange(seg)
End If
Else
a(t) = a(t - p)
db(t + 1, p)
Dim j = a(t - p) + 1
While j < k
a(t) = j
db(t + 1, t)
j += 1
End While
End If
End Sub
db(1, 1)
Dim buf As New StringBuilder
For Each i In seq
buf.Append(alphabet(i))
Next
Dim b = buf.ToString
Return b + b.Substring(0, n - 1)
End Function
Function AllDigits(s As String) As Boolean
For Each c In s
If c < "0" OrElse "9" < c Then
Return False
End If
Next
Return True
End Function
Sub Validate(db As String)
Dim le = db.Length
Dim found(10000) As Integer
Dim errs As New List(Of String)
' Check all strings of 4 consecutive digits within 'db'
' to see if all 10,000 combinations occur without duplication.
For i = 1 To le - 3
Dim s = db.Substring(i - 1, 4)
If (AllDigits(s)) Then
Dim n As Integer = Nothing
Integer.TryParse(s, n)
found(n) += 1
End If
Next
For i = 1 To 10000
If found(i - 1) = 0 Then
errs.Add(String.Format(" PIN number {0,4} missing", i - 1))
ElseIf found(i - 1) > 1 Then
errs.Add(String.Format(" PIN number {0,4} occurs {1} times", i - 1, found(i - 1)))
End If
Next
Dim lerr = errs.Count
If lerr = 0 Then
Console.WriteLine(" No errors found")
Else
Dim pl = If(lerr = 1, "", "s")
Console.WriteLine(" {0} error{1} found:", lerr, pl)
errs.ForEach(Sub(x) Console.WriteLine(x))
End If
End Sub
Function Reverse(s As String) As String
Dim arr = s.ToCharArray
Array.Reverse(arr)
Return New String(arr)
End Function
Sub Main()
Dim db = DeBruijn(10, 4)
Dim le = db.Length
Console.WriteLine("The length of the de Bruijn sequence is {0}", le)
Console.WriteLine(vbNewLine + "The first 130 digits of the de Bruijn sequence are: {0}", db.Substring(0, 130))
Console.WriteLine(vbNewLine + "The last 130 digits of the de Bruijn sequence are: {0}", db.Substring(le - 130, 130))
Console.WriteLine(vbNewLine + "Validating the deBruijn sequence:")
Validate(db)
Console.WriteLine(vbNewLine + "Validating the reversed deBruijn sequence:")
Validate(Reverse(db))
Dim bytes = db.ToCharArray
bytes(4443) = "."
db = New String(bytes)
Console.WriteLine(vbNewLine + "Validating the overlaid deBruijn sequence:")
Validate(db)
End Sub
End Module
- Output:
The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 The last 130 digits of the de Bruijn sequence are: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 Validating the deBruijn sequence: No errors found Validating the reversed deBruijn sequence: No errors found Validating the overlaid deBruijn sequence: 4 errors found: PIN number 1459 missing PIN number 4591 missing PIN number 5814 missing PIN number 8145 missing
Wren
import "./fmt" for Fmt
import "./str" for Str
var deBruijn = ""
for (n in 0..99) {
var a = Fmt.rjust(2, n, "0")
var a1 = a[0].bytes[0]
var a2 = a[1].bytes[0]
if (a2 >= a1) {
deBruijn = deBruijn + ((a1 == a2) ? String.fromByte(a1): a)
var m = n + 1
while (m <= 99) {
var ms = Fmt.rjust(2, m, "0")
if (ms[1].bytes[0] > a1) deBruijn = deBruijn + a + ms
m = m + 1
}
}
}
deBruijn = deBruijn + "000"
System.print("de Bruijn sequence length: %(deBruijn.count)\n")
System.print("First 130 characters:\n%(deBruijn[0...130])\n")
System.print("Last 130 characters:\n%(deBruijn[-130..-1])\n")
var check = Fn.new { |text|
var res = []
var found = List.filled(10000, 0)
var k = 0
for (i in 0...(text.count-3)) {
var s = text[i..i+3]
if (Str.allDigits(s)) {
k = Num.fromString(s)
found[k] = found[k] + 1
}
}
for (i in 0...10000) {
k = found[i]
if (k != 1) {
var e = " Pin number %(Fmt.dz(4, i)) "
e = e + ((k == 0) ? "missing" : "occurs %(k) times")
res.add(e)
}
}
k = res.count
if (k == 0) {
res = "No errors found"
} else {
var s = (k == 1) ? "" : "s"
res = "%(k) error%(s) found:\n" + res.join("\n")
}
return res
}
System.print("Missing 4 digit PINs in this sequence: %(check.call(deBruijn))")
System.print("Missing 4 digit PINs in the reversed sequence: %(check.call(deBruijn[-1..0]))")
System.print("\n4,444th digit in the sequence: '%(deBruijn[4443])' (setting it to '.')")
deBruijn = deBruijn[0..4442] + "." + deBruijn[4444..-1]
System.print("Re-running checks: %(check.call(deBruijn))")
- Output:
de Bruijn sequence length: 10003 First 130 characters: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 Last 130 characters: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 Missing 4 digit PINs in this sequence: No errors found Missing 4 digit PINs in the reversed sequence: No errors found 4,444th digit in the sequence: '4' (setting it to '.') Re-running checks: 4 errors found: Pin number 1459 missing Pin number 4591 missing Pin number 5814 missing Pin number 8145 missing
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");
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(" "));
- 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