I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

de Bruijn sequences

De Bruijn sequences
You are encouraged to solve this task according to the task description, using any language you may know.

The sequences are named after the Dutch mathematician   Nicolaas Govert de Bruijn.

A note on Dutch capitalization:   Nicolaas' last name is   de Bruijn,   the   de   isn't normally capitalized unless it's the first word in a sentence.   Rosetta Code (more or less by default or by fiat) requires the first word in the task name to be capitalized.

In combinatorial mathematics,   a   de Bruijn sequence   of order   n   on a   size-k   alphabet (computer science)   A   is a cyclic sequence in which every possible   length-n   string (computer science, formal theory)   on   A   occurs exactly once as a contiguous substring.

Such a sequence is denoted by   B(k, n)   and has length   kn,   which is also the number of distinct substrings of length   n   on   A;
de Bruijn sequences are therefore optimally short.

There are:

```                         (k!)k(n-1)   ÷   kn
```

distinct de Bruijn sequences   B(k, n).

For this Rosetta Code task,   a   de Bruijn   sequence is to be generated that can be used to shorten a brute-force attack on a   PIN-like   code lock that does not have an "enter" key and accepts the last   n   digits entered.

Note:   automated teller machines (ATMs)   used to work like this,   but their software has been updated to not allow a brute-force attack.

Example

A   digital door lock   with a 4-digit code would have B (10, 4) solutions,   with a length of   10,000   (digits).

Therefore, only at most     10,000 + 3     (as the solutions are cyclic or wrap-around)   presses are needed to open the lock.

Trying all 4-digit codes separately would require   4 × 10,000   or   40,000   presses.

•   Generate a de Bruijn sequence for a 4-digit (decimal) PIN code.
•   Show the length of the generated de Bruijn sequence.
•   (There are many possible de Bruijn sequences that solve this task,   one solution is shown on the discussion page).
•   Show the first and last   130   digits of the de Bruijn sequence.
•   Verify that all four-digit (decimal)   1,000   PIN codes are contained within the de Bruijn sequence.
•   0000, 0001, 0002, 0003,   ...   9996, 9997, 9998, 9999   (note the leading zeros).
•   Reverse the de Bruijn sequence.
•   Again, perform the (above) verification test.
•   Replace the 4,444th digit with a period (.) in the original de Bruijn sequence.
•   Perform the verification test (again).   There should be four PIN codes missing.

(The last requirement is to ensure that the verification tests performs correctly.   The verification processes should list any and all missing PIN codes.)

References

11l

Translation of: D
`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) -> N      I t > @n         I @n % p == 0            @seq.extend(@a[1 .< p + 1])      E         @a[t] = @a[t - p]         @db(t + 1, p)         V j = @a[t - p] + 1         L j < @k            @a[t] = j [&] F'F            @db(t + 1, t)            j++    db(1, 1)   V buf = ‘’   L(i) seq      buf ‘’= alphabet[i]    R buf‘’buf[0 .< n - 1] F validate(db)   V found = [0] * 10'000   [String] errs    L(i) 0 .< db.len - 3      V s = db[i .< i + 4]      I s.is_digit()         found[Int(s)]++    L(i) 10'000      I found[i] == 0         errs [+]= ‘    PIN number #04 missing’.format(i)      E I found[i] > 1         errs [+]= ‘    PIN number #04 occurs #. times’.format(i, found[i])    I errs.empty      print(‘  No errors found’)   E      V pl = I errs.len == 1 {‘’} E ‘s’      print(‘  ’String(errs.len)‘ error’pl‘ found:’)      L(err) errs         print(err) V db = deBruijn(10, 4) print(‘The length of the de Bruijn sequence is ’db.len)print("\nThe first 130 digits of the de Bruijn sequence are: "db[0.<130])print("\nThe last 130 digits of the de Bruijn sequence are: "db[(len)-130..]) print("\nValidating the deBruijn sequence:")validate(db) print("\nValidating the reversed deBruijn sequence:")validate(reversed(db)) db[4443] = ‘.’print("\nValidating the overlaid deBruijn sequence:")validate(db)`
Output:
```The length of the de Bruijn sequence is 10003

The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

The last 130 digits of the de Bruijn sequence are: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Validating the deBruijn sequence:
No errors found

Validating the reversed deBruijn sequence:
No errors found

Validating the overlaid deBruijn sequence:
4 errors found:
PIN number 1459 missing
PIN number 4591 missing
PIN number 5814 missing
PIN number 8145 missing
```

8080 Assembly

`bdos:	equ	5	; BDOS entry point	putch:	equ	2	; Write character to consoleputs:	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,arrzloop:	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,3wrap:	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	retdbelse:	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,valvzero:	mov	m,d	inx	h	dcx	b	mov	a,b	ora	c	jnz	vzero	lxi	h,seq	; Sequence pointerdonum:	push	h	; Store sequence pointer	push	h	; Push two copies	lxi	h,0	; Current 4-digit number	mvi	c,4	; Number has 4 digitsdgtadd:	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 missingvnum:	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 addressvnext:	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 HLrvrs:	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 registersputhl:	push	h	; save registers	push	d	push	b	lxi	b,nbuf	; number buffer pointer	push	b	; keep it on the stackdgt:	lxi	b,-10	lxi	d,-1dgtdiv:	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 HLp130:	push	h	push	d	push	b	mvi	b,130	; 130 digitsp130l:	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 newlinepnl:	lxi	d,snl	;;;	print string in DE, saving registerspstr:	push	h	; store registers	push	d	push 	bpstr_:	mvi	c,puts	; print string using CP/M	call	bdosrsreg:	pop	b	; restore registers	pop	d	pop 	h	retsnl:	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 buffernbuf:	db	' \$'arr:	equ	(\$/256+1)*256	; Place to store a[] (page-aligned)val:	equ	arr+40		; Place to store validation flagsseq:	equ	val+10000	; Place to store De Bruijn sequence`
Output:
```Length: 10003
First 130: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350
Last 130: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000
Verifying... none missing
Reversing...
Verifying... none missing
Set seq[4444] to `.`...
Verifying... 1459 4591 5914 8145 missing```

8086 Assembly

`putch:	equ	2	; Print characterputs:	equ	9	; Print string	cpu	8086	bits	16section	.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 AXputax:	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 SIp130:	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 DIrvrs:	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	retsection	.dataslen:	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	.bssarr:	resb	40		; a[]val:	resb	10000		; validation arrayseq:	equ	\$`
Output:
```Length: 10003
First 130: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350
Last 130: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000
Verifying... none missing.
Reversing...
Verifying... none missing.
Set seq[4444] to `.`...
Verifying... 1460 4592 5915 8146 missing.```

Translation of: D
`with Ada.Text_IO;              use Ada.Text_IO;with Ada.Strings.Fixed;        use Ada.Strings;with Ada.Strings.Unbounded; procedure De_Bruijn_Sequences is    function De_Bruijn (K, N : Positive) return String   is      use Ada.Strings.Unbounded;       Alphabet : constant String := "0123456789";       subtype Decimal is Integer range 0 .. 9;      type Decimal_Array is array (Natural range <>) of Decimal;       A   : Decimal_Array (0 .. K * N - 1) := (others => 0);      Seq : Unbounded_String;       procedure Db (T, P : Positive) is      begin         if T > N then            if N mod P = 0 then               for E of A (1 .. P) loop                  Append (Seq, Alphabet (Alphabet'First + E));               end loop;            end if;         else            A (T) := A (T - P);            Db (T + 1, P);            for J in A (T - P) + 1 .. K - 1 loop               A (T) := J;               Db (T + 1, T);            end loop;         end if;      end Db;    begin      Db (1, 1);      return To_String (Seq) & Slice (Seq, 1, N - 1);   end De_Bruijn;    function Image (Value : Integer) return String   is (Fixed.Trim (Value'Image, Left));    function PIN_Image (Value : Integer) return String   is (Fixed.Tail (Image (Value), Count => 4, Pad => '0'));    procedure Validate (Db : String)   is      Found  : array (0 .. 9_999) of Natural := (others => 0);      Errors : Natural := 0;   begin       --  Check all strings of 4 consecutive digits within 'db'      --  to see if all 10,000 combinations occur without duplication.      for A in Db'First .. Db'Last - 3 loop         declare            PIN : String renames Db (A .. A + 4 - 1);         begin            if (for all Char of PIN => Char in '0' .. '9') then               declare                  N : constant Integer := Integer'Value (PIN);                  F : Natural renames Found (N);               begin                  F := F + 1;               end;            end if;         end;      end loop;       for I in 0_000 .. 9_999 loop         if Found (I) = 0 then            Put_Line ("  PIN number " & PIN_Image (I) & " missing");            Errors := Errors + 1;         elsif Found (I) > 1 then            Put_Line ("  PIN number " & PIN_Image (I) & " occurs "                        & Image (Found (I)) & " times");            Errors := Errors + 1;         end if;      end loop;       case Errors is         when 0 =>  Put_Line ("  No errors found");         when 1 =>  Put_Line ("  1 error found");         when others =>            Put_Line ("  " & Image (Errors) & " errors found");      end case;   end Validate;    function Backwards (S : String) return String is      R : String (S'Range);   begin      for A in 0 .. S'Length - 1 loop         R (R'Last - A) := S (S'First + A);      end loop;      return R;   end Backwards;    DB  : constant String := De_Bruijn (K => 10, N => 4);   Rev : constant String := Backwards (DB);   Ovl :          String := DB;begin   Put_Line ("The length of the de Bruijn sequence is " & DB'Length'Image);   New_Line;    Put_Line ("The first 130 digits of the de Bruijn sequence are: ");   Put_Line ("  " & Fixed.Head (DB, 130));   New_Line;    Put_Line ("The last 130 digits of the de Bruijn sequence are: ");   Put_Line ("  " & Fixed.Tail (DB, 130));   New_Line;    Put_Line ("Validating the deBruijn sequence:");   Validate (DB);   New_Line;    Put_Line ("Validating the reversed deBruijn sequence:");   Validate (Rev);   New_Line;    Ovl (4444) := '.';   Put_Line ("Validating the overlaid deBruijn sequence:");   Validate (Ovl);   New_Line;end De_Bruijn_Sequences;`
Output:
```The length of the de Bruijn sequence is  10003

The first 130 digits of the de Bruijn sequence are:
0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

The last 130 digits of the de Bruijn sequence are:
6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Validating the deBruijn sequence:
No errors found

Validating the reversed deBruijn sequence:
No errors found

Validating the overlaid deBruijn sequence:
PIN number 1459 missing
PIN number 4591 missing
PIN number 5814 missing
PIN number 8145 missing
4 errors found
```

