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.


bdos:	equ	5	; BDOS entry point	
putch:	equ	2	; Write character to console
puts:	equ	9	; Write string to console
	org	100h
	lhld	bdos+1	; Put stack at highest usable address
	sphl
	;;;	Generate de_bruijn(10,4) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	mvi	c,40	; Zero out a[]
	xra	a
	lxi	d,arr
zloop:	stax	d
	inx	d
	dcr	c
	jnz	zloop
	lxi	h,seq	; H = start of sequence
	lxi	b,0101h	; db(1,1)
	call	db_
	lxi	d,seq	; Allow wrap-around by appending first 3 digits
	mvi	c,3
wrap:	ldax	d	; get one of first digits
	mov	m,a	; store after last digit
	inx	d	; advance pointers
	inx	h
	dcr	c	; do this 3 times
	jnz	wrap
	push	h	; store end of data
	;;;	Print length ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	lxi	d,slen	; print "Length: "
	call	pstr
	lxi 	d,-seq	; calculate length (-seq+seqEnd)
	dad	d
	call	puthl	; print length
	call	pnl	; print newline
	;;;	Print first and last 130 digits ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	lxi	d,sfrst	; print "First 130: "
	call	pstr
	lxi 	h,seq	; print first 130 digits
	call	p130
	call	pnl	; print newline
	lxi	d,slast	; print "Last 130: "
	call	pstr
	pop	h	; Get end of sequence
	push	h
	lxi	d,-130	; 130th last digit 
	dad	d
	call	p130	; print last 130 digits
	call	pnl
	call	verify	; verify that all numbers are there
	;;;	Reverse and verify ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	lxi	d,srev	; Print "reversing..."
	call	pstr
	pop	h	; HL = address of last digit
	dcx	h
	push	h	; stack = address of last digit
	lxi	d,seq	; DE = address of first digit
	call	rvrs	; Reverse
	call	verify	; Verify that all numbers are there
	lxi	d,seq	; Then reverse again (restoring it)
	pop	h
	call	rvrs
	;;;	Replace 4444th digit with '.' and verify ;;;;;;;;;;;;;;;;;;;;;;
	lxi	d,s4444
	call	pstr
	mvi	a,'.'
	sta	seq+4444
	call	verify
	rst	0
	;;;	db(t,p); t,p in B,C; end of sequence in HL ;;;;;;;;;;;;;;;;;;;;
db_:	mov	a,b	; if t>n (n=4)
	cpi	5	; t >= n+1
	jc	dbelse
	mov	a,c	; 4%p==0, for p in {1,2,3,4}, is false iff p=3
	cpi	3
	rz		; stop if p=3, i.e. 4%p<>0
	lxi	d,arr+1	; copy P elements to seq forom arr[1..]
dbextn:	ldax	d	; take from a[]
	mov	m,a	; store in sequence
	inx	h	; advance pointers
	inx	d
	dcr	c	; and do this P times
	jnz	dbextn
	ret
dbelse:	mov	a,b	; t - p
	sub	c
	mvi	d,arr/256
	mov	e,a	; a[] is page-aligned for easier indexing
	ldax	d	; get a[t-p]
	mov	e,b	; store in a[t]
	stax	d
	push	b	; keep T and P 
	inr	b	; db(t+1, p)
	call	db_
	pop	b	; restore T and P
	mov	a,b	; get a[t-p]
	sub	c
	mvi	d,arr/256
	mov	e,a
	ldax	d	; j = a[t-p]
dbloop:	inr	a	; j++
	cpi	10	; reached K = 10?
	rnc		; then stop
	mvi	d,arr/256
	mov	e,b
	stax	d	; a[t] = j
	push	psw	; keep j
	push	b	; keep t and p
	mov	c,b
	inr	b
	call	db_	; db(t+1, t)
	pop	b	; restore t and p
	pop	psw	; restore j
	jmp	dbloop
	;;;	Verify that all numbers are there ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
verify:	lxi	d,sver	; print "Verifying... "
	call	pstr
	mvi	d,0	; Zero out the flag array
	lxi	b,10000	
	lxi	h,val
vzero:	mov	m,d
	inx	h
	dcx	b
	mov	a,b
	ora	c
	jnz	vzero
	lxi	h,seq	; Sequence pointer
donum:	push	h	; Store sequence pointer
	push	h	; Push two copies
	lxi	h,0	; Current 4-digit number
	mvi	c,4	; Number has 4 digits
