Anonymous user
User talk:Gerard Schildberger: Difference between revisions
m
→De Bruijn sequence, a draft: a work in progress.
m (→Copy-paste error?: added a reply.) |
m (→De Bruijn sequence, a draft: a work in progress.) |
||
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 1<sup>st</sup> line, but not the 2<sup>nd</sup>. -- [[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''<sup>''n''</sup></big>, which is also the number of distinct substrings of
length <big>''n''</big> on <big>''A''</big>;
<br>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:
<big><big><big>(k!)<sup>k<sup>(n-1)</sup></sup> <big><b>÷</b></big> k<sup>n</sup></big></big></big>
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,444<sup>th</sup> 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].
<br><br>
|