user
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   *k**n*,   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 contain the most consonants
* Find words which contains more than 3 vowels
* Find words whose first and last three letters are equal
* Find words with alternating vowels and consonants

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
* Summarize and say sequence
* 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.
assistant
(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 sequence
my $seq;

for ^100 {
    my $a = .fmt: '%02d';
    next if $a.substr(1,1) < $a.substr(0,1);
    $seq ~= ($a.substr(0,1) == $a.substr(1,1)) ?? $a.substr(0,1) !! $a;
    for +$a ^..^ 100 {
        next if .fmt('%02d').substr(1,1) <= $a.substr(0,1);
        $seq ~= sprintf "%s%02d", $a, $_ ;
    }
}

$seq = $seq.comb.list.rotate((^10000).pick).join;

$seq ~= $seq.substr(0,3);

sub check ($seq) {
    my %chk;
    for ^($seq.chars) { %chk{$seq.substr( $_, 4 )}++ }
    put 'Missing: ', (^9999).grep( { not %chk{ .fmt: '%04d' } } ).fmt: '%04d';
    put 'Extra:   ', %chk.grep( *.value > 1 )».key.sort.fmt: '%04d';
}

## The Task
put "de Bruijn sequence length: " ~ $seq.chars;

put "\nFirst 130 characters:\n" ~ $seq.substr( 0, 130 );

put "\nLast 130 characters:\n" ~ $seq.substr( * - 130 );

put "\nIncorrect 4 digit PINs in this sequence:";
check $seq;

put "\nIncorrect 4 digit PINs in the reversed sequence:";
check $seq.flip;

my $digit = $seq.substr(4443,1);
put "\nReplacing the 4444th digit, ($digit) with { ($digit += 1) %= 10 }";
put "Incorrect 4 digit PINs in the revised sequence:";
$seq.substr-rw(4443,1) = $digit;
check $seq;

```

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
```