BASIC

`10 DEFINT A-Z20 K = 10: N = 430 DIM A(K*N), S(K^N+N), T(5), P(5), V(K^N\8)40 GOSUB 20050 PRINT "Length: ",S60 PRINT "First 130:"70 FOR I=0 TO 129: PRINT USING "#";S(I);: NEXT80 PRINT: PRINT "Last 130:"90 FOR I=S-130 TO S-1: PRINT USING "#";S(I);: NEXT100 PRINT110 GOSUB 600120 PRINT "Reversing...": GOSUB 500: GOSUB 600: GOSUB 500130 PRINT USING "Replacing 4444'th element (#):";S(4443)140 S(4443) = -1 : REM 0-indexed, and using integers150 GOSUB 600160 END200 REM Generate De Bruijn sequence given K and N210 T(R) = 1: P(R) = 1220 IF T(R) > N GOTO 380230 A(T(R)) = A(T(R)-P(R))240 R = R+1250 T(R) = T(R-1)+1260 P(R) = P(R-1)270 GOSUB 220280 R = R-1290 FOR J = A(T(R)-P(R))+1 TO K-1300 A(T(R)) = J310 R = R+1320 T(R) = T(R-1)+1330 P(R) = T(R-1)340 GOSUB 220350 R = R-1355 J = A(T(R))360 NEXT370 RETURN380 IF N MOD P(R) THEN RETURN390 FOR I = 1 TO P(R)400 S(S) = A(I)410 S = S+1420 NEXT430 RETURN500 REM Reverse the sequence510 FOR I=0 TO S\2520 J = S(I)530 S(I) = S(S-I)540 S(S-I) = J550 NEXT560 RETURN600 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): NEXT630 FOR I=0 TO K^N\8-1: V(I)=0: NEXT640 FOR I=0 TO S650 P=0660 FOR J=0 TO N-1662 D=S(I+J)663 IF D<0 GOTO 690665 P=K*P+D669 NEXT J670 X=P\8680 V(X) = V(X) OR 2^(P AND 7)690 NEXT I700 M=1710 FOR I=0 TO K^N\8-1720 IF V(I)=255 GOTO 760730 FOR J=0 TO 7740 IF (V(I) AND 2^J)=0 THEN M=0: PRINT USING " ####";I*8+J;750 NEXT760 NEXT770 IF M THEN PRINT " none";780 PRINT " missing."790 RETURN`
Output:
```Length:        10000
First 130:
00001000200030004000500060007000800090011001200130014001500160017001800190021002
20023002400250026002700280029003100320033003400350
Last 130:
89768986899696977697869796987698869896997699869997777877797788778977987799787879
78887889789878997979887989799879998888988998989999
Validating... none missing.
Reversing...
Validating... none missing.
Replacing 4444'th element (4):
Validating... 1459 4591 5814 8145 missing.```

C#

Translation of: Kotlin
`using System;using System.Collections.Generic;using System.Text; namespace DeBruijn {    class Program {        const string digits = "0123456789";         static string DeBruijn(int k, int n) {            var alphabet = digits.Substring(0, k);            var a = new byte[k * n];            var seq = new List<byte>();            void db(int t, int p) {                if (t > n) {                    if (n % p == 0) {                        seq.AddRange(new ArraySegment<byte>(a, 1, p));                    }                } else {                    a[t] = a[t - p];                    db(t + 1, p);                    var j = a[t - p] + 1;                    while (j < k) {                        a[t] = (byte)j;                        db(t + 1, t);                        j++;                    }                }            }            db(1, 1);            var buf = new StringBuilder();            foreach (var i in seq) {                buf.Append(alphabet[i]);            }            var b = buf.ToString();            return b + b.Substring(0, n - 1);        }         static bool AllDigits(string s) {            foreach (var c in s) {                if (c < '0' || '9' < c) {                    return false;                }            }            return true;        }         static void Validate(string db) {            var le = db.Length;            var found = new int[10_000];            var errs = new List<string>();            // Check all strings of 4 consecutive digits within 'db'            // to see if all 10,000 combinations occur without duplication.            for (int i = 0; i < le - 3; i++) {                var s = db.Substring(i, 4);                if (AllDigits(s)) {                    int.TryParse(s, out int n);                    found[n]++;                }            }            for (int i = 0; i < 10_000; i++) {                if (found[i] == 0) {                    errs.Add(string.Format("    PIN number {0,4} missing", i));                } else if (found[i] > 1) {                    errs.Add(string.Format("    PIN number {0,4} occurs {1} times", i, found[i]));                }            }            var lerr = errs.Count;            if (lerr == 0) {                Console.WriteLine("  No errors found");            } else {                var pl = lerr == 1 ? "" : "s";                Console.WriteLine("  {0} error{1} found:", lerr, pl);                errs.ForEach(Console.WriteLine);            }        }         static string Reverse(string s) {            char[] arr = s.ToCharArray();            Array.Reverse(arr);            return new string(arr);        }         static void Main() {            var db = DeBruijn(10, 4);            var le = db.Length;             Console.WriteLine("The length of the de Bruijn sequence is {0}", le);            Console.WriteLine("\nThe first 130 digits of the de Bruijn sequence are: {0}", db.Substring(0, 130));            Console.WriteLine("\nThe last 130 digits of the de Bruijn sequence are: {0}", db.Substring(le - 130, 130));             Console.WriteLine("\nValidating the deBruijn sequence:");            Validate(db);             Console.WriteLine("\nValidating the reversed deBruijn sequence:");            Validate(Reverse(db));             var bytes = db.ToCharArray();            bytes[4443] = '.';            db = new string(bytes);            Console.WriteLine("\nValidating the overlaid deBruijn sequence:");            Validate(db);        }    }}`
Output:
```The length of the de Bruijn sequence is 10003

The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

The last 130 digits of the de Bruijn sequence are: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Validating the deBruijn sequence:
No errors found

Validating the reversed deBruijn sequence:
No errors found

Validating the overlaid deBruijn sequence:
4 errors found:
PIN number 1459 missing
PIN number 4591 missing
PIN number 5814 missing
PIN number 8145 missing```

C++

Translation of: D
`#include <algorithm>#include <functional>#include <iostream>#include <iterator>#include <string>#include <sstream>#include <vector> typedef unsigned char byte; std::string deBruijn(int k, int n) {    std::vector<byte> a(k * n, 0);    std::vector<byte> seq;     std::function<void(int, int)> db;    db = [&](int t, int p) {        if (t > n) {            if (n % p == 0) {                for (int i = 1; i < p + 1; i++) {                    seq.push_back(a[i]);                }            }        } else {            a[t] = a[t - p];            db(t + 1, p);            auto j = a[t - p] + 1;            while (j < k) {                a[t] = j & 0xFF;                db(t + 1, t);                j++;            }        }    };     db(1, 1);    std::string buf;    for (auto i : seq) {        buf.push_back('0' + i);    }    return buf + buf.substr(0, n - 1);} bool allDigits(std::string s) {    for (auto c : s) {        if (c < '0' || '9' < c) {            return false;        }    }    return true;} void validate(std::string db) {    auto le = db.size();    std::vector<int> found(10000, 0);    std::vector<std::string> errs;     // Check all strings of 4 consecutive digits within 'db'    // to see if all 10,000 combinations occur without duplication.    for (size_t i = 0; i < le - 3; i++) {        auto s = db.substr(i, 4);        if (allDigits(s)) {            auto n = stoi(s);            found[n]++;        }    }     for (int i = 0; i < 10000; i++) {        if (found[i] == 0) {            std::stringstream ss;            ss << "    PIN number " << i << " missing";            errs.push_back(ss.str());        } else if (found[i] > 1) {            std::stringstream ss;            ss << "    PIN number " << i << " occurs " << found[i] << " times";            errs.push_back(ss.str());        }    }     if (errs.empty()) {        std::cout << "  No errors found\n";    } else {        auto pl = (errs.size() == 1) ? "" : "s";        std::cout << "  " << errs.size() << " error" << pl << " found:\n";        for (auto e : errs) {            std::cout << e << '\n';        }    }} int main() {    std::ostream_iterator<byte> oi(std::cout, "");    auto db = deBruijn(10, 4);     std::cout << "The length of the de Bruijn sequence is " << db.size() << "\n\n";    std::cout << "The first 130 digits of the de Bruijn sequence are: ";    std::copy_n(db.cbegin(), 130, oi);    std::cout << "\n\nThe last 130 digits of the de Bruijn sequence are: ";    std::copy(db.cbegin() + (db.size() - 130), db.cend(), oi);    std::cout << "\n";     std::cout << "\nValidating the de Bruijn sequence:\n";    validate(db);     std::cout << "\nValidating the reversed de Bruijn sequence:\n";    auto rdb = db;    std::reverse(rdb.begin(), rdb.end());    validate(rdb);     auto by = db;    by[4443] = '.';    std::cout << "\nValidating the overlaid de Bruijn sequence:\n";    validate(by);     return 0;}`
Output:
```The length of the de Bruijn sequence is 10003

The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

The last 130 digits of the de Bruijn sequence are: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Validating the de Bruijn sequence:
No errors found

Validating the reversed de Bruijn sequence:
No errors found

Validating the overlaid de Bruijn sequence:
4 errors found:
PIN number 1459 missing
PIN number 4591 missing
PIN number 5814 missing
PIN number 8145 missing```

CLU

