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



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



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

Such a sequence is denoted by    B(k, n)    and has
length   kn,   which is also the number of distinct substrings of
length   n   on   A;    

de Bruijn sequences are therefore optimally short.

There are:

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

distinct de Bruijn sequences    B(k, n). 



Task

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



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



Example

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

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

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



Task requirements

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


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

Show all output here, on this page.


Other tasks related to string operations:

Metrics
 Array length
 String length
 Copy a string
 Empty string  (assignment)
Counting
 Word frequency
 Letter frequency
 Jewels and stones
 I before E except after C
 Bioinformatics/base count
 Count occurrences of a substring
 Count how many vowels and consonants occur in a string
Remove/replace
 XXXX redacted
 Conjugate a Latin verb
 Remove vowels from a string
 String interpolation (included)
 Strip block comments
 Strip comments from a string
 Strip a set of characters from a string
 Strip whitespace from a string -- top and tail
 Strip control codes and extended characters from a string
Anagrams/Derangements/shuffling
 Word wheel
 ABC problem
 Sattolo cycle
 Knuth shuffle
 Ordered words
 Superpermutation minimisation
 Textonyms (using a phone text pad)
 Anagrams
 Anagrams/Deranged anagrams
 Permutations/Derangements
Find/Search/Determine
 ABC words
 Odd words
 Word ladder
 Semordnilap
 Word search
 Wordiff  (game)
 String matching
 Tea cup rim text
 Alternade words
 Changeable words
 State name puzzle
 String comparison
 Unique characters
 Unique characters in each string
 Extract file extension
 Levenshtein distance
 Palindrome detection
 Common list elements
 Longest common suffix
 Longest common prefix
 Compare a list of strings 
 Longest common substring
 Find common directory path
 Words from neighbour ones
 Change e letters to i in words
 Non-continuous subsequences
 Longest common subsequence
 Longest palindromic substrings
 Longest increasing subsequence
 Words containing "the" substring
 Sum of the digits of n is substring of n
 Determine if a string is numeric
 Determine if a string is collapsible
 Determine if a string is squeezable
 Determine if a string has all unique characters
 Determine if a string has all the same characters
 Longest substrings without repeating characters
 Find words which contains all the vowels
 Find words which contains most consonants
 Find words which contains more than 3 vowels
 Find words which first and last three letters are equals
 Find words which odd letters are consonants and even letters are vowels or vice_versa
Formatting
 Substring
 Rep-string
 Word wrap
 String case
 Align columns
 Literals/String
 Repeat a string
 Brace expansion
 Brace expansion using ranges
 Reverse a string
 Phrase reversals
 Comma quibbling
 Special characters
 String concatenation
 Substring/Top and tail
 Commatizing numbers
 Reverse words in a string
 Suffixation of decimal numbers
 Long literals, with continuations 
 Numerical and alphabetical suffixes
 Abbreviations, easy
 Abbreviations, simple
 Abbreviations, automatic
Song lyrics/poems/Mad Libs/phrases
 Mad Libs
 Magic 8-ball
 99 Bottles of Beer
 The Name Game (a song)
 The Old lady swallowed a fly
 The Twelve Days of Christmas
Tokenize
 Text between
 Tokenize a string
 Word break problem
 Tokenize a string with escaping
 Split a character string based on change of character
Sequences
 Show ASCII table
 De Bruijn sequences
 Self-referential sequences
 Generate lower case ASCII alphabet




References

   Wikipedia entry:   de Bruijn sequence.
   MathWorld entry:   de Bruijn sequence.
   An  OEIS  entry:   A166315 lexicographically earliest binary de Bruijn sequences, B(2,n)     --- Not B(10,4),   but possibly relevant.


putch:	equ	2	; Print character
puts:	equ	9	; Print string
	cpu	8086
	bits	16
section	.text
	org	100h
	;;;	Calculate de_bruijn(10, 4) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	xor	ax,ax		; zero a[]
	mov	di,arr
	mov	cx,20		; 20 words = 40 bytes
	rep	stosw
	mov	di,seq		; start of sequence
	mov	dx,0101h	; db(1,1)
	call	db_
	mov	si,seq		; Add first 3 to end for wrapping
	mov	cx,3
	rep	movsb
	lea	bp,[di-1]	; Store pointer to last digit in BP
	;;;	Print length ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	mov	ah,puts		; Print "Length:"
	mov	dx,slen
	int	21h
	mov	ax,di		; Length = end - start
	sub	ax,seq
	call	putax		; Print length
	;;;	Print first and last 130 characters and verify ;;;;;;;;;;;;;;;;
	mov	ah,puts		; Print "First 130..."
	mov	dx,sfrst
	int	21h
	mov	si,seq		; print first 130 digits
	call	p130
	mov	ah,puts		; Print "Last 130..."
	mov	dx,slast
	int 	21h
	mov	si,di		; print last 130 digit 
	sub	si,130
	call	p130
	call	verify
	;;;;	Reverse the sequence and verify ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	mov	ah,puts		; Print "Reversing..."
	mov	dx,srev
	int	21h
	mov	si,seq		; SI = first digit in sequence
	mov	di,bp		; DI = last digit in sequence
	call	rvrs		; Reverse
	call	verify		; Verify
	mov	si,seq		; Reverse again, putting it back
	mov	di,bp
	call	rvrs
	;;;	Set seq[4444] to '.' and verify ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	mov	ah,puts		; Print "set seq[4444] to '.'"
	mov	dx,s4444
	int	21h
	mov	[seq+4444],byte '.'
	call	verify		; Verify
	ret
	;;;	db(t, p); t=dh p=dl, di=seq ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
