Problem Statement

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: 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.

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.

(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.

Let's start with the solution:

#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))