`% Generate the De Bruijn sequence consisiting of N-digit numbersde_bruijn = cluster is generate    rep = null    own k: int := 0    own n: int := 0    own a: array[int] := array[int]\$[]    own seq: array[int] := array[int]\$[]     generate = proc (k_, n_: int) returns (string)        k := k_        n := n_        a := array[int]\$fill(0, k*n, 0)        seq := array[int]\$[]        db(1, 1)        s: stream := stream\$create_output()        for i: int in array[int]\$elements(seq) do            stream\$puts(s, int\$unparse(i))        end        return(stream\$get_contents(s))    end generate     db = proc (t, p: int)        if t>n then             if n//p = 0 then                for i: int in int\$from_to(1, p) do                    array[int]\$addh(seq, a[i])                end            end        else            a[t] := a[t - p]            db(t+1, p)            for j: int in int\$from_to(a[t - p] + 1, k-1) do                a[t] := j                db(t + 1, t)            end        end    end dbend de_bruijn % Reverse a stringreverse = 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 valuesfind_missing = proc (db: string, n: int) returns (sequence[string])    db := db || string\$substr(db, 1, n) % wrap    missing: array[string] := array[string]\$[]    s: stream := stream\$create_output()    for i: int in int\$from_to(0, 10**n-1) do        %s: stream := stream\$create_output()        stream\$reset(s)        stream\$putzero(s, int\$unparse(i), n)        val: string := stream\$get_contents(s)        if string\$indexs(val, db) = 0 then            array[string]\$addh(missing, val)        end    end    return(sequence[string]\$a2s(missing))end find_missing % Report all missing values, or 'none'.validate = proc (s: stream, db: string, n: int)    stream\$puts(s, "Validating...")    missing: sequence[string] := find_missing(db, n)    for v: string in sequence[string]\$elements(missing) do        stream\$puts(s, " " || v)    end    if sequence[string]\$size(missing) = 0 then        stream\$puts(s, " none")    end    stream\$putl(s, " missing.")end validate start_up = proc ()    po: stream := stream\$primary_output()     % Generate the De Bruijn sequence for 4-digit numbers    db: string := de_bruijn\$generate(10, 4)     % Report length and first and last digits    stream\$putl(po, "Length: " || int\$unparse(string\$size(db)))    stream\$putl(po, "First 130 characters:")    stream\$putl(po, string\$substr(db, 1, 130))    stream\$putl(po, "Last 130 characters:")    stream\$putl(po, string\$substr(db, string\$size(db)-130, 130))     % See if there are any missing values in the sequence    validate(po, db, 4)     % Reverse and validate again    stream\$putl(po, "Reversing...")    validate(po, reverse(db), 4)     % Replace the 4444'th element with '.' and validate again    stream\$putl(po, "Setting the 4444'th character to '.'...")    db := string\$substr(db, 1, 4443) || "." || string\$rest(db, 4445)    validate(po, db, 4)end start_up`
Output:
```Length: 10000
First 130 characters:
0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350
Last 130 characters:
6897689868996969776978697969876988698969976998699977778777977887789779877997878797888788978987899797988798979987999888898899898999
Validating... none missing.
Reversing...
Validating... none missing.
Setting the 4444'th character to '.'...
Validating... 1459 4591 5814 8145 missing.```

D

Translation of: Kotlin
`import std.array;import std.conv;import std.format;import std.range;import std.stdio; immutable DIGITS = "0123456789"; string deBruijn(int k, int n) {    auto alphabet = DIGITS[0..k];    byte[] a;    a.length = k * n;    byte[] seq;     void db(int t, int p) {        if (t > n) {            if (n % p == 0) {                auto temp = a[1..p + 1];                seq ~= temp;            }        } else {            a[t] = a[t - p];            db(t + 1, p);            auto j = a[t - p] + 1;            while (j < k) {                a[t] = cast(byte)(j & 0xFF);                db(t + 1, t);                j++;            }        }    }    db(1, 1);    string buf;    foreach (i; seq) {        buf ~= alphabet[i];    }     return buf ~ buf[0 .. n - 1];} bool allDigits(string s) {    foreach (c; s) {        if (c < '0' || '9' < c) {            return false;        }    }    return true;} void validate(string db) {    auto le = db.length;    int[10_000] found;    string[] errs;    // Check all strings of 4 consecutive digits within 'db'    // to see if all 10,000 combinations occur without duplication.    foreach (i; 0 .. le - 3) {        auto s = db[i .. i + 4];        if (allDigits(s)) {            auto n = s.to!int;            found[n]++;        }    }    foreach (i; 0 .. 10_000) {        if (found[i] == 0) {            errs ~= format("    PIN number %04d missing", i);        } else if (found[i] > 1) {            errs ~= format("    PIN number %04d occurs %d times", i, found[i]);        }    }    if (errs.empty) {        writeln("  No errors found");    } else {        auto pl = (errs.length == 1) ? "" : "s";        writeln("  ", errs.length, " error", pl, " found:");        writefln("%-(%s\n%)", errs);    }} void main() {    auto db = deBruijn(10, 4);     writeln("The length of the de Bruijn sequence is ", db.length);    writeln("\nThe first 130 digits of the de Bruijn sequence are: ", db[0 .. 130]);    writeln("\nThe last 130 digits of the de Bruijn sequence are: ", db[\$ - 130 .. \$]);     writeln("\nValidating the deBruijn sequence:");    validate(db);     writeln("\nValidating the reversed deBruijn sequence:");    validate(db.retro.to!string);     auto by = db.dup;    by[4443] = '.';    db = by.idup;    writeln("\nValidating the overlaid deBruijn sequence:");    validate(db);}`
Output:
```The length of the de Bruijn sequence is 10003

The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

The last 130 digits of the de Bruijn sequence are: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Validating the deBruijn sequence:
No errors found

Validating the reversed deBruijn sequence:
No errors found

Validating the overlaid deBruijn sequence:
4 errors found:
PIN number 1459 missing
PIN number 4591 missing
PIN number 5814 missing
PIN number 8145 missing```

Go

`package main import (    "bytes"    "fmt"    "strconv"    "strings") const digits = "0123456789" func deBruijn(k, n int) string {    alphabet := digits[0:k]    a := make([]byte, k*n)    var seq []byte    var db func(int, int) // recursive closure    db = func(t, p int) {        if t > n {            if n%p == 0 {                seq = append(seq, a[1:p+1]...)            }        } else {            a[t] = a[t-p]            db(t+1, p)            for j := int(a[t-p] + 1); j < k; j++ {                a[t] = byte(j)                db(t+1, t)            }        }    }    db(1, 1)    var buf bytes.Buffer    for _, i := range seq {        buf.WriteByte(alphabet[i])    }    b := buf.String()    return b + b[0:n-1] // as cyclic append first (n-1) digits} func allDigits(s string) bool {    for _, b := range s {        if b < '0' || b > '9' {            return false        }    }    return true} func validate(db string) {    le := len(db)    found := make([]int, 10000)    var errs []string    // Check all strings of 4 consecutive digits within 'db'    // to see if all 10,000 combinations occur without duplication.    for i := 0; i < le-3; i++ {        s := db[i : i+4]        if allDigits(s) {            n, _ := strconv.Atoi(s)            found[n]++        }    }    for i := 0; i < 10000; i++ {        if found[i] == 0 {            errs = append(errs, fmt.Sprintf("    PIN number %04d missing", i))        } else if found[i] > 1 {            errs = append(errs, fmt.Sprintf("    PIN number %04d occurs %d times", i, found[i]))        }    }    lerr := len(errs)    if lerr == 0 {        fmt.Println("  No errors found")    } else {        pl := "s"        if lerr == 1 {            pl = ""        }        fmt.Printf("  %d error%s found:\n", lerr, pl)        fmt.Println(strings.Join(errs, "\n"))    }} func reverse(s string) string {    bytes := []byte(s)    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {        bytes[i], bytes[j] = bytes[j], bytes[i]    }    return string(bytes)} func main() {    db := deBruijn(10, 4)    le := len(db)    fmt.Println("The length of the de Bruijn sequence is", le)    fmt.Println("\nThe first 130 digits of the de Bruijn sequence are:")    fmt.Println(db[0:130])    fmt.Println("\nThe last 130 digits of the de Bruijn sequence are:")    fmt.Println(db[le-130:])    fmt.Println("\nValidating the de Bruijn sequence:")    validate(db)     fmt.Println("\nValidating the reversed de Bruijn sequence:")    dbr := reverse(db)    validate(dbr)     bytes := []byte(db)    bytes[4443] = '.'    db = string(bytes)    fmt.Println("\nValidating the overlaid de Bruijn sequence:")    validate(db)}`
Output:
```The length of the de Bruijn sequence is 10003

The first 130 digits of the de Bruijn sequence are:
0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

The last 130 digits of the de Bruijn sequence are:
6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Validating the de Bruijn sequence:
No errors found

Validating the reversed de Bruijn sequence:
No errors found

Validating the overlaid de Bruijn sequence:
4 errors found:
PIN number 1459 missing
PIN number 4591 missing
PIN number 5814 missing
PIN number 8145 missing
```

Groovy

Translation of: Java
`import java.util.function.BiConsumer class DeBruijn {    interface Recursable<T, U> {        void apply(T t, U u, Recursable<T, U> r);    }     static <T, U> BiConsumer<T, U> recurse(Recursable<T, U> f) {        return { t, u -> f.apply(t, u, f) }    }     private static String deBruijn(int k, int n) {        byte[] a = new byte[k * n]        Arrays.fill(a, (byte) 0)         List<Byte> seq = new ArrayList<>()         BiConsumer<Integer, Integer> db = recurse({ int t, int p, f ->            if (t > n) {                if (n % p == 0) {                    for (int i = 1; i < p + 1; ++i) {                        seq.add(a[i])                    }                }            } else {                a[t] = a[t - p]                f.apply(t + 1, p, f)                int j = a[t - p] + 1                while (j < k) {                    a[t] = (byte) (j & 0xFF)                    f.apply(t + 1, t, f)                    j++                }            }        })        db.accept(1, 1)         StringBuilder sb = new StringBuilder()        for (Byte i : seq) {            sb.append("0123456789".charAt(i))        }         sb.append(sb.subSequence(0, n - 1))        return sb.toString()    }     private static boolean allDigits(String s) {        for (int i = 0; i < s.length(); ++i) {            char c = s.charAt(i)            if (!Character.isDigit(c)) {                return false            }        }        return true    }     private static void validate(String db) {        int le = db.length()        int[] found = new int[10_000]        Arrays.fill(found, 0)        List<String> errs = new ArrayList<>()         // Check all strings of 4 consecutive digits within 'db'        // to see if all 10,000 combinations occur without duplication.        for (int i = 0; i < le - 3; ++i) {            String s = db.substring(i, i + 4)            if (allDigits(s)) {                int n = Integer.parseInt(s)                found[n]++            }        }         for (int i = 0; i < 10_000; ++i) {            if (found[i] == 0) {                errs.add(String.format("    PIN number %d is missing", i))            } else if (found[i] > 1) {                errs.add(String.format("    PIN number %d occurs %d times", i, found[i]))            }        }         if (errs.isEmpty()) {            System.out.println("    No errors found")        } else {            String pl = (errs.size() == 1) ? "" : "s"            System.out.printf("  %d error%s found:\n", errs.size(), pl)            errs.forEach(System.out.&println)        }    }     static void main(String[] args) {        String db = deBruijn(10, 4)         System.out.printf("The length of the de Bruijn sequence is %d\n\n", db.length())        System.out.printf("The first 130 digits of the de Bruijn sequence are: %s\n\n", db.substring(0, 130))        System.out.printf("The last 130 digits of the de Bruijn sequence are: %s\n\n", db.substring(db.length() - 130))         System.out.println("Validating the de Bruijn sequence:")        validate(db)         StringBuilder sb = new StringBuilder(db)        String rdb = sb.reverse().toString()        System.out.println()        System.out.println("Validating the de Bruijn sequence:")        validate(rdb)         sb = new StringBuilder(db)        sb.setCharAt(4443, '.' as char)        System.out.println()        System.out.println("Validating the overlaid de Bruijn sequence:")        validate(sb.toString())    }}`
Output:
```The length of the de Bruijn sequence is 10003

The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

The last 130 digits of the de Bruijn sequence are: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Validating the de Bruijn sequence:
No errors found

Validating the de Bruijn sequence:
No errors found

Validating the overlaid de Bruijn sequence:
4 errors found:
PIN number 1459 is missing
PIN number 4591 is missing
PIN number 5814 is missing
PIN number 8145 is missing```

