De Bruijn sequences: Difference between revisions
Content deleted Content added
m added related tasks. |
|||
Line 1,572: | Line 1,572: | ||
Validating the overlaid de Bruijn sequence: |
Validating the overlaid de Bruijn sequence: |
||
PIN number 1459 missing |
|||
PIN number 4591 missing |
|||
PIN number 5814 missing |
|||
PIN number 8145 missing</pre> |
|||
=={{header|Nim}}== |
|||
{{trans|D}} |
|||
<lang Nim>import algorithm, parseutils, strformat, strutils |
|||
const Digits = "0123456789" |
|||
#--------------------------------------------------------------------------------------------------- |
|||
func deBruijn(k, n: int): string = |
|||
let alphabet = Digits[0..<k] |
|||
var a = newSeq[byte](k * n) |
|||
var sequence: seq[byte] |
|||
#................................................................................................. |
|||
func db(t, p: int) = |
|||
if t > n: |
|||
if n mod p == 0: |
|||
sequence &= a[1..p] |
|||
else: |
|||
a[t] = a[t - p] |
|||
db(t + 1, p) |
|||
var j = a[t - p] + 1 |
|||
while j < k.uint: |
|||
a[t] = j |
|||
db(t + 1, t) |
|||
inc j |
|||
#............................................................................................... |
|||
db(1, 1) |
|||
for i in sequence: |
|||
result &= alphabet[i] |
|||
result &= result[0..(n-2)] |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc validate(db: string) = |
|||
var found: array[10_000, int] |
|||
var errs: seq[string] |
|||
## Check all strings of 4 consecutive digits within 'db' |
|||
## to see if all 10,000 combinations occur without duplication. |
|||
for i in 0..(db.len - 4): |
|||
let s = db[i..(i+3)] |
|||
var n: int |
|||
if s.parseInt(n) == 4: |
|||
inc found[n] |
|||
for n, count in found: |
|||
if count == 0: |
|||
errs &= fmt" PIN number {n:04d} missing" |
|||
elif count > 1: |
|||
errs &= fmt" PIN number {n:04d} occurs {count} times" |
|||
if errs.len == 0: |
|||
echo " No errors found" |
|||
else: |
|||
let plural = if errs.len == 1: "" else: "s" |
|||
echo fmt" {errs.len} error{plural} found" |
|||
for err in errs: echo err |
|||
#——————————————————————————————————————————————————————————————————————————————————————————————————— |
|||
var db = deBruijn(10, 4) |
|||
echo fmt"The length of the de Bruijn sequence is {db.len}" |
|||
echo "" |
|||
echo fmt"The first 130 digits of the de Bruijn sequence are: {db[0..129]}" |
|||
echo "" |
|||
echo fmt"The last 130 digits of the de Bruijn sequence are: {db[^130..^1]}" |
|||
echo "" |
|||
echo "Validating the deBruijn sequence:" |
|||
db.validate() |
|||
echo "" |
|||
echo "Validating the reversed deBruijn sequence:" |
|||
reversed(db).join().validate() |
|||
echo "" |
|||
db[4443] = '.' |
|||
echo "Validating the overlaid deBruijn sequence:" |
|||
db.validate()</lang> |
|||
{{out}} |
|||
<pre>The length of the de Bruijn sequence is 10003 |
|||
The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 |
|||
The last 130 digits of the de Bruijn sequence are: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 |
|||
Validating the deBruijn sequence: |
|||
No errors found |
|||
Validating the reversed deBruijn sequence: |
|||
No errors found |
|||
Validating the overlaid deBruijn sequence: |
|||
4 errors found |
|||
PIN number 1459 missing |
PIN number 1459 missing |
||
PIN number 4591 missing |
PIN number 4591 missing |