User talk:Gerard Schildberger: Difference between revisions

Line 862:

: Yuppers.   It was just that.   Thanks for the heads up.   I'm trying to figure out just how that happened, I can see how I might have missed the 1st line, but not the 2nd.     -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 18:00, 7 July 2019 (UTC)

== De Bruijn sequence, a draft ==

De Bruijn sequence <---- formal Rosetta Code task name. It might (or should be) named '''De Bruijn sequences''', but I don't

know how that (the plural) might hamper the finding of that task.

$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$

««draft task»»

$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ (The above was munged up to not cause Rosetta Code consternations.)

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 is the first word in a sentence.   Rosetta Code (more or less by default or fiat) requires the first word in the task name to be

capitalized.

In combinatorial mathematics,   a   '''de Bruijn sequence'''   of order   <big> ''n'' </big>   on

a   <big> size-''k'' </big>   alphabet (computer science)   <big> ''A'' </big>   is a cyclic sequence in which every

possible   <big> length-''n'' </big>   string (computer science, formal theory)   on   <big> ''A'' </big>   occurs

exactly once as a contiguous substring.

<!--

───────────────────────────────────────────────────────────────────────────────────────────────────────

Yeah, I know, it's a pretty big mouthful, bit it's what Wikipedia uses, so I went with that definition.

───────────────────────────────────────────────────────────────────────────────────────────────────────

!-->

Such a sequence is denoted by   <big> ''B''(''k'', ''n'') </big>   and has

length   <big>''k''''n''</big>,   which is also the number of distinct substrings of

length   <big>''n''</big>   on   <big>''A''</big>;

de Bruijn sequences are therefore optimally short.

<!--

────────────────────────────────────────────────────────────────────────────────────────────────────────

Expressing the (below) equation with a <math> HTML tag causes it to "blow up" on Rosetta Code's version.

────────────────────────────────────────────────────────────────────────────────────────────────────────

!-->

There are:

distinct de Bruijn sequences   <big> ''B''(''k'', ''n''). </big>

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   [https://en.wikipedia.org/wiki/Personal_Identification_Number PIN]-like   code lock that does not have an "enter"

key and accepts the last   <big> ''n'' </big>   digits entered.

Note:   [https://en.wikipedia.org/wiki/Automated_teller_machine automated tell machines (ATMs)]   used to work like

this,   but their software has been updated to not allow a brute-force attack.

;Example:

A   [https://en.wikipedia.org/wiki/digital_door_lock 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)   presses are needed to

open the lock.

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

;Task:

:*   Generate a de Bruijn sequence for a 4-digit (decimal) PIN code.

:::*   (There are many possible de Bruijn sequences that solve this task.)

:::*   Show the first and last   '''130'''   one hundred digits of the de Bruijn sequence.

:::*   Show the length 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.

:*   Extract the 4,444th digit from the original de Bruijn sequence.

:::*   Add   '''1'''   (unity) to that digit.

:::*   Take the right-most digit of that sum.

:::*   Replace the original digit with the above digit   (in the de Bruijn sequence).

:::*   Perform the verification test (again).   There should be several 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.

;References:

:*   Wikipedia entry:   [https://en.wikipedia.org/wiki/De_Bruijn_sequence de Bruijn sequence].