Permutation-based

Straight-forward implementation of inverse Burrows—Wheeler transform [1] is reasonably efficient for the task (about a milliseconds for B(10,4) in GHCi).

`import Data.Listimport Data.Map ((!))import qualified Data.Map as M -- represents a permutation in a cycle notationcycleForm :: [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 sdeBruijn :: Ord a => [a] -> Int -> [a]deBruijn s n = let lw = concat \$ lyndonWords n s               in lw ++ take (n-1) lw`
```λ> cycleForm [1,4,3,2,0]
[[1,4,0],[3,2]]

λ> lyndonWords "ab" 3
["a","aab","abb","b"]

λ> deBruijn "ab" 3
"aaababbbaa"```

`import Control.Monad (replicateM) main = do  let symbols = ['0'..'9']  let db = deBruijn symbols 4  putStrLn \$ "The length of de Bruijn sequence: " ++ show (length db)  putStrLn \$ "The first 130 symbols are:\n" ++ show (take 130 db)  putStrLn \$ "The last 130 symbols are:\n" ++ show (drop (length db - 130) db)   let words = replicateM 4 symbols  let validate db  = filter (not . (`isInfixOf` db)) words  putStrLn \$ "Words not in the sequence: " ++ unwords (validate db)   let db' = a ++ ('.': tail b) where (a,b) = splitAt 4444 db  putStrLn \$ "Words not in the corrupted sequence: " ++ unwords (validate db') `
```λ> main
The length of de Bruijn sequence: 10003
The first 130 symbols are:
"0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350"
The last 130 symbols are:
"6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000"
Words not in the sequence:
Words not in the corrupted sequence: 1459 4591 5914 8145```

Array-based

Translation of: Python
`import Control.Monad.Stateimport Data.Array (Array, listArray, (!), (//))import qualified Data.Array as A deBruijn :: [a] -> Int -> [a]deBruijn s n =  let    k = length s     db :: Int -> Int -> State (Array Int Int) [Int]        db t p =      if t > n      then         if n `mod` p == 0        then get >>= \a -> return [ a ! k | k <- [1 .. p]]        else return []      else do        a <- get        x <- setArray t (a ! (t-p)) >> db (t+1) p        a <- get        y <- sequence [ setArray t j >> db (t+1) t                      | j <- [a ! (t-p) + 1 .. k - 1] ]        return \$ x ++ concat y     setArray i x = modify (// [(i, x)])     seqn = db 1 1 `evalState` listArray (0, k*n-1) (repeat 0)   in [ s !! i | i <- seqn ++ take (n-1) seqn ]`

J

definitions. The C. verb computes the cycles. J's sort is not a stable sort.

`NB. implement inverse Burrows—Wheeler transform sequence method repeat_alphabet=:  [: , [: i.&> (^ <:) # [assert 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -: 2 repeat_alphabet 4 de_bruijn=: ({~ ([: ; [: C. /:^:2))@:repeat_alphabet     NB. K de_bruijn N pins=: #&10 #: [: i. 10&^   NB. pins y  generates all y digit PINsgroups=: [ ]\ ] , ({.~ <:)~    NB. length x infixes of sequence y cyclically extended by x-1verify_PINs=: (/:[email protected]:groups -: [email protected]:[)  NB. LENGTH verify_PINs SEQUENCE `
`   NB. A is the sequence   A=: 10 de_bruijn 4    NB. tally A   #A10000    NB. literally the first and final 130 digits   Num_j_ {~ 130 ({. ,: ({.~ -)~) A00001010011011110002100201021102020012101201121112021212002210220122112202221222200031003200301031103210302031203220303001310132019469956996699769986990799179927993799479957996799779987990899189928993899489958996899789988990999199929993999499959996999799989999    NB. verifications.  seriously?   4 verify_PINs A1   4 (verify_PINs |.) A1   4 verify_PINs (a.i.'.') (<: 4444)} A0 `

Java

Translation of: C++
`import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.function.BiConsumer; public class DeBruijn {    public interface Recursable<T, U> {        void apply(T t, U u, Recursable<T, U> r);    }     public static <T, U> BiConsumer<T, U> recurse(Recursable<T, U> f) {        return (t, u) -> f.apply(t, u, f);    }     private static String deBruijn(int k, int n) {        byte[] a = new byte[k * n];        Arrays.fill(a, (byte) 0);         List<Byte> seq = new ArrayList<>();         BiConsumer<Integer, Integer> db = recurse((t, p, f) -> {            if (t > n) {                if (n % p == 0) {                    for (int i = 1; i < p + 1; ++i) {                        seq.add(a[i]);                    }                }            } else {                a[t] = a[t - p];                f.apply(t + 1, p, f);                int j = a[t - p] + 1;                while (j < k) {                    a[t] = (byte) (j & 0xFF);                    f.apply(t + 1, t, f);                    j++;                }            }        });        db.accept(1, 1);         StringBuilder sb = new StringBuilder();        for (Byte i : seq) {            sb.append("0123456789".charAt(i));        }         sb.append(sb.subSequence(0, n - 1));        return sb.toString();    }     private static boolean allDigits(String s) {        for (int i = 0; i < s.length(); ++i) {            char c = s.charAt(i);            if (!Character.isDigit(c)) {                return false;            }        }        return true;    }     private static void validate(String db) {        int le = db.length();        int[] found = new int[10_000];        Arrays.fill(found, 0);        List<String> errs = new ArrayList<>();         // Check all strings of 4 consecutive digits within 'db'        // to see if all 10,000 combinations occur without duplication.        for (int i = 0; i < le - 3; ++i) {            String s = db.substring(i, i + 4);            if (allDigits(s)) {                int n = Integer.parseInt(s);                found[n]++;            }        }         for (int i = 0; i < 10_000; ++i) {            if (found[i] == 0) {                errs.add(String.format("    PIN number %d is missing", i));            } else if (found[i] > 1) {                errs.add(String.format("    PIN number %d occurs %d times", i, found[i]));            }        }         if (errs.isEmpty()) {            System.out.println("    No errors found");        } else {            String pl = (errs.size() == 1) ? "" : "s";            System.out.printf("  %d error%s found:\n", errs.size(), pl);            errs.forEach(System.out::println);        }    }     public static void main(String[] args) {        String db = deBruijn(10, 4);         System.out.printf("The length of the de Bruijn sequence is %d\n\n", db.length());        System.out.printf("The first 130 digits of the de Bruijn sequence are: %s\n\n", db.substring(0, 130));        System.out.printf("The last 130 digits of the de Bruijn sequence are: %s\n\n", db.substring(db.length() - 130));         System.out.println("Validating the de Bruijn sequence:");        validate(db);         StringBuilder sb = new StringBuilder(db);        String rdb = sb.reverse().toString();        System.out.println();        System.out.println("Validating the de Bruijn sequence:");        validate(rdb);         sb = new StringBuilder(db);        sb.setCharAt(4443, '.');        System.out.println();        System.out.println("Validating the overlaid de Bruijn sequence:");        validate(sb.toString());    }}`
Output:
```The length of the de Bruijn sequence is 10003

The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

The last 130 digits of the de Bruijn sequence are: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Validating the de Bruijn sequence:
No errors found

Validating the de Bruijn sequence:
No errors found

Validating the overlaid de Bruijn sequence:
4 errors found:
PIN number 1459 is missing
PIN number 4591 is missing
PIN number 5814 is missing
PIN number 8145 is missing```

Julia

`function debruijn(k::Integer, n::Integer)    alphabet = b"0123456789abcdefghijklmnopqrstuvwxyz"[1:k]    a = zeros(UInt8, k * n)    seq = UInt8[]     function db(t, p)        if t > n            if n % p == 0                append!(seq, a[2:p+1])            end        else            a[t + 1] = a[t - p + 1]            db(t + 1, p)            for j in a[t-p+1]+1:k-1                a[t + 1] = j                db(t + 1, t)            end        end    end     db(1, 1)    return String([alphabet[i + 1] for i in vcat(seq, seq[1:n-1])])end function verifyallPIN(str, k, n, deltaposition=0)    if deltaposition != 0        str = str[1:deltaposition-1] * "." * str[deltaposition+1:end]    end    result = true    for i in 1:k^n-1        pin = string(i, pad=n)        if !occursin(pin, str)            println("PIN \$pin does not occur in the sequence.")            result = false        end    end    println("The sequence does ", result ? "" : "not ", "contain all PINs.")end const s = debruijn(10, 4)println("The length of the sequence is \$(length(s)). The first 130 digits are:\n",    s[1:130], "\nand the last 130 digits are:\n", s[end-130:end])print("Testing sequence: "), verifyallPIN(s, 10, 4)print("Testing the reversed sequence: "), verifyallPIN(reverse(s), 10, 4)println("\nAfter replacing 4444th digit with \'.\':"), verifyallPIN(s, 10, 4, 4444) `
Output:
```The length of the sequence is 10003. The first 130 digits are:
0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350
and the last 130 digits are:
76898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000
Testing sequence: The sequence does contain all PINs.
Testing the reversed sequence: The sequence does contain all PINs.

After replacing 4444th digit with '.':
PIN 1459 does not occur in the sequence.
PIN 4591 does not occur in the sequence.
PIN 5814 does not occur in the sequence.
PIN 8145 does not occur in the sequence.
The sequence does not contain all PINs.
```

Kotlin

