De Bruijn sequences: Difference between revisions
m
→{{header|11l}}: Void
(Add Scala implementation) |
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
||
| (3 intermediate revisions by 2 users not shown) | |||
Line 91:
[Byte] seq
F db(Int t, Int p) ->
I t > @n
I @n % p == 0
Line 1,403:
PIN number 5814 missing
PIN number 8145 missing</pre>
=={{header|EasyLang}}==
{{trans|Lua}}
<syntaxhighlight>
global a[] seq[] k n .
proc db t p . .
if t > n
if n mod p = 0
for i = 1 to p
seq[] &= a[i + 1]
.
.
else
a[t + 1] = a[t - p + 1]
db t + 1 p
j = a[t - p + 1] + 1
while j < k
a[t + 1] = j mod 256
db t + 1 t
j += 1
.
.
.
func$ debruijn k0 n0 .
k = k0
n = n0
a[] = [ ]
len a[] k * n
seq[] = [ ]
db 1 1
for v in seq[]
buf$ &= v
.
buf$ &= substr buf$ 1 (n - 1)
return buf$
.
func alldigits s$ .
for c$ in strchars s$
if strcode c$ < 48 or strcode c$ > 57
return 0
.
.
return 1
.
proc validate db$ . .
len found[] 10000
for i = 1 to len db$ - 3
s$ = substr db$ i 4
if alldigits s$ = 1
n = number s$
found[n + 1] += 1
.
.
for i = 1 to 10000
if found[i] = 0
errs$[] &= " PIN number " & i - 1 & " missing"
elif found[i] > 1
errs$[] &= " PIN number " & i - 1 & " occurs " & found[i] & " times"
.
.
if len errs$[] = 0
print " No errors found"
else
for s$ in errs$[]
print s$
.
.
.
proc main . .
db$ = debruijn 10 4
print "The length of the de Bruijn sequence is " & len db$
print ""
write "The first 130 digits of the de Bruijn sequence are: "
print substr db$ 1 130
print ""
write "The last 130 digits of the de Bruijn sequence are: "
print substr db$ -130 130
print ""
print "Validating the de Bruijn sequence:"
validate db$
print ""
print "Validating the reversed de Bruijn sequence:"
for i = len db$ downto 1
dbr$ &= substr db$ i 1
.
validate dbr$
print ""
db$ = substr db$ 1 4443 & "." & substr db$ 4445 (1 / 0)
print "Validating the overlaid de Bruijn sequence:"
validate db$
print ""
.
main
</syntaxhighlight>
=={{header|Go}}==
Line 1,943 ⟶ 2,037:
PIN number 5814 is missing
PIN number 8145 is missing</pre>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
'''Works with gojq, the Go implementation of jq'''
<syntaxhighlight lang="jq">
def allDigits:
all(explode[]; 48 <= . and . <= 57);
def lpad($len): tostring | ($len - length) as $l | ("0" * $l) + .;
def deBruijn:
{deBruijn: ""}
| reduce range(0; 100) as $n (.;
($n|lpad(2)) as $a
| ($a | explode) as [$a1, $a2]
| if $a2 >= $a1
then .deBruijn += (if ($a1 == $a2) then ([$a1]|implode) else $a end)
| .m = $n + 1
| until(.m > 99;
(.m|lpad(2)) as $ms
| if ($ms[1:2]|explode[0]) > $a1
then .deBruijn += $a + $ms
end
| .m += 1 )
end )
| .deBruijn + "000" ;
def describe:
. as $d
| "de Bruijn sequence length: \($d|length)",
"First 130 characters:",
$d[0:130],
"Last 130 characters:",
$d[-130:];
def check:
. as $text
| { res: [],
found: [range(0;10000) | 0],
k: 0 }
| reduce range( 0; $text|length-3) as $i (.;
$text[$i : $i+4] as $s
| if ($s|allDigits)
then .k = ($s|tonumber)
| .found[.k] += 1
end )
| reduce range(0; 10000) as $i (.;
.k = .found[$i]
| if .k != 1
then (" Pin number \($i) "
+ (if .k == 0 then "missing" else "occurs \(.k) times" end ) ) as $e
| .res += [$e]
end )
| .k = (.res|length)
| if .k == 0
then .res = "No errors found"
else
(if .k == 1 then "" else "s" end) as $s
| .res = "\(.k) error\($s) found:\n" + (.res | join("\n"))
end
| .res ;
# The tasks
deBruijn
| describe,
"Missing 4 digit PINs in this sequence: \(check)",
"Missing 4 digit PINs in the reversed sequence: \(explode|reverse|implode|check)",
"4,444th digit in the sequence: '\(.[4443])' (setting it to '.')",
( .[0:4443] + "." + .[4444:]
| "Re-running checks: \(check)" )
</syntaxhighlight>
{{output}}
<pre>
de Bruijn sequence length: 10003
First 130 characters:
0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350
Last 130 characters:
6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000
Missing 4 digit PINs in this sequence: No errors found
Missing 4 digit PINs in the reversed sequence: No errors found
4,444th digit in the sequence: '4' (setting it to '.')
Re-running checks: 4 errors found:
Pin number 1459 missing
Pin number 4591 missing
Pin number 5814 missing
Pin number 8145 missing
</pre>
=={{header|Julia}}==
| |||