De Bruijn sequences: Difference between revisions
→{{header|Go}}
Line 184:
}
}
}</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 4591 missing
PIN number 5814 missing
PIN number 8145 missing</pre>
=={{header|D}}==
{{trans|Kotlin}}
<lang d>import std.array;
import std.conv;
import std.format;
import std.range;
import std.stdio;
immutable DIGITS = "0123456789";
string deBruijn(int k, int n) {
auto alphabet = DIGITS[0..k];
byte[] a;
a.length = k * n;
byte[] seq;
void db(int t, int p) {
if (t > n) {
if (n % p == 0) {
auto temp = a[1..p + 1];
seq ~= temp;
}
} else {
a[t] = a[t - p];
db(t + 1, p);
auto j = a[t - p] + 1;
while (j < k) {
a[t] = cast(byte)(j & 0xFF);
db(t + 1, t);
j++;
}
}
}
db(1, 1);
string buf;
foreach (i; seq) {
buf ~= alphabet[i];
}
return buf ~ buf[0 .. n - 1];
}
bool allDigits(string s) {
foreach (c; s) {
if (c < '0' || '9' < c) {
return false;
}
}
return true;
}
void validate(string db) {
auto le = db.length;
int[10_000] found;
string[] errs;
// Check all strings of 4 consecutive digits within 'db'
// to see if all 10,000 combinations occur without duplication.
foreach (i; 0 .. le - 3) {
auto s = db[i .. i + 4];
if (allDigits(s)) {
auto n = s.to!int;
found[n]++;
}
}
foreach (i; 0 .. 10_000) {
if (found[i] == 0) {
errs ~= format(" PIN number %04d missing", i);
} else if (found[i] > 1) {
errs ~= format(" PIN number %04d occurs %d times", i, found[i]);
}
}
if (errs.empty) {
writeln(" No errors found");
} else {
auto pl = (errs.length == 1) ? "" : "s";
writeln(" ", errs.length, " error", pl, " found:");
writefln("%-(%s\n%)", errs);
}
}
void main() {
auto db = deBruijn(10, 4);
writeln("The length of the de Bruijn sequence is ", db.length);
writeln("\nThe first 130 digits of the de Bruijn sequence are: ", db[0 .. 130]);
writeln("\nThe last 130 digits of the de Bruijn sequence are: ", db[$ - 130 .. $]);
writeln("\nValidating the deBruijn sequence:");
validate(db);
writeln("\nValidating the reversed deBruijn sequence:");
validate(db.retro.to!string);
auto by = db.dup;
by[4443] = '.';
db = by.idup;
writeln("\nValidating the overlaid deBruijn sequence:");
validate(db);
}</lang>
{{out}}
| |||