Translation of: Go
`const val digits = "0123456789" fun deBruijn(k: Int, n: Int): String {    val alphabet = digits.substring(0, k)    val a = ByteArray(k * n)    val seq = mutableListOf<Byte>()    fun db(t: Int, p: Int) {        if (t > n) {            if (n % p == 0) {                seq.addAll(a.sliceArray(1..p).asList())            }        } else {            a[t] = a[t - p]            db(t + 1, p)            var j = a[t - p] + 1            while (j < k) {                a[t] = j.toByte()                db(t + 1, t)                j++            }        }    }    db(1, 1)    val buf = StringBuilder()    for (i in seq) {        buf.append(alphabet[i.toInt()])    }    val b = buf.toString()    return b + b.subSequence(0, n - 1)} fun allDigits(s: String): Boolean {    for (c in s) {        if (c < '0' || '9' < c) {            return false        }    }    return true} fun validate(db: String) {    val le = db.length    val found = MutableList(10_000) { 0 }    val errs = mutableListOf<String>()    // Check all strings of 4 consecutive digits within 'db'    // to see if all 10,000 combinations occur without duplication.    for (i in 0 until le - 3) {        val s = db.substring(i, i + 4)        if (allDigits(s)) {            val n = s.toInt()            found[n]++        }    }    for (i in 0 until 10_000) {        if (found[i] == 0) {            errs.add("    PIN number %04d missing".format(i))        } else if (found[i] > 1) {            errs.add("    PIN number %04d occurs %d times".format(i, found[i]))        }    }    val lerr = errs.size    if (lerr == 0) {        println("  No errors found")    } else {        val pl = if (lerr == 1) {            ""        } else {            "s"        }        println("  \$lerr error\$pl found:")        println(errs.joinToString("\n"))    }} fun main() {    var db = deBruijn(10, 4)    val le = db.length     println("The length of the de Bruijn sequence is \$le")    println("\nThe first 130 digits of the de Bruijn sequence are: \${db.subSequence(0, 130)}")    println("\nThe last 130 digits of the de Bruijn sequence are: \${db.subSequence(le - 130, le)}")     println("\nValidating the deBruijn sequence:")    validate(db)     println("\nValidating the reversed deBruijn sequence:")    validate(db.reversed())     val bytes = db.toCharArray()    bytes[4443] = '.'    db = String(bytes)    println("\nValidating the overlaid deBruijn sequence:")    validate(db)}`
Output:
```The length of the de Bruijn sequence is 10003

The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

The last 130 digits of the de Bruijn sequence are: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Validating the deBruijn sequence:
No errors found

Validating the reversed deBruijn sequence:
No errors found

Validating the overlaid deBruijn sequence:
4 errors found:
PIN number 1459 missing
PIN number 4591 missing
PIN number 5814 missing
PIN number 8145 missing```

Lua

Translation of: C++
`function tprint(tbl)    for i,v in pairs(tbl) do        print(v)    endend function deBruijn(k, n)    local a = {}    for i=1, k*n do        table.insert(a, 0)    end     local seq = {}    function db(t, p)        if t > n then            if n % p == 0 then                for i=1, p do                    table.insert(seq, a[i + 1])                end            end        else            a[t + 1] = a[t - p + 1]            db(t + 1, p)             local j = a[t - p + 1] + 1            while j < k do                a[t + 1] = j % 256                db(t + 1, t)                j = j + 1            end        end    end     db(1, 1)     local buf = ""    for i,v in pairs(seq) do        buf = buf .. tostring(v)    end    return buf .. buf:sub(1, n - 1)end function allDigits(s)    return s:match('[0-9]+') == send 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)    endend function main()    local db = deBruijn(10,4)     print("The length of the de Bruijn sequence is " .. string.len(db))    print()     io.write("The first 130 digits of the de Bruijn sequence are: ")    print(db:sub(0, 130))    print()     io.write("The last 130 digits of the de Bruijn sequence are: ")    print(db:sub(-130))    print()     print("Validating the de Bruijn sequence:")    validate(db)    print()     print("Validating the reversed de Bruijn sequence:")    validate(db:reverse())    print()     db = db:sub(1,4443) .. "." .. db:sub(4445)    print("Validating the overlaid de Bruijn sequence:")    validate(db)    print()end main()`
Output:
```The length of the de Bruijn sequence is 10003

The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

The last 130 digits of the de Bruijn sequence are: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Validating the de Bruijn sequence:
No errors found

Validating the reversed de Bruijn sequence:
No errors found

Validating the overlaid de Bruijn sequence:
PIN number 1459 missing
PIN number 4591 missing
PIN number 5814 missing
PIN number 8145 missing```

Mathematica/Wolfram Language

`seq = DeBruijnSequence[Range[0, 9], 4];seq = seq~Join~Take[seq, 3];Length[seq]{seq[[;; 130]], seq[[-130 ;;]]}Complement[ StringDrop[ToString[NumberForm[#, 4, NumberPadding -> {"0", "0"}]],     1] & /@ Range[0, 9999],  Union[StringJoin /@ Partition[ToString /@ seq, 4, 1]]]seq = Reverse[seq];Complement[ StringDrop[ToString[NumberForm[#, 4, NumberPadding -> {"0", "0"}]],     1] & /@ Range[0, 9999],  Union[StringJoin /@ Partition[ToString /@ seq, 4, 1]]]seq[[4444]] = ".";Complement[ StringDrop[ToString[NumberForm[#, 4, NumberPadding -> {"0", "0"}]],     1] & /@ Range[0, 9999],  Union[StringJoin /@ Partition[ToString /@ seq, 4, 1]]]`
Output:
```10003
{{0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 4, 0, 0, 0, 5, 0, 0,
0, 6, 0, 0, 0, 7, 0, 0, 0, 8, 0, 0, 0, 9, 0, 0, 1, 1, 0, 0, 1, 2,
0, 0, 1, 3, 0, 0, 1, 4, 0, 0, 1, 5, 0, 0, 1, 6, 0, 0, 1, 7, 0, 0, 1,
8, 0, 0, 1, 9, 0, 0, 2, 1, 0, 0, 2, 2, 0, 0, 2, 3, 0, 0, 2, 4, 0,
0, 2, 5, 0, 0, 2, 6, 0, 0, 2, 7, 0, 0, 2, 8, 0, 0, 2, 9, 0, 0, 3, 1,
0, 0, 3, 2, 0, 0, 3, 3, 0, 0, 3, 4, 0, 0, 3, 5, 0}, {6, 8, 9, 8, 6,
8, 9, 9, 6, 9, 6, 9, 7, 7, 6, 9, 7, 8, 6, 9, 7, 9, 6, 9, 8, 7, 6,
9, 8, 8, 6, 9, 8, 9, 6, 9, 9, 7, 6, 9, 9, 8, 6, 9, 9, 9, 7, 7, 7, 7,
8, 7, 7, 7, 9, 7, 7, 8, 8, 7, 7, 8, 9, 7, 7, 9, 8, 7, 7, 9, 9, 7,
8, 7, 8, 7, 9, 7, 8, 8, 8, 7, 8, 8, 9, 7, 8, 9, 8, 7, 8, 9, 9, 7, 9,
7, 9, 8, 8, 7, 9, 8, 9, 7, 9, 9, 8, 7, 9, 9, 9, 8, 8, 8, 8, 9, 8,
8, 9, 9, 8, 9, 8, 9, 9, 9, 9, 0, 0, 0}}
{}
{}
{"1478", "4781", "7813", "8137"}```

Nim

Translation of: D
`import algorithm, parseutils, strformat, strutils const Digits = "0123456789" #--------------------------------------------------------------------------------------------------- func deBruijn(k, n: int): string =  let alphabet = Digits[0..<k]  var a = newSeq[byte](k * n)  var sequence: seq[byte]   #.................................................................................................   func db(t, p: int) =    if t > n:      if n mod p == 0:        sequence &= a[1..p]    else:      a[t] = a[t - p]      db(t + 1, p)      var j = a[t - p] + 1      while j < k.uint:        a[t] = j        db(t + 1, t)        inc j     #...............................................................................................   db(1, 1)  for i in sequence:    result &= alphabet[i]  result &= result[0..(n-2)] #--------------------------------------------------------------------------------------------------- proc validate(db: string) =   var found: array[10_000, int]  var errs: seq[string]   ## Check all strings of 4 consecutive digits within 'db'  ## to see if all 10,000 combinations occur without duplication.  for i in 0..(db.len - 4):    let s = db[i..(i+3)]    var n: int    if s.parseInt(n) == 4:      inc found[n]   for n, count in found:    if count == 0:      errs &= fmt"    PIN number {n:04d} missing"    elif count > 1:      errs &= fmt"    PIN number {n:04d} occurs {count} times"   if errs.len == 0:    echo "  No errors found"  else:    let plural = if errs.len == 1: "" else: "s"    echo fmt"  {errs.len} error{plural} found"    for err in errs: echo err #——————————————————————————————————————————————————————————————————————————————————————————————————— var db = deBruijn(10, 4) echo fmt"The length of the de Bruijn sequence is {db.len}"echo ""echo fmt"The first 130 digits of the de Bruijn sequence are: {db[0..129]}"echo ""echo fmt"The last 130 digits of the de Bruijn sequence are: {db[^130..^1]}"echo "" echo "Validating the deBruijn sequence:"db.validate()echo ""echo "Validating the reversed deBruijn sequence:"reversed(db).join().validate()echo "" db[4443] = '.'echo "Validating the overlaid deBruijn sequence:"db.validate()`
Output:
```The length of the de Bruijn sequence is 10003

The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

The last 130 digits of the de Bruijn sequence are: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Validating the deBruijn sequence:
No errors found

Validating the reversed deBruijn sequence:
No errors found

Validating the overlaid deBruijn sequence:
4 errors found
PIN number 1459 missing
PIN number 4591 missing
PIN number 5814 missing
PIN number 8145 missing```

Pascal

A console application in Free Pascal, created with the Lazarus IDE.

For a given word length n, constructs a de Bruijn sequence by concatenating, in lexicographic order, all the Lyndon words whose length divides n. (See Wikipedia article "de Bruijn sequence", section "Construction".)