db_:	cmp	dh,4		; t>n? (n=4)
	jbe	.els
	cmp	dl,3		; for p in {1,2,3,4}, 4%p==0 iff p=3
	je	.out
	mov	si,arr+1	; add DL=P bytes from a[1..] to sequence
	mov	cl,dl
	xor 	ch,ch
	rep	movsb
	jmp	.out
.els:	xor	bh,bh
	mov	bl,dh
	sub	bl,dl		; t - p
	mov	al,[arr+bx]	; al = a[t-p]
	mov	bl,dh		; t 
	mov	[arr+bx],al	; a[t] = al
	push	dx		; keep arguments
	inc	dh		; db(++t,p)
	call	db_			
	pop	dx		; restore arguments
	mov	bl,dh		; al = a[t-p]
	sub	bl,dl
	mov	al,[arr+bx]
.loop:	inc	al		; al++
	cmp	al,10		; when al>=k,
	jae	.out		; then stop.
	mov	bl,dh
	mov	[arr+bx],al	; a[t] = j
	push	ax		; keep state
	push	dx
	mov	dl,dh		; db(t+1, t)
	inc	dh
	call	db_
	pop	dx
	pop	ax
	jmp	.loop
.out:	ret
	;;;	Verify that all numbers are there ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
verify:	mov	ah,puts		; Print "verifying..."
	mov	dx,sver
	int	21h
	mov	di,val		; Zero validation array
	mov	cx,5000		; 10000 bytes = 5000 words
	xor	ax,ax
	rep	stosw
	mov	di,val
	mov	si,seq		; Pointer to start of sequence
	mov	cx,6409h	; CH=100 (multiplier), CL=9 (highest digit)
.num:	mov	ax,[si]		; Read first two digits
	cmp	ah,cl		; Check that they are valid
	ja	.inval
	cmp	al,cl
	ja	.inval
	xchg	al,ah		; High digit * 10 + low digit
	aad
	mul	ch		; Multiply by 100 (to add in next two)
	mov	bx,ax
	mov	ax,[si+2]	; Read last two digits
	cmp	ah,cl		; Check that they are valid
	ja	.inval
	cmp	al,cl
	ja	.inval
	xchg	al,ah		; High digit * 10 + low digit
	aad
	add	bx,ax		; BX = final 4-digit number
	inc	byte [di+bx]	; Mark this 4-digit number as seen
.inval:	inc	si		; Next digit
	cmp	si,seq+10000	; Are we at the end yet?
	jne	.num		; If not, do next number
	mov	si,val		; For each number < 10000, check if it's there
	xor	cl,cl		; Will be set if a number is missing
.test:	lodsb			; Do we have this number?
	test	al,al
	jnz	.tnext		; If so, try next number
	mov	ax,si		; Otherwise, print the missing number
	sub	ax,val
	call	putax
	mov	cl,1		; And set CL
.tnext:	cmp	si,val+10000	; Are we at the end yet?
	jne	.test
	test	cl,cl
	mov	dx,smiss	; Print "... missing"
	jnz	.print		; if CL is set
	mov	dx,snone	; or "none missing" otherwise.
.print:	mov	ah,puts
	int	21h
	ret
	;;;	Subroutines ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	;;;	Print number in AX
putax:	push	ax		; Keep registers we're changing
	push	dx		
	push	bx
	push	di
	mov	di,numbuf	; Pointer to number buffer
	mov	bx,10		; Divisor
.digit:	xor	dx,dx		; Divide AX by 10
	div	bx
	add	dl,'0'		; Add '0' to remainder (digit)
	dec	di		; Store digit in buffer
	mov	[di],dl
	test	ax,ax		; Any more digits?
	jnz	.digit		; If so, do next digits
	mov	dx,di		; At the end, print the string
	mov	ah,puts
	int	21h
	pop	di		; Restore registers
	pop	bx
	pop	dx
	pop	ax
	ret 
	;;;	Print 130 digits starting at SI
p130:	mov	cx,130		; 130 characters
	mov	ah,putch	; Print characters
.loop:	lodsb			; Get digit
	add	al,'0'		; Make ASCII
	mov	dl,al		; Print digit
	int	21h
	loop 	.loop
	ret
	;;;	Reverse memory starting at SI and ending at DI
rvrs:	mov	al,[si]		; Load [SI],
	mov	ah,[di]		; Load [DI],
	mov	[di],al		; Set [DI] = old [SI]
	mov	[si],ah		; Set [SI] = old [DI]
	inc	si		; Increment bottom pointer
	dec	di		; Decrement top pointer
	cmp	si,di		; If SI >= DI, we're done
	jb	rvrs
	ret
section	.data
slen:	db	'Length: $'
sfrst:	db	13,10,'First 130: $'
slast:	db	13,10,'Last 130: $'
srev:	db	13,10,'Reversing... $'
s4444:	db	13,10,'Set seq[4444] to `.`...$'
sver:	db	13,10,'Verifying... $'
snone:	db	'none '
smiss:	db	'missing.$'
	db	'00000'
numbuf:	db	' $'
section	.bss
arr:	resb	40		; a[]
val:	resb	10000		; validation array
seq:	equ	$