De Bruijn sequences: Difference between revisions

← Older edit

De Bruijn sequences (view source)

Revision as of 08:48, 7 May 2024

102,235 bytes added , 1 month ago

m

→‎{{header|11l}}: Void

Alextretyak

1,481

edits

Revision as of 14:10, 4 September 2019 (view source) rosettacode>Sorawee (+Racket) ← Older edit		Latest revision as of 08:48, 7 May 2024 (view source) Alextretyak (talk \| contribs) m (→‎{{header\|11l}}: Void)
(50 intermediate revisions by 21 users not shown)
Line 1: {{~~draft~~ 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   [~~https~~[wp:~~//en.wikipedia.org/wiki/~~Personal_Identification_Number \|PIN]]-like   code lock that does not have an "enter" key and accepts the last   <big> ''n'' </big>   digits entered. Note:   [~~https~~[wp:~~//en.wikipedia.org/wiki/~~Automated_teller_machine \|automated ~~tell~~teller machines (ATMs)]]   used to work like this,   but their software has been updated to not allow a brute-force attack. ;Example: A   [~~https~~[wp:~~//en.wikipedia.org/wiki/~~digital_door_lock \|digital door lock]]   with a 4-digit code would 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 ~~several~~four PIN codes missing. Line 71: Show all output here, on this page. {{Template:Strings}} ;References: :*   Wikipedia entry:   [~~https~~[wp:~~//en.wikipedia.org/wiki/~~De_Bruijn_sequence \|de Bruijn sequence]]. :*   MathWorld entry:   [http://mathworld.wolfram.com/deBruijnSequence.html de Bruijn sequence]. :*   An  OEIS  entry:   [~~https~~[oeis:~~//oeis.org/~~A166315 \|A166315 lexicographically earliest binary de Bruijn sequences, B(2,n)]]     --- Not B(10,4),   but possibly relevant. <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(KN), 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=KP+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 " ####";I8+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}} <syntaxhighlight lang="csharp">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); } } }</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\|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, kn, 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, 10n-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}}== <~~lang~~syntaxhighlight lang="go">package main import ( Line 189 ⟶ 1,608: fmt.Println("\nValidating the overlaid de Bruijn sequence:") validate(db) }</~~lang~~syntaxhighlight> {{out}} Line 213 ⟶ 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, kn-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}}== <syntaxhighlight lang="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) </syntaxhighlight>{{out}} <pre> 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. </pre> =={{header\|Kotlin}}== {{trans\|Go}} <syntaxhighlight lang="scala">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) }</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\|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, kn 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 := seqLenk; 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, 2n - 2); for j := 1 to n - 1 do wrap[j] := deB[L + j - n + 1]; for j := n to 2n - 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\|~~Perl 6~~Raku}} <~~lang~~syntaxhighlight lang="perl">use strict; use warnings; use feature 'say'; Line 254 ⟶ 2,765: substr $seq, 4443, 1, 5; say "Incorrect 4 digit PINs in the revised sequence:"; check $seq;</~~lang~~syntaxhighlight> {{out}} <pre>de Bruijn sequence length: 10003 Line 276 ⟶ 2,787: Missing: 1459 4591 5814 8145 Extra: 1559 5591 5815 8155</pre> ~~=={{header\|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. ~~<lang perl6># Generate the sequence~~ ~~my $seq;~~ ~~for ^100 {~~ ~~my $a = .fmt: '%02d';~~ ~~next if $a.substr(1,1) < $a.substr(0,1);~~ ~~$seq ~= ($a.substr(0,1) == $a.substr(1,1)) ?? $a.substr(0,1) !! $a;~~ ~~for +$a ^..^ 100 {~~ ~~next if .fmt('%02d').substr(1,1) <= $a.substr(0,1);~~ ~~$seq ~= sprintf "%s%02d", $a, $_ ;~~ } } ~~$seq = $seq.comb.list.rotate((^10000).pick).join;~~ ~~$seq ~= $seq.substr(0,3);~~ ~~sub check ($seq) {~~ ~~my %chk;~~ ~~for ^($seq.chars) { %chk{$seq.substr( $_, 4 )}++ }~~ ~~put 'Missing: ', (^9999).grep( { not %chk{ .fmt: '%04d' } } ).fmt: '%04d';~~ ~~put 'Extra: ', %chk.grep( .value > 1 )».key.sort.fmt: '%04d';~~ } ~~## The Task~~ ~~put "de Bruijn sequence length: " ~ $seq.chars;~~ ~~put "\nFirst 130 characters:\n" ~ $seq.substr( 0, 130 );~~ ~~put "\nLast 130 characters:\n" ~ $seq.substr( * - 130 );~~ ~~put "\nIncorrect 4 digit PINs in this sequence:";~~ ~~check $seq;~~ ~~put "\nIncorrect 4 digit PINs in the reversed sequence:";~~ ~~check $seq.flip;~~ ~~my $digit = $seq.substr(4443,1);~~ ~~put "\nReplacing the 4444th digit, ($digit) with { ($digit += 1) %= 10 }";~~ ~~put "Incorrect 4 digit PINs in the revised sequence:";~~ ~~$seq.substr-rw(4443,1) = $digit;~~ ~~check $seq;</lang>~~ ~~{{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\|Phix}}== {{trans\|zkl}} {{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}} <pre> Line 416 ⟶ 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 422 ⟶ 2,984: {{trans\|Go}} <~~lang~~syntaxhighlight lang="racket">#lang racket (define (de-bruijn k n) Line 467 ⟶ 3,029: (validate "" seq) (validate "reversed " (reverse seq)) (validate "overlaid " (list-update seq 4443 add1))</~~lang~~syntaxhighlight> {{out}} Line 492 ⟶ 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 === <~~lang~~syntaxhighlight lang="rexx">/REXX pgm calculates the de Bruijn sequence for all pin numbers (4 digit decimals). / $= /initialize the de Bruijn sequence. / #=10; lastNode= (#-2)(#-2)(#-1)(#-2) /this number is formed when this # ···/ Line 543 ⟶ 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</~~lang~~syntaxhighlight> {{out\|output}} <pre> Line 572 ⟶ 3,203: This method slightly bloats the program and slows execution. <~~lang~~syntaxhighlight lang="rexx">/REXX pgm calculates the de Bruijn sequence for all pin numbers (4 digit decimals). / $= /initialize the de Bruijn sequence. / do j=0 for 10; $= $ j; jj= j \|\| j /compose the left half of the numbers./ Line 619 ⟶ 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</~~lang~~syntaxhighlight> {{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\|~~Perl6~~Raku}} <~~lang~~syntaxhighlight lang="zkl">dbSeq:=Data(); // a byte/character buffer foreach n in (100){ a,a01,a11 := "%02d".fmt(n), a[0,1], a[1,1]; Line 634 ⟶ 3,671: } } dbSeq.append("000");</~~lang~~syntaxhighlight> <~~lang~~syntaxhighlight lang="zkl">seqText:=dbSeq.text; println("de Bruijn sequence length: ",dbSeq.len()); Line 651 ⟶ 3,688: println("\n4444th digit in the sequence: ", seqText[4443]); dbSeq[4443]="."; println("Setting the 4444th digit and reruning checks: ",chk(dbSeq.text).concat(" "));</~~lang~~syntaxhighlight> {{out}} <pre>