` program deBruijnSequence;uses SysUtils; // Create a de Bruijn sequence for the given word length and alphabet.function deBruijn( const n : integer; // word length                   const alphabet : string) : string;var  d, k, m, s, t, seqLen : integer;  w : array of integer;begin  k := Length( alphabet);  // de Bruijn sequence will have length k^n  seqLen := 1;  for t := 1 to n do seqLen := seqLen*k;  SetLength( result, seqLen);  d := 0; // index into de Bruijn sequence (will be pre-inc'd)  // Work through Lyndon words of length <= n, in lexicographic order.  SetLength( w, n); // w holds array of indices into the alphabet  w[0] := 1; // first Lyndon word  m := 1; // m = length of Lyndon word  repeat    // If m divides n, append the current Lyndon word to the output    if (m = n) or (m = 1) or (n mod m = 0) then begin      for t := 0 to m - 1 do begin        inc(d);        result[d] := alphabet[w[t]];      end;    end;    // Get next Lyndon word using Duval's algorithm:    // (1) Fill w with repetitions of current word    s := 0; t := m;    while (t < n) do begin      w[t] := w[s];      inc(t);  inc(s);      if s = m then s := 0;    end;    // (2) Repeatedly delete highest index k from end of w, if present    m := n;    while (m > 0) and (w[m - 1] = k) do dec(m);    // (3) If word is now null, stop; else increment end value    if m > 0 then inc( w[m - 1]);  until m = 0;  Assert( d = seqLen); // check that the sequence is exactly filled inend; // Check a de Bruijn sequence, assuming that its alphabet consists//  of the digits '0'..'9' (in any order);procedure CheckDecimal( const n : integer; // word length                        const deB : string);var  count : array of integer;  j, L, pin, nrErrors : integer;  wrap : string;begin  L := Length( deB);  // The de Bruijn sequence is cyclic; make an array to handle wrapround.  SetLength( wrap, 2*n - 2);  for j := 1 to n - 1 do wrap[j] := deB[L + j - n  + 1];  for j := n to 2*n - 2 do wrap[j] := deB[j - n + 1];  // Count occurrences of each PIN.  // PIN = -1 if character is not a decimal digit.  SetLength( count, L);  for j := 0 to L - 1 do count[L] := 0;  for j := 1 to L - n + 1 do begin    pin := SysUtils.StrToIntDef( Copy( deB, j, n), -1);    if pin >= 0 then inc( count[pin]);  end;  for j := 1 to n - 1 do begin    pin := SysUtils.StrToIntDef( Copy( wrap, j, n), -1);    if pin >= 0 then inc( count[pin]);  end;  // Check that all counts are 1  nrErrors := 0;  for j := 0 to L - 1 do begin    if count[j] <> 1 then begin      inc( nrErrors);      WriteLn( SysUtils.Format( '  PIN %d has count %d', [j, count[j]]));    end;  end;  WriteLn( SysUtils.Format( '  Number of errors = %d', [nrErrors])); end; // Main routinevar  deB, rev : string;  L, j : integer;begin   deB := deBruijn( 4, '0123456789');//   deB := deBruijn( 4, '7368290514'); // any permutation would do   L := Length( deB);   WriteLn( SysUtils.Format( 'Length of de Bruijn sequence = %d', [L]));   if L >= 260 then begin     WriteLn;     WriteLn( 'First and last 130 characters are:');     WriteLn( Copy( deB, 1, 65));     WriteLn( Copy( deb, 66, 65));     WriteLn( '...');     WriteLn( Copy( deB, L - 129, 65));     WriteLn( Copy( deB, L - 64, 65));   end;   WriteLn;   WriteLn( 'Checking de Bruijn sequence:');   CheckDecimal( 4, deB);   // Check reversed sequence   SetLength( rev, L);   for j := 1 to L do rev[j] := deB[L + 1 - j];   WriteLn( 'Checking reversed sequence:');   CheckDecimal( 4, rev);   // Check sequence with '.' instad of decimal digit   if L >= 4444 then begin     deB[4444] := '.';     WriteLn( 'Checking vandalized sequence:');     CheckDecimal( 4, deB);   end;end. `
Output:
```Length of de Bruijn sequence = 10000

First and last 130 characters are:
00001000200030004000500060007000800090011001200130014001500160017
00180019002100220023002400250026002700280029003100320033003400350
...
89768986899696977697869796987698869896997699869997777877797788778
97798779978787978887889789878997979887989799879998888988998989999

Checking de Bruijn sequence:
Number of errors = 0
Checking reversed sequence:
Number of errors = 0
Checking vandalized sequence:
PIN 1459 has count 0
PIN 4591 has count 0
PIN 5814 has count 0
PIN 8145 has count 0
Number of errors = 4
```

Perl

Translation of: Raku
`use strict;use warnings;use feature 'say'; my \$seq;for my \$x (0..99) {    my \$a = sprintf '%02d', \$x;    next if substr(\$a,1,1) < substr(\$a,0,1);    \$seq .= (substr(\$a,0,1) == substr(\$a,1,1)) ? substr(\$a,0,1) : \$a;    for (\$a+1 .. 99) {        next if substr(sprintf('%02d', \$_), 1,1) <= substr(\$a,0,1);        \$seq .= sprintf "%s%02d", \$a, \$_;    }}\$seq .= '000'; sub check {    my(\$seq) = @_;    my %chk;    for (0.. -1 + length \$seq) { \$chk{substr(\$seq, \$_, 4)}++ }    say 'Missing: ' . join ' ', grep { ! \$chk{ sprintf('%04d',\$_) } } 0..9999;    say 'Extra:   ' . join ' ', sort grep { \$chk{\$_} > 1 } keys %chk;} my \$n = 130;say "de Bruijn sequence length: " . length \$seq;say "\nFirst \$n characters:\n" . substr(\$seq, 0, \$n );say "\nLast \$n characters:\n"  . substr(\$seq, -\$n, \$n);say "\nIncorrect 4 digit PINs in this sequence:";check \$seq; say "\nIncorrect 4 digit PINs in the reversed sequence:";check(reverse \$seq); say "\nReplacing the 4444th digit, '@{[substr(\$seq,4443,1)]}', with '5'";substr \$seq, 4443, 1, 5;say "Incorrect 4 digit PINs in the revised sequence:";check \$seq;`
Output:
```de Bruijn sequence length: 10003

First 130 characters:
0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

Last 130 characters:
6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

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

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

Replacing the 4444th digit, '4', with '5'
Incorrect 4 digit PINs in the revised sequence:
Missing: 1459 4591 5814 8145
Extra:   1559 5591 5815 8155```

Phix

Translation of: zkl
Translation of: Go
```string deBruijn = ""
for n=0 to 99 do
string a = sprintf("%02d",n)
integer a1 = a[1],
a2 = a[2]
if a2>=a1 then
deBruijn &= iff(a1=a2?a1:a)
for m=n+1 to 99 do
string ms = sprintf("%02d",m)
if ms[2]>a1 then
deBruijn &= a&ms
end if
end for
end if
end for
deBruijn &= "000"
printf(1,"de Bruijn sequence length: %d\n\n",length(deBruijn))
printf(1,"First 130 characters:\n%s\n\n",deBruijn[1..130])
printf(1,"Last 130 characters:\n%s\n\n",deBruijn[-130..-1])

function check(string text)
sequence res = {}
sequence found = repeat(0,10000)
integer k
for i=1 to length(text)-3 do
k = to_integer(text[i..i+3],-1)+1
if k!=0 then found[k] += 1 end if
end for
for i=1 to 10000 do
k = found[i]
if k!=1 then
string e = sprintf("Pin number %04d ",i-1)
e &= iff(k=0?"missing":sprintf("occurs %d times",k))
res = append(res,e)
end if
end for
k = length(res)
if k=0 then
res = "No errors found"
else
string s = iff(k=1?"":"s")
res = sprintf("%d error%s found:\n ",{k,s})&join(res,"\n ")
end if
return res
end function

printf(1,"Missing 4 digit PINs in this sequence: %s\n", check(deBruijn))
printf(1,"Missing 4 digit PINs in the reversed sequence: %s\n",check(reverse(deBruijn)))
printf(1,"4444th digit in the sequence: %c (setting it to .)\n", deBruijn[4444])
deBruijn[4444] = '.'
printf(1,"Re-running checks: %s\n",check(deBruijn))
```
Output:
```de Bruijn sequence length: 10003

First 130 characters:
0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

Last 130 characters:
6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Missing 4 digit PINs in this sequence: No errors found
Missing 4 digit PINs in the reversed sequence: No errors found
4444th digit in the sequence: 4 (setting it to .)
Re-running checks: 4 errors found:
Pin number 1459 missing
Pin number 4591 missing
Pin number 5814 missing
Pin number 8145 missing
```

Python

` # from https://en.wikipedia.org/wiki/De_Bruijn_sequence def de_bruijn(k, n):    """    de Bruijn sequence for alphabet k    and subsequences of length n.    """    try:        # let's see if k can be cast to an integer;        # if so, make our alphabet a list        _ = int(k)        alphabet = list(map(str, range(k)))     except (ValueError, TypeError):        alphabet = k        k = len(k)     a = [0] * k * n    sequence = []     def db(t, p):        if t > n:            if n % p == 0:                sequence.extend(a[1:p + 1])        else:            a[t] = a[t - p]            db(t + 1, p)            for j in range(a[t - p] + 1, k):                a[t] = j                db(t + 1, t)    db(1, 1)    return "".join(alphabet[i] for i in sequence) def validate(db):    """     Check that all 10,000 combinations of 0-9 are present in     De Bruijn string db.     Validating the reversed deBruijn sequence:      No errors found     Validating the overlaid deBruijn sequence:      4 errors found:        PIN number 1459 missing        PIN number 4591 missing        PIN number 5814 missing        PIN number 8145 missing     """     dbwithwrap = db+db[0:3]     digits = '0123456789'     errorstrings = []     for d1 in digits:        for d2 in digits:            for d3 in digits:                for d4 in digits:                    teststring = d1+d2+d3+d4                    if teststring not in dbwithwrap:                        errorstrings.append(teststring)     if len(errorstrings) > 0:        print("  "+str(len(errorstrings))+" errors found:")        for e in errorstrings:            print("  PIN number "+e+"  missing")    else:        print("  No errors found") db = de_bruijn(10, 4) print(" ")print("The length of the de Bruijn sequence is ", str(len(db)))print(" ")print("The first 130 digits of the de Bruijn sequence are: "+db[0:130])print(" ")print("The last 130 digits of the de Bruijn sequence are: "+db[-130:])print(" ")print("Validating the deBruijn sequence:")validate(db)dbreversed = db[::-1]print(" ")print("Validating the reversed deBruijn sequence:")validate(dbreversed)dboverlaid = db[0:4443]+'.'+db[4444:]print(" ")print("Validating the overlaid deBruijn sequence:")validate(dboverlaid) `
Output:
```The length of the de Bruijn sequence is  10000

The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

The last 130 digits of the de Bruijn sequence are: 8976898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999

Validating the deBruijn sequence:
No errors found

Validating the reversed deBruijn sequence:
No errors found

Validating the overlaid deBruijn sequence:
4 errors found:
PIN number 1459  missing
PIN number 4591  missing
PIN number 5814  missing
PIN number 8145  missing
```

