Rosetta Code

De Bruijn sequences: Difference between revisions

Page Discussion

De Bruijn sequences (view source)

Revision as of 23:48, 27 July 2022

104 bytes removed ,  1 year ago
m
tidy up some Wikipedia and OEIS links
(Added solution for Pascal.)
m (tidy up some Wikipedia and OEIS links)
Line 36:
;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   [https[wp://en.wikipedia.org/wiki/Personal_Identification_Number |PIN]]-like   code lock that does not have an "enter"
key and accepts the last &nbsp; <big> ''n'' </big> &nbsp; digits entered.
 
 
Note: &nbsp; [https[wp://en.wikipedia.org/wiki/Automated_teller_machine |automated teller machines (ATMs)]] &nbsp; used to work like
this, &nbsp; but their software has been updated to not allow a brute-force attack.
 
 
;Example:
A &nbsp; [https[wp://en.wikipedia.org/wiki/digital_door_lock |digital door lock]] &nbsp; with a 4-digit code would
have ''B''&thinsp;(10,&nbsp;4) solutions, &nbsp; with a length of &nbsp; '''10,000''' &nbsp; (digits).
 
Line 76:
 
;References:
:* &nbsp; Wikipedia entry: &nbsp; [https[wp://en.wikipedia.org/wiki/De_Bruijn_sequence |de Bruijn sequence]].
:* &nbsp; MathWorld entry: &nbsp; [http://mathworld.wolfram.com/deBruijnSequence.html de Bruijn sequence].
:* &nbsp; An &nbsp;OEIS&nbsp; entry: &nbsp; [https[oeis://oeis.org/A166315 |A166315 lexicographically earliest binary de Bruijn sequences, B(2,n)]] &nbsp; &nbsp; --- Not B(10,4), &nbsp; but possibly relevant.
<br><br>
 
Line 1,676:
=={{header|Haskell}}==
=== Permutation-based ===
Straight-forward implementation of inverse Burrows—Wheeler transform [https[wp://en.wikipedia.org/wiki/De_Bruijn_sequence#Construction|De_Bruijn_sequence#Construction] is reasonably efficient for the task (about a milliseconds for B(10,4) in GHCi).
 
<lang haskell>import Data.List
Thundergnat
10,333

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/293598"