De Bruijn sequences: Difference between revisions
m
→{{header|11l}}: Void
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
|||
| (46 intermediate revisions by 20 users not shown) | |||
Line 1:
{{task}}
{{DISPLAYTITLE:de Bruijn sequences}}
The sequences are named after the Dutch mathematician Nicolaas Govert de Bruijn.
Line 36:
;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 [
key and accepts the last <big> ''n'' </big> digits entered.
Note: [
this, but their software has been updated to not allow a brute-force attack.
;Example:
A [
have ''B'' (10, 4) solutions, with a length of '''10,000''' (digits).
Line 64:
:* Again, perform the (above) verification test.
:* Replace the 4,444<sup>th</sup> digit with a period (.) in the original de Bruijn sequence.
:::* Perform the verification test (again). There should be
Line 71:
Show all output here, on this page.
{{Template:Strings}}
;References:
:* Wikipedia entry: [
:* MathWorld entry: [http://mathworld.wolfram.com/deBruijnSequence.html de Bruijn sequence].
:* An OEIS entry: [
<br><br>
=={{header|
{{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#}}==
{{trans|Kotlin}}
<
using System.Collections.Generic;
using System.Text;
Line 184 ⟶ 1,011:
}
}
}</
{{out}}
<pre>The length of the de Bruijn sequence is 10003
Line 204 ⟶ 1,031:
PIN number 5814 missing
PIN number 8145 missing</pre>
=={{header|C++}}==
{{trans|D}}
<syntaxhighlight lang="cpp">#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;
}</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 missing
PIN number 4591 missing
PIN number 5814 missing
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}}==
{{trans|Kotlin}}
<syntaxhighlight lang="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);
}</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|EasyLang}}==
{{trans|Lua}}
<syntaxhighlight>
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}}==
<
import (
Line 315 ⟶ 1,608:
fmt.Println("\nValidating the overlaid de Bruijn sequence:")
validate(db)
}</
{{out}}
Line 339 ⟶ 1,632:
PIN number 5814 missing
PIN number 8145 missing
</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}}==
{{trans|C++}}
<syntaxhighlight lang="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());
}
}</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|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}}==
<
alphabet = b"0123456789abcdefghijklmnopqrstuvwxyz"[1:k]
a = zeros(UInt8, k * n)
Line 387 ⟶ 2,173:
print("Testing the reversed sequence: "), verifyallPIN(reverse(s), 10, 4)
println("\nAfter replacing 4444th digit with \'.\':"), verifyallPIN(s, 10, 4, 4444)
</
<pre>
The length of the sequence is 10003. The first 130 digits are:
Line 403 ⟶ 2,189:
The sequence does not contain all PINs.
</pre>
=={{header|Kotlin}}==
{{trans|Go}}
<
fun deBruijn(k: Int, n: Int): String {
Line 500 ⟶ 2,285:
println("\nValidating the overlaid deBruijn sequence:")
validate(db)
}</
{{out}}
<pre>The length of the de Bruijn sequence is 10003
Line 520 ⟶ 2,305:
PIN number 5814 missing
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}}==
{{trans|
<
use warnings;
use feature 'say';
Line 560 ⟶ 2,765:
substr $seq, 4443, 1, 5;
say "Incorrect 4 digit PINs in the revised sequence:";
check $seq;</
{{out}}
<pre>de Bruijn sequence length: 10003
Line 582 ⟶ 2,787:
Missing: 1459 4591 5814 8145
Extra: 1559 5591 5815 8155</pre>
=={{header|Phix}}==
{{trans|zkl}}
{{trans|Go}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #004080;">string</span> <span style="color: #000000;">deBruijn</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">deBruijn</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">"000"</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;">"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>
<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>
<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>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<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>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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>
<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;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"No errors found"</span>
<span style="color: #008080;">else</span>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</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;">"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>
<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>
<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>
<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}}
<pre>
Line 722 ⟶ 2,862:
Pin number 5814 missing
Pin number 8145 missing
</pre>
=={{header|Python}}==
<syntaxhighlight lang="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)
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
Line 728 ⟶ 2,984:
{{trans|Go}}
<
(define (de-bruijn k n)
Line 773 ⟶ 3,029:
(validate "" seq)
(validate "reversed " (reverse seq))
(validate "overlaid " (list-update seq 4443 add1))</
{{out}}
Line 798 ⟶ 3,054:
5814 is missing
</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2019.07.1}}
Deviates very slightly from the task spec. Generates a randomized de Bruijn sequence and replaces the 4444th digit with a the digit plus 1 mod 10 rather than a '.', mostly so it can demonstrate detection of extra PINs as well as missing ones.
<syntaxhighlight lang="raku" line># 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;</syntaxhighlight>
{{out|Sample output}}
<pre>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</pre>
=={{header|REXX}}==
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 ===
<
$= /*initialize the de Bruijn sequence. */
#=10; lastNode= (#-2)(#-2)(#-1)(#-2) /*this number is formed when this # ···*/
Line 849 ⟶ 3,174:
if e==0 then e= 'No' /*Gooder English (sic) the error count.*/
say _ e 'errors found.' /*display the number of errors found. */
return</
{{out|output}}
<pre>
Line 878 ⟶ 3,203:
This method slightly bloats the program and slows execution.
<
$= /*initialize the de Bruijn sequence. */
do j=0 for 10; $= $ j; jj= j || j /*compose the left half of the numbers.*/
Line 925 ⟶ 3,250:
if e==0 then e= 'No' /*Gooder English (sic) the error count.*/
say _ e 'errors found.' /*display the number of errors found. */
return</
{{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}}==
{{trans|C#}}
<syntaxhighlight lang="vbnet">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</syntaxhighlight>
{{out}}
<pre>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|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}}==
{{trans|
<
foreach n in (100){
a,a01,a11 := "%02d".fmt(n), a[0,1], a[1,1];
Line 940 ⟶ 3,671:
}
}
dbSeq.append("000");</
<
println("de Bruijn sequence length: ",dbSeq.len());
Line 957 ⟶ 3,688:
println("\n4444th digit in the sequence: ", seqText[4443]);
dbSeq[4443]=".";
println("Setting the 4444th digit and reruning checks: ",chk(dbSeq.text).concat(" "));</
{{out}}
<pre>
| |||