Racket

Translation of: Go
`#lang racket (define (de-bruijn k n)  (define a (make-vector (* k n) 0))  (define seq '())  (define (db t p)    (cond      [(> t n) (when (= (modulo n p) 0)                 (set! seq (cons (call-with-values                                  (thunk (vector->values a 1 (add1 p)))                                  list)                                 seq)))]      [else (vector-set! a t (vector-ref a (- t p)))            (db (add1 t) p)            (for ([j (in-range (add1 (vector-ref a (- t p))) k)])              (vector-set! a t j)              (db (add1 t) t))]))  (db 1 1)  (define seq* (append* (reverse seq)))  (append seq* (take seq* (sub1 n)))) (define seq (de-bruijn 10 4))(printf "The length of the de Bruijn sequence is ~a\n\n" (length seq))(printf "The first 130 digits of the de Bruijn sequence are:\n~a\n\n"        (take seq 130))(printf "The last 130 digits of the de Bruijn sequence are:\n~a\n\n"        (take-right seq 130)) (define (validate name seq)  (printf "Validating the ~ade Bruijn sequence:\n" name)  (define expected (for/set ([i (in-range 0 10000)]) i))  (define actual (for/set ([a (in-list seq)]                           [b (in-list (rest seq))]                           [c (in-list (rest (rest seq)))]                           [d (in-list (rest (rest (rest seq))))])                   (+ (* 1000 a) (* 100 b) (* 10 c) d)))  (define diff (set-subtract expected actual))  (cond    [(set-empty? diff) (printf "  No errors found\n")]    [else (for ([n (in-set diff)])            (printf "  ~a is missing\n" (~a n #:width 4 #:pad-string "0")))])  (newline)) (validate "" seq)(validate "reversed " (reverse seq))(validate "overlaid " (list-update seq 4443 add1))`
Output:
```The length of the de Bruijn sequence is 10003

The first 130 digits of the de Bruijn sequence are:
(0 0 0 0 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5 0 0 0 6 0 0 0 7 0 0 0 8 0 0 0 9 0 0 1 1 0 0 1 2 0 0 1 3 0 0 1 4 0 0 1 5 0 0 1 6 0 0 1 7 0 0 1 8 0 0 1 9 0 0 2 1 0 0 2 2 0 0 2 3 0 0 2 4 0 0 2 5 0 0 2 6 0 0 2 7 0 0 2 8 0 0 2 9 0 0 3 1 0 0 3 2 0 0 3 3 0 0 3 4 0 0 3 5 0)

The last 130 digits of the de Bruijn sequence are:
(6 8 9 8 6 8 9 9 6 9 6 9 7 7 6 9 7 8 6 9 7 9 6 9 8 7 6 9 8 8 6 9 8 9 6 9 9 7 6 9 9 8 6 9 9 9 7 7 7 7 8 7 7 7 9 7 7 8 8 7 7 8 9 7 7 9 8 7 7 9 9 7 8 7 8 7 9 7 8 8 8 7 8 8 9 7 8 9 8 7 8 9 9 7 9 7 9 8 8 7 9 8 9 7 9 9 8 7 9 9 9 8 8 8 8 9 8 8 9 9 8 9 8 9 9 9 9 0 0 0)

Validating the de Bruijn sequence:
No errors found

Validating the reversed de Bruijn sequence:
No errors found

Validating the overlaid de Bruijn sequence:
1459 is missing
4591 is missing
8145 is missing
5814 is missing
```

Raku

(formerly Perl 6)

Works with: Rakudo version 2019.07.1

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

`# Generate the sequencemy \$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 Taskput "de Bruijn sequence length: " ~ \$seq.chars; put "\nFirst 130 characters:\n" ~ \$seq.substr( 0, 130 ); put "\nLast 130 characters:\n" ~ \$seq.substr( * - 130 ); put "\nIncorrect 4 digit PINs in this sequence:";check \$seq; put "\nIncorrect 4 digit PINs in the reversed sequence:";check \$seq.flip; my \$digit = \$seq.substr(4443,1);put "\nReplacing the 4444th digit, (\$digit) with { (\$digit += 1) %= 10 }";put "Incorrect 4 digit PINs in the revised sequence:";\$seq.substr-rw(4443,1) = \$digit;check \$seq;`
Sample output:
```de Bruijn sequence length: 10003

First 130 characters:
4558455945654566456745684569457545764577457845794585458645874588458945954596459745984599464647464846494655465646574658465946654666

Last 130 characters:
5445644574458445944654466446744684469447544764477447844794485448644874488448944954496449744984499454546454745484549455545564557455

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

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

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

REXX

The   de Bruijn   sequence generated by these REXX programs are identical to the sequence shown on the   discussion   page   (1st topic).

hard-coded node to be removed

`/*REXX pgm calculates the  de Bruijn  sequence for all pin numbers  (4 digit decimals). */\$=                                               /*initialize the  de Bruijn  sequence. */#=10;   lastNode= (#-2)(#-2)(#-1)(#-2)           /*this number is formed when this # ···*/                                                 /*  ··· is skipped near the cycle end. */  do j=0  for 10;  \$= \$ || j;  jj= j || j        /*compose the left half of the numbers.*/                                                 /* [↓]     "  right  "   "  "     "    */                                do k=jj+1  to 99;      z= jj || right(k, 2, 0)                                if z==lastNode  then iterate    /*the last node skipped.*/                                if pos(z, \$)\==0  then iterate  /*# in sequence? Skip it*/                                \$= \$ || z        /* ◄─────────────────────────────────┐ */                                end   /*k*/      /*append a number to the sequence──◄─┘ */      do r= jj  to (j || 9);  b= right(r, 2, 0)   /*compose the left half of the numbers.*/     if b==jj  then iterate     \$= \$ || right(b, 2, 0)                      /* [↓]     "  right  "   "  "     "    */                                do k= b+1  to 99;      z= right(b, 2, 0) || right(k, 2, 0)                                if pos(z, \$)\==0  then iterate  /*# in sequence? Skip it*/                                \$= \$ || z        /* ◄─────────────────────────────────┐ */                                end   /*k*/      /*append a number to the sequence──◄─┘ */     end   /*r*/  end      /*j*/                      @deB= 'de Bruijn sequence' /*literal used in some SAY instructions*/\$= \$ || left(\$, 3)        /*append 000*/         /*simulate "wrap-around" de Bruijn seq.*/       say 'length of the' @deB " is " length(\$) /*display the length of  de Bruijn seq.*/say;   say 'first 130 digits of the' @deB":"     /*display the title for the next line. */       say left(\$, 130)                          /*display 130 left-most digits of seq. */say;   say ' last 130 digits of the' @deB":"     /*display the title for the next line. */       say right(\$, 130)                         /*display 130 right-most digits of seq.*/say                                              /*display a blank line.                */call val \$                                       /*call the  VAL  sub for verification. */               @deB= 'reversed'   @deB           /*next,  we'll check on a reversed seq.*/\$\$= reverse(\$)                                   /*do what a mirror does,  reversify it.*/call val \$\$                                      /*call the  VAL  sub for verification. */\$= overlay(., \$, 4444)                           /*replace 4,444th digit with a period. */               @deB= 'overlaid' subword(@deB, 2) /* [↑] this'll cause a validation barf.*/call val \$                                       /*call the  VAL  sub for verification. */exit                                             /*stick a fork in it,  we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/val: parse arg \$\$\$;    e= 0;    _= copies('─',8) /*count of errors (missing PINs) so far*/     say;      say _ 'validating the'    @deB"." /*display what's happening in the pgm. */         do pin=0  for 1e4; pin4= right(pin,4,0) /* [↓]  maybe add leading zeros to pin.*/         if pos(pin4, \$\$\$)\==0  then iterate     /*Was number found?  Just as expected. */         say 'PIN number '      pin       " wasn't found in"         @deb'.'         e= e + 1                                /*bump the counter for number of errors*/         end   /*pin*/                           /* [↑]  validate all 10,000 pin numbers*/     if e==0  then e= 'No'                       /*Gooder English (sic) the error count.*/     say _   e   'errors found.'                 /*display the number of errors found.  */     return`
output:
```length of the de Bruijn sequence  is  10003

first 130 digits of the de Bruijn sequence:
0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

last 130 digits of the de Bruijn sequence:
6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

──────── validating the de Bruijn sequence.
──────── No errors found.

──────── validating the reversed de Bruijn sequence.
──────── No errors found.

──────── validating the overlaid de Bruijn sequence.
PIN number  1459  wasn't found in overlaid de Bruijn sequence.
PIN number  4591  wasn't found in overlaid de Bruijn sequence.
PIN number  5814  wasn't found in overlaid de Bruijn sequence.
PIN number  8145  wasn't found in overlaid de Bruijn sequence.
──────── 4 errors found.
```

programmatically removing of a node

Programming note:   instead of hardcoding the   lastNode   (that is elided from the sequence),   the 5th to the last node could simply be deleted.

This method slightly bloats the program and slows execution.