dgtadd:	mov	d,h	; HL *= 10 
	mov	e,l
	dad	h
	dad	h
	dad	d
	dad	h
	xthl		; Get sequence pointer
	mov	a,m	; Get digit
	inx	h	; Advance pointer
	cpi	10	; Valid digit?
	jnc	dinval	; If not, go do next 4-digit number
	xthl		; Back to number
	mov	e,a
	mvi	d,0
	dad	d	; Add digit to number
	dcr	c	; More digits?
	jnz	dgtadd	; Then get digit
	lxi	d,val	; HL is now the current 4-digit number
	dad	d
	inr	m 	; val[HL]++ (we've seen it)
dinval:	pop	h	; Pointer to after last valid digit
	pop	h	; Pointer to start of current number
	inx	h	; Get 4-digit number that starts at next digit	
	mov	d,h	; Next pointer in DE
	mov	e,l
	lxi	b,-(seq+10000)	; Are we there yet?
	dad	b
	mov	a,h
	ora	l
	xchg		; Next pointer back in HL
	jnz	donum	; If not done, do next number. 
	lxi	h,val	; Done - get start of validation array
	mvi	b,0	; B will be set if one is missing
vnum:	mov	a,m	; Have we seen HL-val?
	ana	a 	
	jnz	vnext	; If so, do the next number
	push	h	; Otherwise, keep current address,
	lxi	d,-val	; Subtract val (to get the number)
	dad	d
	call	puthl	; Print this number as being missing
	mvi	b,1	; Set B,
	pop 	h	; and then restore the address
vnext:	inx	h	; Increment the number
	push	h
	lxi	d,-(val+10000)	; Are we there yet?
	dad	d
	mov	a,h
	ora	l
	pop	h
	jnz	vnum	; If not, check next number.
	dcr	b	; At the end, if B was not set,
	lxi	d,snone	; print "none missing",
	jnz	pstr
	lxi	d,smiss	; otherwise, print "missing"
	jmp	pstr
	;;;	Subroutines ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	;;;	reverse memory starting at DE and ending at HL
rvrs:	mov	b,m	; Load [HL]
	ldax	d	; Load [DE]
	mov	m,a	; [HL] = old [DE]
	mov	a,b
	stax	d	; [DE] = old [HL]
	inx	d	; Move bottom pointer upwards,
	dcx	h	; Move top pointer downwards,
	mov	a,d	; D<H = not there yet
	cmp	h
	jc	rvrs
	mov	a,e	; E<L = not there yet
	cmp	l
	jc	rvrs
	ret
	;;;	print number in HL, saving registers
puthl:	push	h	; save registers
	push	d
	push	b
	lxi	b,nbuf	; number buffer pointer
	push	b	; keep it on the stack
dgt:	lxi	b,-10
	lxi	d,-1
dgtdiv:	inx	d	; calculate digit
	dad	b
	jc	dgtdiv
	mvi	a,'0'+10
	add	l
	pop	h	; get pointer from stack
	dcx	h	; go to previous digit
	mov	m,a	; store digit
	push	h 	; put pointer back
	xchg		; are there any more digits?
	mov	a,h
	ora	l
	jnz	dgt	; if so, calculate next digit
	pop	d 	; otherwise, get pointer to first digit
	jmp	pstr_	; and print the resulting string	
	;;;	print 130 digits from the sequence, starting at HL
p130:	push	h
	push	d
	push	b
	mvi	b,130	; 130 digits
p130l:	mov	a,m	; get current digit
	adi 	'0'	; make ASCII
	inx	h	; advance pointer
	push	b	; save pointer and counter
	push	h
	mvi	c,putch	; print character
	mov	e,a
	call	bdos
	pop	h	; restore pointer and counter
	pop	b
	dcr	b	; one fewer character left
	jnz	p130l	; if characters left, print next
	jmp	rsreg	; otherwise, restore registers and return
	;;;	print newline
pnl:	lxi	d,snl
	;;;	print string in DE, saving registers
pstr:	push	h	; store registers
	push	d
	push 	b
pstr_:	mvi	c,puts	; print string using CP/M
	call	bdos
rsreg:	pop	b	; restore registers
	pop	d
	pop 	h
	ret
snl:	db	13,10,'$'
slen:	db	'Length: $'
sfrst:	db	'First 130: $'
slast:	db	'Last 130: $'
srev:	db	'Reversing...',13,10,'$'
s4444:	db	'Set seq[4444] to `.`...',13,10,'$'
sver:	db	'Verifying... $'
snone:	db	'none '
smiss:	db	'missing',13,10,'$'
	db	'00000'	; number output buffer
nbuf:	db	' $'
arr:	equ	($/256+1)*256	; Place to store a[] (page-aligned)
val:	equ	arr+40		; Place to store validation flags
seq:	equ	val+10000	; Place to store De Bruijn sequence