De Bruijn sequences: Difference between revisions
m
→{{header|11l}}: Void
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
|||
| (18 intermediate revisions by 12 users not shown) | |||
Line 1:
{{task}}
{{DISPLAYTITLE:de Bruijn sequences}}
The sequences are named after the Dutch mathematician Nicolaas Govert de Bruijn.
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 [
key and accepts the last <big> ''n'' </big> digits entered.
Note: [
this, but their software has been updated to not allow a brute-force attack.
;Example:
A [
have ''B'' (10, 4) solutions, with a length of '''10,000''' (digits).
Line 64:
:* Again, perform the (above) verification test.
:* Replace the 4,444<sup>th</sup> digit with a period (.) in the original de Bruijn sequence.
:::* Perform the verification test (again). There should be
Line 76:
;References:
:* Wikipedia entry: [
:* MathWorld entry: [http://mathworld.wolfram.com/deBruijnSequence.html de Bruijn sequence].
:* An OEIS entry: [
<br><br>
=={{header|11l}}==
{{trans|D}}
<syntaxhighlight lang="11l">V digits = ‘0123456789’
F deBruijn(k, n)
V alphabet = :digits[0 .< k]
V a = [Byte(0)] * (k * n)
[Byte] seq
F db(Int t, Int p) -> Void
I t > @n
I @n % p == 0
@seq.extend(@a[1 .< p + 1])
E
@a[t] = @a[t - p]
@db(t + 1, p)
V j = @a[t - p] + 1
L j < @k
@a[t] = j [&] F'F
@db(t + 1, t)
j++
db(1, 1)
V buf = ‘’
L(i) seq
buf ‘’= alphabet[i]
R buf‘’buf[0 .< n - 1]
F validate(db)
V found = [0] * 10'000
[String] errs
L(i) 0 .< db.len - 3
V s = db[i .< i + 4]
I s.is_digit()
found[Int(s)]++
L(i) 10'000
I found[i] == 0
errs [+]= ‘ PIN number #04 missing’.format(i)
E I found[i] > 1
errs [+]= ‘ PIN number #04 occurs #. times’.format(i, found[i])
I errs.empty
print(‘ No errors found’)
E
V pl = I errs.len == 1 {‘’} E ‘s’
print(‘ ’String(errs.len)‘ error’pl‘ found:’)
L(err) errs
print(err)
V db = deBruijn(10, 4)
print(‘The length of the de Bruijn sequence is ’db.len)
print("\nThe first 130 digits of the de Bruijn sequence are: "db[0.<130])
print("\nThe last 130 digits of the de Bruijn sequence are: "db[(len)-130..])
print("\nValidating the deBruijn sequence:")
validate(db)
print("\nValidating the reversed deBruijn sequence:")
validate(reversed(db))
db[4443] = ‘.’
print("\nValidating the overlaid deBruijn sequence:")
validate(db)</syntaxhighlight>
{{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 4591 missing
PIN number 5814 missing
PIN number 8145 missing
</pre>
=={{header|8080 Assembly}}==
<
putch: equ 2 ; Write character to console
puts: equ 9 ; Write string to console
Line 348 ⟶ 439:
arr: equ ($/256+1)*256 ; Place to store a[] (page-aligned)
val: equ arr+40 ; Place to store validation flags
seq: equ val+10000 ; Place to store De Bruijn sequence</
{{out}}
Line 363 ⟶ 454:
=={{header|8086 Assembly}}==
<
puts: equ 9 ; Print string
cpu 8086
Line 562 ⟶ 653:
arr: resb 40 ; a[]
val: resb 10000 ; validation array
seq: equ $</
{{out}}
Line 575 ⟶ 666:
Verifying... 1460 4592 5915 8146 missing.</pre>
=={{header|Ada}}==
{{trans|D}}
<syntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO;
with Ada.Strings.Fixed; use Ada.Strings;
with Ada.Strings.Unbounded;
procedure De_Bruijn_Sequences is
function De_Bruijn (K, N : Positive) return String
is
use Ada.Strings.Unbounded;
Alphabet : constant String := "0123456789";
subtype Decimal is Integer range 0 .. 9;
type Decimal_Array is array (Natural range <>) of Decimal;
A : Decimal_Array (0 .. K * N - 1) := (others => 0);
Seq : Unbounded_String;
procedure Db (T, P : Positive) is
begin
if T > N then
if N mod P = 0 then
for E of A (1 .. P) loop
Append (Seq, Alphabet (Alphabet'First + E));
end loop;
end if;
else
A (T) := A (T - P);
Db (T + 1, P);
for J in A (T - P) + 1 .. K - 1 loop
A (T) := J;
Db (T + 1, T);
end loop;
end if;
end Db;
begin
Db (1, 1);
return To_String (Seq) & Slice (Seq, 1, N - 1);
end De_Bruijn;
function Image (Value : Integer) return String
is (Fixed.Trim (Value'Image, Left));
function PIN_Image (Value : Integer) return String
is (Fixed.Tail (Image (Value), Count => 4, Pad => '0'));
procedure Validate (Db : String)
is
Found : array (0 .. 9_999) of Natural := (others => 0);
Errors : Natural := 0;
begin
-- Check all strings of 4 consecutive digits within 'db'
-- to see if all 10,000 combinations occur without duplication.
for A in Db'First .. Db'Last - 3 loop
declare
PIN : String renames Db (A .. A + 4 - 1);
begin
if (for all Char of PIN => Char in '0' .. '9') then
declare
N : constant Integer := Integer'Value (PIN);
F : Natural renames Found (N);
begin
F := F + 1;
end;
end if;
end;
end loop;
for I in 0_000 .. 9_999 loop
if Found (I) = 0 then
Put_Line (" PIN number " & PIN_Image (I) & " missing");
Errors := Errors + 1;
elsif Found (I) > 1 then
Put_Line (" PIN number " & PIN_Image (I) & " occurs "
& Image (Found (I)) & " times");
Errors := Errors + 1;
end if;
end loop;
case Errors is
when 0 => Put_Line (" No errors found");
when 1 => Put_Line (" 1 error found");
when others =>
Put_Line (" " & Image (Errors) & " errors found");
end case;
end Validate;
function Backwards (S : String) return String is
R : String (S'Range);
begin
for A in 0 .. S'Length - 1 loop
R (R'Last - A) := S (S'First + A);
end loop;
return R;
end Backwards;
DB : constant String := De_Bruijn (K => 10, N => 4);
Rev : constant String := Backwards (DB);
Ovl : String := DB;
begin
Put_Line ("The length of the de Bruijn sequence is " & DB'Length'Image);
New_Line;
Put_Line ("The first 130 digits of the de Bruijn sequence are: ");
Put_Line (" " & Fixed.Head (DB, 130));
New_Line;
Put_Line ("The last 130 digits of the de Bruijn sequence are: ");
Put_Line (" " & Fixed.Tail (DB, 130));
New_Line;
Put_Line ("Validating the deBruijn sequence:");
Validate (DB);
New_Line;
Put_Line ("Validating the reversed deBruijn sequence:");
Validate (Rev);
New_Line;
Ovl (4444) := '.';
Put_Line ("Validating the overlaid deBruijn sequence:");
Validate (Ovl);
New_Line;
end De_Bruijn_Sequences;</syntaxhighlight>
{{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:
PIN number 1459 missing
PIN number 4591 missing
PIN number 5814 missing
PIN number 8145 missing
4 errors found
</pre>
=={{header|BASIC}}==
<syntaxhighlight lang="gwbasic">10 DEFINT A-Z
20 K = 10: N = 4
30 DIM A(K*N), S(K^N+N), T(5), P(5), V(K^N\8)
40 GOSUB 200
50 PRINT "Length: ",S
60 PRINT "First 130:"
70 FOR I=0 TO 129: PRINT USING "#";S(I);: NEXT
80 PRINT: PRINT "Last 130:"
90 FOR I=S-130 TO S-1: PRINT USING "#";S(I);: NEXT
100 PRINT
110 GOSUB 600
120 PRINT "Reversing...": GOSUB 500: GOSUB 600: GOSUB 500
130 PRINT USING "Replacing 4444'th element (#):";S(4443)
140 S(4443) = -1 : REM 0-indexed, and using integers
150 GOSUB 600
160 END
200 REM Generate De Bruijn sequence given K and N
210 T(R) = 1: P(R) = 1
220 IF T(R) > N GOTO 380
230 A(T(R)) = A(T(R)-P(R))
240 R = R+1
250 T(R) = T(R-1)+1
260 P(R) = P(R-1)
270 GOSUB 220
280 R = R-1
290 FOR J = A(T(R)-P(R))+1 TO K-1
300 A(T(R)) = J
310 R = R+1
320 T(R) = T(R-1)+1
330 P(R) = T(R-1)
340 GOSUB 220
350 R = R-1
355 J = A(T(R))
360 NEXT
370 RETURN
380 IF N MOD P(R) THEN RETURN
390 FOR I = 1 TO P(R)
400 S(S) = A(I)
410 S = S+1
420 NEXT
430 RETURN
500 REM Reverse the sequence
510 FOR I=0 TO S\2
520 J = S(I)
530 S(I) = S(S-I)
540 S(S-I) = J
550 NEXT
560 RETURN
600 REM Validate the sequence (uses bit packing to save memory)
610 PRINT "Validating...";
620 FOR I=0 TO N-1: S(S+I)=S(I): NEXT
630 FOR I=0 TO K^N\8-1: V(I)=0: NEXT
640 FOR I=0 TO S
650 P=0
660 FOR J=0 TO N-1
662 D=S(I+J)
663 IF D<0 GOTO 690
665 P=K*P+D
669 NEXT J
670 X=P\8
680 V(X) = V(X) OR 2^(P AND 7)
690 NEXT I
700 M=1
710 FOR I=0 TO K^N\8-1
720 IF V(I)=255 GOTO 760
730 FOR J=0 TO 7
740 IF (V(I) AND 2^J)=0 THEN M=0: PRINT USING " ####";I*8+J;
750 NEXT
760 NEXT
770 IF M THEN PRINT " none";
780 PRINT " missing."
790 RETURN</syntaxhighlight>
{{out}}
<pre>Length: 10000
First 130:
00001000200030004000500060007000800090011001200130014001500160017001800190021002
20023002400250026002700280029003100320033003400350
Last 130:
89768986899696977697869796987698869896997699869997777877797788778977987799787879
78887889789878997979887989799879998888988998989999
Validating... none missing.
Reversing...
Validating... none missing.
Replacing 4444'th element (4):
Validating... 1459 4591 5814 8145 missing.</pre>
=={{header|C sharp|C#}}==
{{trans|Kotlin}}
<
using System.Collections.Generic;
using System.Text;
Line 682 ⟶ 1,011:
}
}
}</
{{out}}
<pre>The length of the de Bruijn sequence is 10003
Line 705 ⟶ 1,034:
=={{header|C++}}==
{{trans|D}}
<
#include <functional>
#include <iostream>
Line 819 ⟶ 1,148:
return 0;
}</
{{out}}
<pre>The length of the de Bruijn sequence is 10003
Line 839 ⟶ 1,168:
PIN number 5814 missing
PIN number 8145 missing</pre>
=={{header|CLU}}==
<syntaxhighlight lang="clu">% Generate the De Bruijn sequence consisiting of N-digit numbers
de_bruijn = cluster is generate
rep = null
own k: int := 0
own n: int := 0
own a: array[int] := array[int]$[]
own seq: array[int] := array[int]$[]
generate = proc (k_, n_: int) returns (string)
k := k_
n := n_
a := array[int]$fill(0, k*n, 0)
seq := array[int]$[]
db(1, 1)
s: stream := stream$create_output()
for i: int in array[int]$elements(seq) do
stream$puts(s, int$unparse(i))
end
return(stream$get_contents(s))
end generate
db = proc (t, p: int)
if t>n then
if n//p = 0 then
for i: int in int$from_to(1, p) do
array[int]$addh(seq, a[i])
end
end
else
a[t] := a[t - p]
db(t+1, p)
for j: int in int$from_to(a[t - p] + 1, k-1) do
a[t] := j
db(t + 1, t)
end
end
end db
end de_bruijn
% Reverse a string
reverse = proc (s: string) returns (string)
r: array[char] := array[char]$predict(1, string$size(s))
for c: char in string$chars(s) do
array[char]$addl(r, c)
end
return(string$ac2s(r))
end reverse
% Find all missing N-digit values
find_missing = proc (db: string, n: int) returns (sequence[string])
db := db || string$substr(db, 1, n) % wrap
missing: array[string] := array[string]$[]
s: stream := stream$create_output()
for i: int in int$from_to(0, 10**n-1) do
%s: stream := stream$create_output()
stream$reset(s)
stream$putzero(s, int$unparse(i), n)
val: string := stream$get_contents(s)
if string$indexs(val, db) = 0 then
array[string]$addh(missing, val)
end
end
return(sequence[string]$a2s(missing))
end find_missing
% Report all missing values, or 'none'.
validate = proc (s: stream, db: string, n: int)
stream$puts(s, "Validating...")
missing: sequence[string] := find_missing(db, n)
for v: string in sequence[string]$elements(missing) do
stream$puts(s, " " || v)
end
if sequence[string]$size(missing) = 0 then
stream$puts(s, " none")
end
stream$putl(s, " missing.")
end validate
start_up = proc ()
po: stream := stream$primary_output()
% Generate the De Bruijn sequence for 4-digit numbers
db: string := de_bruijn$generate(10, 4)
% Report length and first and last digits
stream$putl(po, "Length: " || int$unparse(string$size(db)))
stream$putl(po, "First 130 characters:")
stream$putl(po, string$substr(db, 1, 130))
stream$putl(po, "Last 130 characters:")
stream$putl(po, string$substr(db, string$size(db)-130, 130))
% See if there are any missing values in the sequence
validate(po, db, 4)
% Reverse and validate again
stream$putl(po, "Reversing...")
validate(po, reverse(db), 4)
% Replace the 4444'th element with '.' and validate again
stream$putl(po, "Setting the 4444'th character to '.'...")
db := string$substr(db, 1, 4443) || "." || string$rest(db, 4445)
validate(po, db, 4)
end start_up</syntaxhighlight>
{{out}}
<pre>Length: 10000
First 130 characters:
0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350
Last 130 characters:
6897689868996969776978697969876988698969976998699977778777977887789779877997878797888788978987899797988798979987999888898899898999
Validating... none missing.
Reversing...
Validating... none missing.
Setting the 4444'th character to '.'...
Validating... 1459 4591 5814 8145 missing.</pre>
=={{header|D}}==
{{trans|Kotlin}}
<
import std.conv;
import std.format;
Line 938 ⟶ 1,383:
writeln("\nValidating the overlaid deBruijn sequence:");
validate(db);
}</
{{out}}
<pre>The length of the de Bruijn sequence is 10003
Line 958 ⟶ 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}}==
<
import (
Line 1,069 ⟶ 1,608:
fmt.Println("\nValidating the overlaid de Bruijn sequence:")
validate(db)
}</
{{out}}
Line 1,097 ⟶ 1,636:
=={{header|Groovy}}==
{{trans|Java}}
<
class DeBruijn {
Line 1,208 ⟶ 1,747:
validate(sb.toString())
}
}</
{{out}}
<pre>The length of the de Bruijn sequence is 10003
Line 1,228 ⟶ 1,767:
PIN number 5814 is missing
PIN number 8145 is missing</pre>
=={{header|Haskell}}==
=== Permutation-based ===
Straight-forward implementation of inverse Burrows—Wheeler transform [[wp:De_Bruijn_sequence#Construction|De_Bruijn_sequence#Construction] is reasonably efficient for the task (about a milliseconds for B(10,4) in GHCi).
<syntaxhighlight lang="haskell">import Data.List
import Data.Map ((!))
import qualified Data.Map as M
-- represents a permutation in a cycle notation
cycleForm :: [Int] -> [[Int]]
cycleForm p = unfoldr getCycle $ M.fromList $ zip [0..] p
where
getCycle p
| M.null p = Nothing
| otherwise =
let Just ((x,y), m) = M.minViewWithKey p
c = if x == y then [] else takeWhile (/= x) (iterate (m !) y)
in Just (c ++ [x], foldr M.delete m c)
-- the set of Lyndon words generated by inverse Burrows—Wheeler transform
lyndonWords :: Ord a => [a] -> Int -> [[a]]
lyndonWords s n = map (ref !!) <$> cycleForm perm
where
ref = concat $ replicate (length s ^ (n - 1)) s
perm = s >>= (`elemIndices` ref)
-- returns the de Bruijn sequence of order n for an alphabeth s
deBruijn :: Ord a => [a] -> Int -> [a]
deBruijn s n = let lw = concat $ lyndonWords n s
in lw ++ take (n-1) lw</syntaxhighlight>
<pre>λ> cycleForm [1,4,3,2,0]
[[1,4,0],[3,2]]
λ> lyndonWords "ab" 3
["a","aab","abb","b"]
λ> deBruijn "ab" 3
"aaababbbaa"</pre>
The task.
<syntaxhighlight lang="haskell">import Control.Monad (replicateM)
main = do
let symbols = ['0'..'9']
let db = deBruijn symbols 4
putStrLn $ "The length of de Bruijn sequence: " ++ show (length db)
putStrLn $ "The first 130 symbols are:\n" ++ show (take 130 db)
putStrLn $ "The last 130 symbols are:\n" ++ show (drop (length db - 130) db)
let words = replicateM 4 symbols
let validate db = filter (not . (`isInfixOf` db)) words
putStrLn $ "Words not in the sequence: " ++ unwords (validate db)
let db' = a ++ ('.': tail b) where (a,b) = splitAt 4444 db
putStrLn $ "Words not in the corrupted sequence: " ++ unwords (validate db') </syntaxhighlight>
<pre>λ> main
The length of de Bruijn sequence: 10003
The first 130 symbols are:
"0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350"
The last 130 symbols are:
"6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000"
Words not in the sequence:
Words not in the corrupted sequence: 1459 4591 5914 8145</pre>
=== Array-based ===
{{trans|Python}}
<syntaxhighlight lang="haskell">import Control.Monad.State
import Data.Array (Array, listArray, (!), (//))
import qualified Data.Array as A
deBruijn :: [a] -> Int -> [a]
deBruijn s n =
let
k = length s
db :: Int -> Int -> State (Array Int Int) [Int]
db t p =
if t > n
then
if n `mod` p == 0
then get >>= \a -> return [ a ! k | k <- [1 .. p]]
else return []
else do
a <- get
x <- setArray t (a ! (t-p)) >> db (t+1) p
a <- get
y <- sequence [ setArray t j >> db (t+1) t
| j <- [a ! (t-p) + 1 .. k - 1] ]
return $ x ++ concat y
setArray i x = modify (// [(i, x)])
seqn = db 1 1 `evalState` listArray (0, k*n-1) (repeat 0)
in [ s !! i | i <- seqn ++ take (n-1) seqn ]</syntaxhighlight>
=={{header|J}}==
definitions. The C. verb computes the cycles. J's sort is
<
repeat_alphabet=: [: , [: i.&> (^ <:) # [
Line 1,241 ⟶ 1,880:
groups=: [ ]\ ] , ({.~ <:)~ NB. length x infixes of sequence y cyclically extended by x-1
verify_PINs=: (/:~@:groups -: pins@:[) NB. LENGTH verify_PINs SEQUENCE
</
A=: 10 de_bruijn 4
Line 1,260 ⟶ 1,899:
4 verify_PINs (a.i.'.') (<: 4444)} A
0
</syntaxhighlight>
=={{header|Java}}==
{{trans|C++}}
<
import java.util.Arrays;
import java.util.List;
Line 1,378 ⟶ 2,017:
validate(sb.toString());
}
}</
{{out}}
<pre>The length of the de Bruijn sequence is 10003
Line 1,398 ⟶ 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}}==
<
alphabet = b"0123456789abcdefghijklmnopqrstuvwxyz"[1:k]
a = zeros(UInt8, k * n)
Line 1,445 ⟶ 2,173:
print("Testing the reversed sequence: "), verifyallPIN(reverse(s), 10, 4)
println("\nAfter replacing 4444th digit with \'.\':"), verifyallPIN(s, 10, 4, 4444)
</
<pre>
The length of the sequence is 10003. The first 130 digits are:
Line 1,464 ⟶ 2,192:
=={{header|Kotlin}}==
{{trans|Go}}
<
fun deBruijn(k: Int, n: Int): String {
Line 1,557 ⟶ 2,285:
println("\nValidating the overlaid deBruijn sequence:")
validate(db)
}</
{{out}}
<pre>The length of the de Bruijn sequence is 10003
Line 1,580 ⟶ 2,308:
=={{header|Lua}}==
{{trans|C++}}
<
for i,v in pairs(tbl) do
print(v)
Line 1,691 ⟶ 2,419:
end
main()</
{{out}}
<pre>The length of the de Bruijn sequence is 10003
Line 1,712 ⟶ 2,440:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
seq = seq~Join~Take[seq, 3];
Length[seq]
Line 1,729 ⟶ 2,457:
StringDrop[ToString[NumberForm[#, 4, NumberPadding -> {"0", "0"}]],
1] & /@ Range[0, 9999],
Union[StringJoin /@ Partition[ToString /@ seq, 4, 1]]]</
{{out}}
Line 1,751 ⟶ 2,479:
=={{header|Nim}}==
{{trans|D}}
<
const Digits = "0123456789"
Line 1,832 ⟶ 2,560:
db[4443] = '.'
echo "Validating the overlaid deBruijn sequence:"
db.validate()</
{{out}}
Line 1,853 ⟶ 2,581:
PIN number 5814 missing
PIN number 8145 missing</pre>
=={{header|Pascal}}==
A console application in Free Pascal, created with the Lazarus IDE.
For a given word length n, constructs a de Bruijn sequence by concatenating, in lexicographic order, all the Lyndon words whose length divides n. (See Wikipedia article "de Bruijn sequence", section "Construction".)
<syntaxhighlight lang="pascal">
program deBruijnSequence;
uses SysUtils;
// Create a de Bruijn sequence for the given word length and alphabet.
function deBruijn( const n : integer; // word length
const alphabet : string) : string;
var
d, k, m, s, t, seqLen : integer;
w : array of integer;
begin
k := Length( alphabet);
// de Bruijn sequence will have length k^n
seqLen := 1;
for t := 1 to n do seqLen := seqLen*k;
SetLength( result, seqLen);
d := 0; // index into de Bruijn sequence (will be pre-inc'd)
// Work through Lyndon words of length <= n, in lexicographic order.
SetLength( w, n); // w holds array of indices into the alphabet
w[0] := 1; // first Lyndon word
m := 1; // m = length of Lyndon word
repeat
// If m divides n, append the current Lyndon word to the output
if (m = n) or (m = 1) or (n mod m = 0) then begin
for t := 0 to m - 1 do begin
inc(d);
result[d] := alphabet[w[t]];
end;
end;
// Get next Lyndon word using Duval's algorithm:
// (1) Fill w with repetitions of current word
s := 0; t := m;
while (t < n) do begin
w[t] := w[s];
inc(t); inc(s);
if s = m then s := 0;
end;
// (2) Repeatedly delete highest index k from end of w, if present
m := n;
while (m > 0) and (w[m - 1] = k) do dec(m);
// (3) If word is now null, stop; else increment end value
if m > 0 then inc( w[m - 1]);
until m = 0;
Assert( d = seqLen); // check that the sequence is exactly filled in
end;
// Check a de Bruijn sequence, assuming that its alphabet consists
// of the digits '0'..'9' (in any order);
procedure CheckDecimal( const n : integer; // word length
const deB : string);
var
count : array of integer;
j, L, pin, nrErrors : integer;
wrap : string;
begin
L := Length( deB);
// The de Bruijn sequence is cyclic; make an array to handle wrapround.
SetLength( wrap, 2*n - 2);
for j := 1 to n - 1 do wrap[j] := deB[L + j - n + 1];
for j := n to 2*n - 2 do wrap[j] := deB[j - n + 1];
// Count occurrences of each PIN.
// PIN = -1 if character is not a decimal digit.
SetLength( count, L);
for j := 0 to L - 1 do count[L] := 0;
for j := 1 to L - n + 1 do begin
pin := SysUtils.StrToIntDef( Copy( deB, j, n), -1);
if pin >= 0 then inc( count[pin]);
end;
for j := 1 to n - 1 do begin
pin := SysUtils.StrToIntDef( Copy( wrap, j, n), -1);
if pin >= 0 then inc( count[pin]);
end;
// Check that all counts are 1
nrErrors := 0;
for j := 0 to L - 1 do begin
if count[j] <> 1 then begin
inc( nrErrors);
WriteLn( SysUtils.Format( ' PIN %d has count %d', [j, count[j]]));
end;
end;
WriteLn( SysUtils.Format( ' Number of errors = %d', [nrErrors]));
end;
// Main routine
var
deB, rev : string;
L, j : integer;
begin
deB := deBruijn( 4, '0123456789');
// deB := deBruijn( 4, '7368290514'); // any permutation would do
L := Length( deB);
WriteLn( SysUtils.Format( 'Length of de Bruijn sequence = %d', [L]));
if L >= 260 then begin
WriteLn;
WriteLn( 'First and last 130 characters are:');
WriteLn( Copy( deB, 1, 65));
WriteLn( Copy( deb, 66, 65));
WriteLn( '...');
WriteLn( Copy( deB, L - 129, 65));
WriteLn( Copy( deB, L - 64, 65));
end;
WriteLn;
WriteLn( 'Checking de Bruijn sequence:');
CheckDecimal( 4, deB);
// Check reversed sequence
SetLength( rev, L);
for j := 1 to L do rev[j] := deB[L + 1 - j];
WriteLn( 'Checking reversed sequence:');
CheckDecimal( 4, rev);
// Check sequence with '.' instad of decimal digit
if L >= 4444 then begin
deB[4444] := '.';
WriteLn( 'Checking vandalized sequence:');
CheckDecimal( 4, deB);
end;
end.
</syntaxhighlight>
{{out}}
<pre>
Length of de Bruijn sequence = 10000
First and last 130 characters are:
00001000200030004000500060007000800090011001200130014001500160017
00180019002100220023002400250026002700280029003100320033003400350
...
89768986899696977697869796987698869896997699869997777877797788778
97798779978787978887889789878997979887989799879998888988998989999
Checking de Bruijn sequence:
Number of errors = 0
Checking reversed sequence:
Number of errors = 0
Checking vandalized sequence:
PIN 1459 has count 0
PIN 4591 has count 0
PIN 5814 has count 0
PIN 8145 has count 0
Number of errors = 4
</pre>
=={{header|Perl}}==
{{trans|Raku}}
<
use warnings;
use feature 'say';
Line 1,893 ⟶ 2,765:
substr $seq, 4443, 1, 5;
say "Incorrect 4 digit PINs in the revised sequence:";
check $seq;</
{{out}}
<pre>de Bruijn sequence length: 10003
Line 1,919 ⟶ 2,791:
{{trans|zkl}}
{{trans|Go}}
<!--<
<span style="color: #004080;">string</span> <span style="color: #000000;">deBruijn</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">99</span> <span style="color: #008080;">do</span>
Line 1,971 ⟶ 2,843:
<span style="color: #000000;">deBruijn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">4444</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'.'</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Re-running checks: %s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">check</span><span style="color: #0000FF;">(</span><span style="color: #000000;">deBruijn</span><span style="color: #0000FF;">))</span>
<!--</
{{out}}
<pre>
Line 1,993 ⟶ 2,865:
=={{header|Python}}==
<
# from https://en.wikipedia.org/wiki/De_Bruijn_sequence
Line 2,085 ⟶ 2,957:
print("Validating the overlaid deBruijn sequence:")
validate(dboverlaid)
</syntaxhighlight>
{{out}}
<pre>
Line 2,112 ⟶ 2,984:
{{trans|Go}}
<
(define (de-bruijn k n)
Line 2,157 ⟶ 3,029:
(validate "" seq)
(validate "reversed " (reverse seq))
(validate "overlaid " (list-update seq 4443 add1))</
{{out}}
Line 2,188 ⟶ 3,060:
Deviates very slightly from the task spec. Generates a randomized de Bruijn sequence and replaces the 4444th digit with a the digit plus 1 mod 10 rather than a '.', mostly so it can demonstrate detection of extra PINs as well as missing ones.
<syntaxhighlight lang="raku"
my $seq;
Line 2,229 ⟶ 3,101:
put "Incorrect 4 digit PINs in the revised sequence:";
$seq.substr-rw(4443,1) = $digit;
check $seq;</
{{out|Sample output}}
<pre>de Bruijn sequence length: 10003
Line 2,255 ⟶ 3,127:
The de Bruijn sequence generated by these REXX programs are identical to the sequence shown on the ''discussion'' page (1<sup>st</sup> topic).
=== hard-coded node to be removed ===
<
$= /*initialize the de Bruijn sequence. */
#=10; lastNode= (#-2)(#-2)(#-1)(#-2) /*this number is formed when this # ···*/
Line 2,302 ⟶ 3,174:
if e==0 then e= 'No' /*Gooder English (sic) the error count.*/
say _ e 'errors found.' /*display the number of errors found. */
return</
{{out|output}}
<pre>
Line 2,331 ⟶ 3,203:
This method slightly bloats the program and slows execution.
<
$= /*initialize the de Bruijn sequence. */
do j=0 for 10; $= $ j; jj= j || j /*compose the left half of the numbers.*/
Line 2,378 ⟶ 3,250:
if e==0 then e= 'No' /*Gooder English (sic) the error count.*/
say _ e 'errors found.' /*display the number of errors found. */
return</
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br>
=={{header|Ruby}}==
{{trans|D}}
<
alphabet = "0123456789"
@a = Array.new(k * n, 0)
Line 2,455 ⟶ 3,327:
db[4443] = '.'
print "Validating the overlaid de Bruijn sequence:\n"
validate(db)</
{{out}}
<pre>The length of the de Bruijn sequence is 10003
Line 2,472 ⟶ 3,344:
PIN number 5814 missing
PIN number 8145 missing</pre>
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="Scala">
import scala.collection.mutable.ListBuffer
object DeBruijn {
def deBruijn(k: Int, n: Int): String = {
val a = Array.fill[Byte](k * n)(0)
val seq = new ListBuffer[Byte]()
def db(t: Int, p: Int): Unit = {
if (t > n) {
if (n % p == 0) {
seq ++= a.slice(1, p + 1)
}
} else {
a(t) = a(t - p)
db(t + 1, p)
for (j <- (a(t - p) + 1).until(k)) {
a(t) = j.toByte
db(t + 1, t)
}
}
}
db(1, 1)
val sb = new StringBuilder
seq.foreach(i => sb.append("0123456789".charAt(i)))
sb.append(sb.subSequence(0, n - 1)).toString
}
private def allDigits(s: String): Boolean = s.forall(_.isDigit)
private def validate(db: String): Unit = {
val found = Array.fill(10000)(0)
val errs = ListBuffer[String]()
for (i <- 0 until db.length - 3) {
val s = db.substring(i, i + 4)
if (allDigits(s)) {
val n = s.toInt
found(n) += 1
}
}
for (i <- found.indices) {
if (found(i) == 0) errs += s" PIN number $i is missing"
else if (found(i) > 1) errs += s" PIN number $i occurs ${found(i)} times"
}
if (errs.isEmpty) println(" No errors found")
else {
val pl = if (errs.size == 1) "" else "s"
println(s" ${errs.size} error$pl found:")
errs.foreach(println)
}
}
def main(args: Array[String]): Unit = {
val db = deBruijn(10, 4)
println(s"The length of the de Bruijn sequence is ${db.length}\n")
println(s"The first 130 digits of the de Bruijn sequence are: ${db.take(130)}\n")
println(s"The last 130 digits of the de Bruijn sequence are: ${db.takeRight(130)}\n")
println("Validating the de Bruijn sequence:")
validate(db)
println()
println("Validating the reversed de Bruijn sequence:")
validate(db.reverse)
val overlaidDb = db.updated(4443, '.')
println()
println("Validating the overlaid de Bruijn sequence:")
validate(overlaidDb)
}
}
</syntaxhighlight>
{{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 de Bruijn sequence:
No errors found
Validating the reversed de Bruijn sequence:
No errors found
Validating the overlaid de Bruijn sequence:
4 errors found:
PIN number 1459 is missing
PIN number 4591 is missing
PIN number 5814 is missing
PIN number 8145 is missing
</pre>
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Module Module1
Line 2,578 ⟶ 3,555:
End Sub
End Module</
{{out}}
<pre>The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350
Line 2,601 ⟶ 3,578:
{{libheader|Wren-fmt}}
{{libheader|Wren-str}}
<
import "./str" for Str
var deBruijn = ""
Line 2,659 ⟶ 3,636:
System.print("\n4,444th digit in the sequence: '%(deBruijn[4443])' (setting it to '.')")
deBruijn = deBruijn[0..4442] + "." + deBruijn[4444..-1]
System.print("Re-running checks: %(check.call(deBruijn))")</
{{out}}
Line 2,684 ⟶ 3,661:
=={{header|zkl}}==
{{trans|Raku}}
<
foreach n in (100){
a,a01,a11 := "%02d".fmt(n), a[0,1], a[1,1];
Line 2,694 ⟶ 3,671:
}
}
dbSeq.append("000");</
<
println("de Bruijn sequence length: ",dbSeq.len());
Line 2,711 ⟶ 3,688:
println("\n4444th digit in the sequence: ", seqText[4443]);
dbSeq[4443]=".";
println("Setting the 4444th digit and reruning checks: ",chk(dbSeq.text).concat(" "));</
{{out}}
<pre>
| |||