`/*REXX pgm calculates the  de Bruijn  sequence for all pin numbers  (4 digit decimals). */\$=                                               /*initialize the  de Bruijn  sequence. */   do j=0  for 10;  \$= \$ j;   jj= j || j          /*compose the left half of the numbers.*/  \$\$= space(\$, 0)                                /* [↓]     "  right  "   "  "     "    */                                do k=jj+1  to 99;      z= jj || right(k, 2, 0)                                if pos(z, \$\$)\==0  then iterate /*# in sequence? Skip it*/                                \$= \$ z           /* ◄─────────────────────────────────┐ */                                end   /*k*/      /*append a number to the sequence──◄─┘ */  \$\$= space(\$, 0)     do r= jj  to (j || 9);  b= right(r, 2, 0)   /*compose the left half of the numbers.*/     if b==jj  then iterate     \$= \$ right(b, 2, 0)                         /* [↓]     "  right  "   "  "     "    */     \$\$= space(\$, 0);           do k= b+1  to 99;      z= right(b, 2, 0) || right(k, 2, 0)                                if pos(z, \$\$)\==0  then iterate /*# in sequence? Skip it*/                                \$= \$ z           /* ◄─────────────────────────────────┐ */                                end   /*k*/      /*append a number to the sequence──◄─┘ */     \$\$= space(\$, 0)     end   /*r*/  end      /*j*/ \$= delword(\$, words(\$)-4, 1)                     /*delete 5th from the last word in \$.  */\$= space(\$, 0)                      @deB= 'de Bruijn sequence' /*literal used in some SAY instructions*/\$= \$ || left(\$, 3)        /*append 000*/         /*simulate "wrap-around" de Bruijn seq.*/       say 'length of the' @deB " is " length(\$) /*display the length of  de Bruijn seq.*/say;   say 'first 130 digits of the' @deB":"     /*display the title for the next line. */       say left(\$, 130)                          /*display 130 left-most digits of seq. */say;   say ' last 130 digits of the' @deB":"     /*display the title for the next line. */       say right(\$, 130)                         /*display 130 right-most digits of seq.*/call val \$                                       /*call the  VAL  sub for verification. */               @deB= 'reversed'   @deB           /*next,  we'll check on a reversed seq.*/\$r= reverse(\$)                                   /*do what a mirror does,  reversify it.*/call val \$r                                      /*call the  VAL  sub for verification. */\$= overlay(., \$, 4444)                           /*replace 4,444th digit with a period. */               @deB= 'overlaid' subword(@deB, 2) /* [↑] this'll cause a validation barf.*/call val \$                                       /*call the  VAL  sub for verification. */exit                                             /*stick a fork in it,  we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/val: parse arg \$\$\$;    e= 0;    _= copies('─',8) /*count of errors (missing PINs) so far*/     say;      say _ 'validating the'    @deB"." /*display what's happening in the pgm. */         do pin=0  for 1e4; pin4= right(pin,4,0) /* [↓]  maybe add leading zeros to pin.*/         if pos(pin4, \$\$\$)\==0  then iterate     /*Was number found?  Just as expected. */         say 'PIN number '      pin       " wasn't found in"         @deb'.'         e= e + 1                                /*bump the counter for number of errors*/         end   /*pin*/                           /* [↑]  validate all 10,000 pin numbers*/     if e==0  then e= 'No'                       /*Gooder English (sic) the error count.*/     say _   e   'errors found.'                 /*display the number of errors found.  */     return`
output   is identical to the 1st REXX version.

Ruby

Translation of: D
`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    endend db = deBruijn(10, 4)print "The length of the de Bruijn sequence is ", db.length, "\n\n"print "The first 130 digits of the de Bruijn sequence are: ", db[0 .. 129], "\n\n"print "The last 130 digits of the de Bruijn sequence are: ", db[-130 .. db.length], "\n\n" print "Validating the de Bruijn sequence:\n"validate(db)print "\n" db[4443] = '.'print "Validating the overlaid de Bruijn sequence:\n"validate(db)`
Output:
```The length of the de Bruijn sequence is 10003

The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

The last 130 digits of the de Bruijn sequence are: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Validating the de Bruijn sequence:
No errors found

Validating the overlaid de Bruijn sequence:
4 errors found:
PIN number 1459 missing
PIN number 4591 missing
PIN number 5814 missing
PIN number 8145 missing```

Visual Basic .NET

Translation of: C#
`Imports System.Text Module Module1     ReadOnly DIGITS As String = "0123456789"     Function DeBruijn(k As Integer, n As Integer) As String        Dim alphabet = DIGITS.Substring(0, k)        Dim a(k * n) As Byte        Dim seq As New List(Of Byte)        Dim db As Action(Of Integer, Integer) = Sub(t As Integer, p As Integer)                                                    If t > n Then                                                        If n Mod p = 0 Then                                                            Dim seg = New ArraySegment(Of Byte)(a, 1, p)                                                            seq.AddRange(seg)                                                        End If                                                    Else                                                        a(t) = a(t - p)                                                        db(t + 1, p)                                                        Dim j = a(t - p) + 1                                                        While j < k                                                            a(t) = j                                                            db(t + 1, t)                                                            j += 1                                                        End While                                                    End If                                                End Sub        db(1, 1)        Dim buf As New StringBuilder        For Each i In seq            buf.Append(alphabet(i))        Next        Dim b = buf.ToString        Return b + b.Substring(0, n - 1)    End Function     Function AllDigits(s As String) As Boolean        For Each c In s            If c < "0" OrElse "9" < c Then                Return False            End If        Next        Return True    End Function     Sub Validate(db As String)        Dim le = db.Length        Dim found(10000) As Integer        Dim errs As New List(Of String)        ' Check all strings of 4 consecutive digits within 'db'        ' to see if all 10,000 combinations occur without duplication.        For i = 1 To le - 3            Dim s = db.Substring(i - 1, 4)            If (AllDigits(s)) Then                Dim n As Integer = Nothing                Integer.TryParse(s, n)                found(n) += 1            End If        Next        For i = 1 To 10000            If found(i - 1) = 0 Then                errs.Add(String.Format("    PIN number {0,4} missing", i - 1))            ElseIf found(i - 1) > 1 Then                errs.Add(String.Format("    PIN number {0,4} occurs {1} times", i - 1, found(i - 1)))            End If        Next        Dim lerr = errs.Count        If lerr = 0 Then            Console.WriteLine("  No errors found")        Else            Dim pl = If(lerr = 1, "", "s")            Console.WriteLine("  {0} error{1} found:", lerr, pl)            errs.ForEach(Sub(x) Console.WriteLine(x))        End If    End Sub     Function Reverse(s As String) As String        Dim arr = s.ToCharArray        Array.Reverse(arr)        Return New String(arr)    End Function     Sub Main()        Dim db = DeBruijn(10, 4)        Dim le = db.Length         Console.WriteLine("The length of the de Bruijn sequence is {0}", le)        Console.WriteLine(vbNewLine + "The first 130 digits of the de Bruijn sequence are: {0}", db.Substring(0, 130))        Console.WriteLine(vbNewLine + "The last 130 digits of the de Bruijn sequence are: {0}", db.Substring(le - 130, 130))         Console.WriteLine(vbNewLine + "Validating the deBruijn sequence:")        Validate(db)         Console.WriteLine(vbNewLine + "Validating the reversed deBruijn sequence:")        Validate(Reverse(db))         Dim bytes = db.ToCharArray        bytes(4443) = "."        db = New String(bytes)        Console.WriteLine(vbNewLine + "Validating the overlaid deBruijn sequence:")        Validate(db)    End Sub End Module`
Output:
```The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

The last 130 digits of the de Bruijn sequence are: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Validating the deBruijn sequence:
No errors found

Validating the reversed deBruijn sequence:
No errors found

Validating the overlaid deBruijn sequence:
4 errors found:
PIN number 1459 missing
PIN number 4591 missing
PIN number 5814 missing
PIN number 8145 missing```

Wren

Translation of: Phix
Library: Wren-fmt
Library: Wren-str
`import "/fmt" for Fmtimport "/str" for Str var deBruijn = ""for (n in 0..99) {    var a = Fmt.rjust(2, n, "0")    var a1 = a[0].bytes[0]    var a2 = a[1].bytes[0]    if (a2 >= a1) {        deBruijn = deBruijn + ((a1 == a2) ? String.fromByte(a1): a)        var m = n + 1        while (m <= 99) {            var ms = Fmt.rjust(2, m, "0")            if (ms[1].bytes[0] > a1) deBruijn = deBruijn + a + ms            m = m + 1        }    }} deBruijn = deBruijn + "000"System.print("de Bruijn sequence length: %(deBruijn.count)\n")System.print("First 130 characters:\n%(deBruijn[0...130])\n")System.print("Last 130 characters:\n%(deBruijn[-130..-1])\n") var check = Fn.new { |text|    var res = []    var found = List.filled(10000, 0)    var k = 0    for (i in 0...(text.count-3)) {        var s = text[i..i+3]        if (Str.allDigits(s)) {            k = Num.fromString(s)            found[k] = found[k] + 1        }    }    for (i in 0...10000) {        k = found[i]        if (k != 1) {            var e = "  Pin number %(Fmt.dz(4, i)) "            e = e + ((k == 0) ? "missing" : "occurs %(k) times")            res.add(e)        }    }    k = res.count    if (k == 0) {        res = "No errors found"    } else {        var s = (k == 1) ? "" : "s"        res = "%(k) error%(s) found:\n" + res.join("\n")    }    return res} System.print("Missing 4 digit PINs in this sequence: %(check.call(deBruijn))")System.print("Missing 4 digit PINs in the reversed sequence: %(check.call(deBruijn[-1..0]))") System.print("\n4,444th digit in the sequence: '%(deBruijn[4443])' (setting it to '.')")deBruijn = deBruijn[0..4442] + "." + deBruijn[4444..-1]System.print("Re-running checks: %(check.call(deBruijn))")`
Output:
```de Bruijn sequence length: 10003

First 130 characters:
0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

Last 130 characters:
6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Missing 4 digit PINs in this sequence: No errors found
Missing 4 digit PINs in the reversed sequence: No errors found

4,444th digit in the sequence: '4' (setting it to '.')
Re-running checks: 4 errors found:
Pin number 1459 missing
Pin number 4591 missing
Pin number 5814 missing
Pin number 8145 missing
```

zkl

Translation of: Raku
`dbSeq:=Data();	// a byte/character bufferforeach n in (100){   a,a01,a11 := "%02d".fmt(n), a[0,1], a[1,1];   if(a11<a01) continue;   dbSeq.append( if(a01==a11) a01 else a );   foreach m in ([n+1 .. 99]){      if("%02d".fmt(m)[1,1] <= a01) continue;      dbSeq.append("%s%02d".fmt(a,m));   }}dbSeq.append("000");`
`seqText:=dbSeq.text;println("de Bruijn sequence length: ",dbSeq.len()); println("\nFirst 130 characters:\n",seqText[0,130]);println("\nLast 130 characters:\n", seqText[-130,*]); fcn chk(seqText){   chk:=Dictionary();   foreach n in ([0..seqText.len()-1]){ chk[seqText[n,4]]=True }   (9999).pump(List,"%04d".fmt,'wrap(k){ if(chk.holds(k)) Void.Skip else k })}println("\nMissing 4 digit PINs in this sequence: ", chk(seqText).concat(" "));print("Missing 4 digit PINs in the reversed sequence: ",chk(seqText.reverse()).concat(" ")); println("\n4444th digit in the sequence: ", seqText[4443]);dbSeq[4443]=".";println("Setting the 4444th digit and reruning checks: ",chk(dbSeq.text).concat(" "));`
Output:
```de Bruijn sequence length: 10003

First 130 characters:
0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

Last 130 characters:
6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Missing 4 digit PINs in this sequence:
Missing 4 digit PINs in the reversed sequence:
4444th digit in the sequence: 4
Setting the 4444th digit and reruning checks: 1459 4591 5814 8145
```