De Bruijn sequences
You are encouraged to solve this task according to the task description, using any language you may know.
The sequences are named after the Dutch mathematician Nicolaas Govert de Bruijn.
A note on Dutch capitalization: Nicolaas' last name is de Bruijn, the de isn't normally capitalized
unless it's the first word in a sentence. Rosetta Code (more or less by default or by fiat) requires the first word in the task name to be
capitalized.
In combinatorial mathematics, a de Bruijn sequence of order n on
a size-k alphabet (computer science) A is a cyclic sequence in which every
possible length-n string (computer science, formal theory) on A occurs
exactly once as a contiguous substring.
Such a sequence is denoted by B(k, n) and has
length kn, which is also the number of distinct substrings of
length n on A;
de Bruijn sequences are therefore optimally short.
There are:
(k!)k(n-1) ÷ kn
distinct de Bruijn sequences B(k, n).
- 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 PIN-like code lock that does not have an "enter" key and accepts the last n digits entered.
Note: automated teller machines (ATMs) used to work like
this, but their software has been updated to not allow a brute-force attack.
- Example
A digital door lock with a 4-digit code would have B (10, 4) solutions, with a length of 10,000 (digits).
Therefore, only at most 10,000 + 3 (as the solutions are cyclic or wrap-around) presses are needed to open the lock.
Trying all 4-digit codes separately would require 4 × 10,000 or 40,000 presses.
- Task requirements
-
- Generate a de Bruijn sequence for a 4-digit (decimal) PIN code.
- Show the length of the generated de Bruijn sequence.
- (There are many possible de Bruijn sequences that solve this task, one solution is shown on the discussion page).
- Show the first and last 130 digits of the de Bruijn sequence.
- Verify that all four-digit (decimal) 1,000 PIN codes are contained within the de Bruijn sequence.
- 0000, 0001, 0002, 0003, ... 9996, 9997, 9998, 9999 (note the leading zeros).
- Reverse the de Bruijn sequence.
- Again, perform the (above) verification test.
- Replace the 4,444th digit with a period (.) in the original de Bruijn sequence.
- Perform the verification test (again). There should be several PIN codes missing.
(The last requirement is to ensure that the verification tests performs correctly. The verification processes should list
any and all missing PIN codes.)
Show all output here, on this page.
- References
-
- Wikipedia entry: de Bruijn sequence.
- MathWorld entry: de Bruijn sequence.
- An OEIS entry: A166315 lexicographically earliest binary de Bruijn sequences, B(2,n) --- Not B(10,4), but possibly relevant.
C#
<lang csharp>using System; using System.Collections.Generic; using System.Text;
namespace DeBruijn {
class Program {
const string digits = "0123456789";
static string DeBruijn(int k, int n) {
var alphabet = digits.Substring(0, k);
var a = new byte[k * n];
var seq = new List<byte>();
void db(int t, int p) {
if (t > n) {
if (n % p == 0) {
seq.AddRange(new ArraySegment<byte>(a, 1, p));
}
} else {
a[t] = a[t - p];
db(t + 1, p);
var j = a[t - p] + 1;
while (j < k) {
a[t] = (byte)j;
db(t + 1, t);
j++;
}
}
}
db(1, 1);
var buf = new StringBuilder();
foreach (var i in seq) {
buf.Append(alphabet[i]);
}
var b = buf.ToString();
return b + b.Substring(0, n - 1);
}
static bool AllDigits(string s) {
foreach (var c in s) {
if (c < '0' || '9' < c) {
return false;
}
}
return true;
}
static void Validate(string db) {
var le = db.Length;
var found = new int[10_000];
var errs = new List<string>();
// Check all strings of 4 consecutive digits within 'db'
// to see if all 10,000 combinations occur without duplication.
for (int i = 0; i < le - 3; i++) {
var s = db.Substring(i, 4);
if (AllDigits(s)) {
int.TryParse(s, out int n);
found[n]++;
}
}
for (int i = 0; i < 10_000; i++) {
if (found[i] == 0) {
errs.Add(string.Format(" PIN number {0,4} missing", i));
} else if (found[i] > 1) {
errs.Add(string.Format(" PIN number {0,4} occurs {1} times", i, found[i]));
}
}
var lerr = errs.Count;
if (lerr == 0) {
Console.WriteLine(" No errors found");
} else {
var pl = lerr == 1 ? "" : "s";
Console.WriteLine(" {0} error{1} found:", lerr, pl);
errs.ForEach(Console.WriteLine);
}
}
static string Reverse(string s) {
char[] arr = s.ToCharArray();
Array.Reverse(arr);
return new string(arr);
}
static void Main() {
var db = DeBruijn(10, 4);
var le = db.Length;
Console.WriteLine("The length of the de Bruijn sequence is {0}", le);
Console.WriteLine("\nThe first 130 digits of the de Bruijn sequence are: {0}", db.Substring(0, 130));
Console.WriteLine("\nThe last 130 digits of the de Bruijn sequence are: {0}", db.Substring(le - 130, 130));
Console.WriteLine("\nValidating the deBruijn sequence:");
Validate(db);
Console.WriteLine("\nValidating the reversed deBruijn sequence:");
Validate(Reverse(db));
var bytes = db.ToCharArray();
bytes[4443] = '.';
db = new string(bytes);
Console.WriteLine("\nValidating the overlaid deBruijn sequence:");
Validate(db);
}
}
}</lang>
- Output:
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
C++
<lang cpp>#include <algorithm>
- include <functional>
- include <iostream>
- include <iterator>
- include <string>
- include <sstream>
- include <vector>
typedef unsigned char byte;
std::string deBruijn(int k, int n) {
std::vector<byte> a(k * n, 0); std::vector<byte> seq;
std::function<void(int, int)> db;
db = [&](int t, int p) {
if (t > n) {
if (n % p == 0) {
for (int i = 1; i < p + 1; i++) {
seq.push_back(a[i]);
}
}
} else {
a[t] = a[t - p];
db(t + 1, p);
auto j = a[t - p] + 1;
while (j < k) {
a[t] = j & 0xFF;
db(t + 1, t);
j++;
}
}
};
db(1, 1);
std::string buf;
for (auto i : seq) {
buf.push_back('0' + i);
}
return buf + buf.substr(0, n - 1);
}
bool allDigits(std::string s) {
for (auto c : s) {
if (c < '0' || '9' < c) {
return false;
}
}
return true;
}
void validate(std::string db) {
auto le = db.size(); std::vector<int> found(10000, 0); std::vector<std::string> errs;
// Check all strings of 4 consecutive digits within 'db'
// to see if all 10,000 combinations occur without duplication.
for (size_t i = 0; i < le - 3; i++) {
auto s = db.substr(i, 4);
if (allDigits(s)) {
auto n = stoi(s);
found[n]++;
}
}
for (int i = 0; i < 10000; i++) {
if (found[i] == 0) {
std::stringstream ss;
ss << " PIN number " << i << " missing";
errs.push_back(ss.str());
} else if (found[i] > 1) {
std::stringstream ss;
ss << " PIN number " << i << " occurs " << found[i] << " times";
errs.push_back(ss.str());
}
}
if (errs.empty()) {
std::cout << " No errors found\n";
} else {
auto pl = (errs.size() == 1) ? "" : "s";
std::cout << " " << errs.size() << " error" << pl << " found:\n";
for (auto e : errs) {
std::cout << e << '\n';
}
}
}
int main() {
std::ostream_iterator<byte> oi(std::cout, ""); auto db = deBruijn(10, 4);
std::cout << "The length of the de Bruijn sequence is " << db.size() << "\n\n"; std::cout << "The first 130 digits of the de Bruijn sequence are: "; std::copy_n(db.cbegin(), 130, oi); std::cout << "\n\nThe last 130 digits of the de Bruijn sequence are: "; std::copy(db.cbegin() + (db.size() - 130), db.cend(), oi); std::cout << "\n";
std::cout << "\nValidating the de Bruijn sequence:\n"; validate(db);
std::cout << "\nValidating the reversed de Bruijn sequence:\n"; auto rdb = db; std::reverse(rdb.begin(), rdb.end()); validate(rdb);
auto by = db; by[4443] = '.'; std::cout << "\nValidating the overlaid de Bruijn sequence:\n"; validate(by);
return 0;
}</lang>
- Output:
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 missing
PIN number 4591 missing
PIN number 5814 missing
PIN number 8145 missing
D
<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>
- Output:
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
Go
<lang go>package main
import (
"bytes" "fmt" "strconv" "strings"
)
const digits = "0123456789"
func deBruijn(k, n int) string {
alphabet := digits[0:k]
a := make([]byte, k*n)
var seq []byte
var db func(int, int) // recursive closure
db = func(t, p int) {
if t > n {
if n%p == 0 {
seq = append(seq, a[1:p+1]...)
}
} else {
a[t] = a[t-p]
db(t+1, p)
for j := int(a[t-p] + 1); j < k; j++ {
a[t] = byte(j)
db(t+1, t)
}
}
}
db(1, 1)
var buf bytes.Buffer
for _, i := range seq {
buf.WriteByte(alphabet[i])
}
b := buf.String()
return b + b[0:n-1] // as cyclic append first (n-1) digits
}
func allDigits(s string) bool {
for _, b := range s {
if b < '0' || b > '9' {
return false
}
}
return true
}
func validate(db string) {
le := len(db)
found := make([]int, 10000)
var errs []string
// Check all strings of 4 consecutive digits within 'db'
// to see if all 10,000 combinations occur without duplication.
for i := 0; i < le-3; i++ {
s := db[i : i+4]
if allDigits(s) {
n, _ := strconv.Atoi(s)
found[n]++
}
}
for i := 0; i < 10000; i++ {
if found[i] == 0 {
errs = append(errs, fmt.Sprintf(" PIN number %04d missing", i))
} else if found[i] > 1 {
errs = append(errs, fmt.Sprintf(" PIN number %04d occurs %d times", i, found[i]))
}
}
lerr := len(errs)
if lerr == 0 {
fmt.Println(" No errors found")
} else {
pl := "s"
if lerr == 1 {
pl = ""
}
fmt.Printf(" %d error%s found:\n", lerr, pl)
fmt.Println(strings.Join(errs, "\n"))
}
}
func reverse(s string) string {
bytes := []byte(s)
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
bytes[i], bytes[j] = bytes[j], bytes[i]
}
return string(bytes)
}
func main() {
db := deBruijn(10, 4)
le := len(db)
fmt.Println("The length of the de Bruijn sequence is", le)
fmt.Println("\nThe first 130 digits of the de Bruijn sequence are:")
fmt.Println(db[0:130])
fmt.Println("\nThe last 130 digits of the de Bruijn sequence are:")
fmt.Println(db[le-130:])
fmt.Println("\nValidating the de Bruijn sequence:")
validate(db)
fmt.Println("\nValidating the reversed de Bruijn sequence:")
dbr := reverse(db)
validate(dbr)
bytes := []byte(db)
bytes[4443] = '.'
db = string(bytes)
fmt.Println("\nValidating the overlaid de Bruijn sequence:")
validate(db)
}</lang>
- Output:
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 missing
PIN number 4591 missing
PIN number 5814 missing
PIN number 8145 missing
J
definitions. The C. verb computes the cycles. <lang J>NB. implement inverse Burrows—Wheeler transform sequence method
repeat_alphabet=: [: , [: i.&> (^ <:) # [ assert 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -: 2 repeat_alphabet 4
de_bruijn=: ({~ ([: ; [: C. /:^:2))@:repeat_alphabet NB. K de_bruijn N
pins=: #&10 #: [: i. 10&^ NB. pins y generates all y digit PINs groups=: [ ]\ ] , ({.~ <:)~ NB. length x infixes of sequence y cyclically extended by x-1 verify_PINs=: (/:~@:groups -: pins@:[) NB. LENGTH verify_PINs SEQUENCE </lang>Task<lang J> NB. A is the sequence
A=: 10 de_bruijn 4
NB. tally A #A
10000
NB. literally the first and final 130 digits
Num_j_ {~ 130 ({. ,: ({.~ -)~) A
0000101001101111000210020102110202001210120112111202121200221022012211220222122220003100320030103110321030203120322030300131013201 9469956996699769986990799179927993799479957996799779987990899189928993899489958996899789988990999199929993999499959996999799989999
NB. verifications. seriously? 4 verify_PINs A
1
4 (verify_PINs |.) A
1
4 verify_PINs (a.i.'.') (<: 4444)} A
0 </lang>
Java
<lang java>import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.function.BiConsumer;
public class DeBruijn {
public interface Recursable<T, U> {
void apply(T t, U u, Recursable<T, U> r);
}
public static <T, U> BiConsumer<T, U> recurse(Recursable<T, U> f) {
return (t, u) -> f.apply(t, u, f);
}
private static String deBruijn(int k, int n) {
byte[] a = new byte[k * n];
Arrays.fill(a, (byte) 0);
List<Byte> seq = new ArrayList<>();
BiConsumer<Integer, Integer> db = recurse((t, p, f) -> {
if (t > n) {
if (n % p == 0) {
for (int i = 1; i < p + 1; ++i) {
seq.add(a[i]);
}
}
} else {
a[t] = a[t - p];
f.apply(t + 1, p, f);
int j = a[t - p] + 1;
while (j < k) {
a[t] = (byte) (j & 0xFF);
f.apply(t + 1, t, f);
j++;
}
}
});
db.accept(1, 1);
StringBuilder sb = new StringBuilder();
for (Byte i : seq) {
sb.append("0123456789".charAt(i));
}
sb.append(sb.subSequence(0, n - 1));
return sb.toString();
}
private static boolean allDigits(String s) {
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (!Character.isDigit(c)) {
return false;
}
}
return true;
}
private static void validate(String db) {
int le = db.length();
int[] found = new int[10_000];
Arrays.fill(found, 0);
List<String> errs = new ArrayList<>();
// Check all strings of 4 consecutive digits within 'db'
// to see if all 10,000 combinations occur without duplication.
for (int i = 0; i < le - 3; ++i) {
String s = db.substring(i, i + 4);
if (allDigits(s)) {
int n = Integer.parseInt(s);
found[n]++;
}
}
for (int i = 0; i < 10_000; ++i) {
if (found[i] == 0) {
errs.add(String.format(" PIN number %d is missing", i));
} else if (found[i] > 1) {
errs.add(String.format(" PIN number %d occurs %d times", i, found[i]));
}
}
if (errs.isEmpty()) {
System.out.println(" No errors found");
} else {
String pl = (errs.size() == 1) ? "" : "s";
System.out.printf(" %d error%s found:\n", errs.size(), pl);
errs.forEach(System.out::println);
}
}
public static void main(String[] args) {
String db = deBruijn(10, 4);
System.out.printf("The length of the de Bruijn sequence is %d\n\n", db.length());
System.out.printf("The first 130 digits of the de Bruijn sequence are: %s\n\n", db.substring(0, 130));
System.out.printf("The last 130 digits of the de Bruijn sequence are: %s\n\n", db.substring(db.length() - 130));
System.out.println("Validating the de Bruijn sequence:");
validate(db);
StringBuilder sb = new StringBuilder(db);
String rdb = sb.reverse().toString();
System.out.println();
System.out.println("Validating the de Bruijn sequence:");
validate(rdb);
sb = new StringBuilder(db);
sb.setCharAt(4443, '.');
System.out.println();
System.out.println("Validating the overlaid de Bruijn sequence:");
validate(sb.toString());
}
}</lang>
- Output:
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 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
Julia
<lang julia>function debruijn(k::Integer, n::Integer)
alphabet = b"0123456789abcdefghijklmnopqrstuvwxyz"[1:k] a = zeros(UInt8, k * n) seq = UInt8[]
function db(t, p)
if t > n
if n % p == 0
append!(seq, a[2:p+1])
end
else
a[t + 1] = a[t - p + 1]
db(t + 1, p)
for j in a[t-p+1]+1:k-1
a[t + 1] = j
db(t + 1, t)
end
end
end
db(1, 1) return String([alphabet[i + 1] for i in vcat(seq, seq[1:n-1])])
end
function verifyallPIN(str, k, n, deltaposition=0)
if deltaposition != 0
str = str[1:deltaposition-1] * "." * str[deltaposition+1:end]
end
result = true
for i in 1:k^n-1
pin = string(i, pad=n)
if !occursin(pin, str)
println("PIN $pin does not occur in the sequence.")
result = false
end
end
println("The sequence does ", result ? "" : "not ", "contain all PINs.")
end
const s = debruijn(10, 4) println("The length of the sequence is $(length(s)). The first 130 digits are:\n",
s[1:130], "\nand the last 130 digits are:\n", s[end-130:end])
print("Testing sequence: "), verifyallPIN(s, 10, 4) print("Testing the reversed sequence: "), verifyallPIN(reverse(s), 10, 4) println("\nAfter replacing 4444th digit with \'.\':"), verifyallPIN(s, 10, 4, 4444)
</lang>
- Output:
The length of the sequence is 10003. The first 130 digits are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 and the last 130 digits are: 76898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 Testing sequence: The sequence does contain all PINs. Testing the reversed sequence: The sequence does contain all PINs. After replacing 4444th digit with '.': PIN 1459 does not occur in the sequence. PIN 4591 does not occur in the sequence. PIN 5814 does not occur in the sequence. PIN 8145 does not occur in the sequence. The sequence does not contain all PINs.
Kotlin
<lang scala>const val digits = "0123456789"
fun deBruijn(k: Int, n: Int): String {
val alphabet = digits.substring(0, k)
val a = ByteArray(k * n)
val seq = mutableListOf<Byte>()
fun db(t: Int, p: Int) {
if (t > n) {
if (n % p == 0) {
seq.addAll(a.sliceArray(1..p).asList())
}
} else {
a[t] = a[t - p]
db(t + 1, p)
var j = a[t - p] + 1
while (j < k) {
a[t] = j.toByte()
db(t + 1, t)
j++
}
}
}
db(1, 1)
val buf = StringBuilder()
for (i in seq) {
buf.append(alphabet[i.toInt()])
}
val b = buf.toString()
return b + b.subSequence(0, n - 1)
}
fun allDigits(s: String): Boolean {
for (c in s) {
if (c < '0' || '9' < c) {
return false
}
}
return true
}
fun validate(db: String) {
val le = db.length
val found = MutableList(10_000) { 0 }
val errs = mutableListOf<String>()
// Check all strings of 4 consecutive digits within 'db'
// to see if all 10,000 combinations occur without duplication.
for (i in 0 until le - 3) {
val s = db.substring(i, i + 4)
if (allDigits(s)) {
val n = s.toInt()
found[n]++
}
}
for (i in 0 until 10_000) {
if (found[i] == 0) {
errs.add(" PIN number %04d missing".format(i))
} else if (found[i] > 1) {
errs.add(" PIN number %04d occurs %d times".format(i, found[i]))
}
}
val lerr = errs.size
if (lerr == 0) {
println(" No errors found")
} else {
val pl = if (lerr == 1) {
""
} else {
"s"
}
println(" $lerr error$pl found:")
println(errs.joinToString("\n"))
}
}
fun main() {
var db = deBruijn(10, 4) val le = db.length
println("The length of the de Bruijn sequence is $le")
println("\nThe first 130 digits of the de Bruijn sequence are: ${db.subSequence(0, 130)}")
println("\nThe last 130 digits of the de Bruijn sequence are: ${db.subSequence(le - 130, le)}")
println("\nValidating the deBruijn sequence:")
validate(db)
println("\nValidating the reversed deBruijn sequence:")
validate(db.reversed())
val bytes = db.toCharArray()
bytes[4443] = '.'
db = String(bytes)
println("\nValidating the overlaid deBruijn sequence:")
validate(db)
}</lang>
- Output:
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
Perl
<lang perl>use strict; use warnings; use feature 'say';
my $seq; for my $x (0..99) {
my $a = sprintf '%02d', $x;
next if substr($a,1,1) < substr($a,0,1);
$seq .= (substr($a,0,1) == substr($a,1,1)) ? substr($a,0,1) : $a;
for ($a+1 .. 99) {
next if substr(sprintf('%02d', $_), 1,1) <= substr($a,0,1);
$seq .= sprintf "%s%02d", $a, $_;
}
} $seq .= '000';
sub check {
my($seq) = @_;
my %chk;
for (0.. -1 + length $seq) { $chk{substr($seq, $_, 4)}++ }
say 'Missing: ' . join ' ', grep { ! $chk{ sprintf('%04d',$_) } } 0..9999;
say 'Extra: ' . join ' ', sort grep { $chk{$_} > 1 } keys %chk;
}
my $n = 130; say "de Bruijn sequence length: " . length $seq; say "\nFirst $n characters:\n" . substr($seq, 0, $n ); say "\nLast $n characters:\n" . substr($seq, -$n, $n); say "\nIncorrect 4 digit PINs in this sequence:"; check $seq;
say "\nIncorrect 4 digit PINs in the reversed sequence:"; check(reverse $seq);
say "\nReplacing the 4444th digit, '@{[substr($seq,4443,1)]}', with '5'"; substr $seq, 4443, 1, 5; say "Incorrect 4 digit PINs in the revised sequence:"; check $seq;</lang>
- Output:
de Bruijn sequence length: 10003 First 130 characters: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 Last 130 characters: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 Incorrect 4 digit PINs in this sequence: Missing: Extra: Incorrect 4 digit PINs in the reversed sequence: Missing: Extra: Replacing the 4444th digit, '4', with '5' Incorrect 4 digit PINs in the revised sequence: Missing: 1459 4591 5814 8145 Extra: 1559 5591 5815 8155
Phix
<lang Phix>string deBruijn = "" for n=0 to 99 do
string a = sprintf("%02d",n)
integer {a1,a2} = a
if a2>=a1 then
deBruijn &= iff(a1=a2?a1:a)
for m=n+1 to 99 do
string ms = sprintf("%02d",m)
if ms[2]>a1 then
deBruijn &= a&ms
end if
end for
end if
end for deBruijn &= "000" printf(1,"de Bruijn sequence length: %d\n\n",length(deBruijn)) printf(1,"First 130 characters:\n%s\n\n",deBruijn[1..130]) printf(1,"Last 130 characters:\n%s\n\n",deBruijn[-130..-1])
function check(string text)
sequence res = {}
sequence found = repeat(0,10000)
integer k
for i=1 to length(text)-3 do
k = to_integer(text[i..i+3],-1)+1
if k!=0 then found[k] += 1 end if
end for
for i=1 to 10000 do
k = found[i]
if k!=1 then
string e = sprintf("Pin number %04d ",i-1)
e &= iff(k=0?"missing":sprintf("occurs %d times",k))
res = append(res,e)
end if
end for
k = length(res)
if k=0 then
res = "No errors found"
else
string s = iff(k=1?"":"s")
res = sprintf("%d error%s found:\n ",{k,s})&join(res,"\n ")
end if
return res
end function
printf(1,"Missing 4 digit PINs in this sequence: %s\n", check(deBruijn)) printf(1,"Missing 4 digit PINs in the reversed sequence: %s\n",check(reverse(deBruijn))) printf(1,"4444th digit in the sequence: %c (setting it to .)\n", deBruijn[4444]) deBruijn[4444] = '.' printf(1,"Re-running checks: %s\n",check(deBruijn))</lang>
- Output:
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 4444th 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
Python
<lang python>
def de_bruijn(k, n):
"""
de Bruijn sequence for alphabet k
and subsequences of length n.
"""
try:
# let's see if k can be cast to an integer;
# if so, make our alphabet a list
_ = int(k)
alphabet = list(map(str, range(k)))
except (ValueError, TypeError):
alphabet = k
k = len(k)
a = [0] * k * n sequence = []
def db(t, p):
if t > n:
if n % p == 0:
sequence.extend(a[1:p + 1])
else:
a[t] = a[t - p]
db(t + 1, p)
for j in range(a[t - p] + 1, k):
a[t] = j
db(t + 1, t)
db(1, 1)
return "".join(alphabet[i] for i in sequence)
def validate(db):
"""
Check that all 10,000 combinations of 0-9 are present in
De Bruijn string db.
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
"""
dbwithwrap = db+db[0:3]
digits = '0123456789'
errorstrings = []
for d1 in digits:
for d2 in digits:
for d3 in digits:
for d4 in digits:
teststring = d1+d2+d3+d4
if teststring not in dbwithwrap:
errorstrings.append(teststring)
if len(errorstrings) > 0:
print(" "+str(len(errorstrings))+" errors found:")
for e in errorstrings:
print(" PIN number "+e+" missing")
else:
print(" No errors found")
db = de_bruijn(10, 4)
print(" ") print("The length of the de Bruijn sequence is ", str(len(db))) print(" ") print("The first 130 digits of the de Bruijn sequence are: "+db[0:130]) print(" ") print("The last 130 digits of the de Bruijn sequence are: "+db[-130:]) print(" ") print("Validating the deBruijn sequence:") validate(db) dbreversed = db[::-1] print(" ") print("Validating the reversed deBruijn sequence:") validate(dbreversed) dboverlaid = db[0:4443]+'.'+db[4444:] print(" ") print("Validating the overlaid deBruijn sequence:") validate(dboverlaid) </lang>
- Output:
The length of the de Bruijn sequence is 10000 The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 The last 130 digits of the de Bruijn sequence are: 8976898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999 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
Racket
<lang racket>#lang racket
(define (de-bruijn k n)
(define a (make-vector (* k n) 0))
(define seq '())
(define (db t p)
(cond
[(> t n) (when (= (modulo n p) 0)
(set! seq (cons (call-with-values
(thunk (vector->values a 1 (add1 p)))
list)
seq)))]
[else (vector-set! a t (vector-ref a (- t p)))
(db (add1 t) p)
(for ([j (in-range (add1 (vector-ref a (- t p))) k)])
(vector-set! a t j)
(db (add1 t) t))]))
(db 1 1)
(define seq* (append* (reverse seq)))
(append seq* (take seq* (sub1 n))))
(define seq (de-bruijn 10 4)) (printf "The length of the de Bruijn sequence is ~a\n\n" (length seq)) (printf "The first 130 digits of the de Bruijn sequence are:\n~a\n\n"
(take seq 130))
(printf "The last 130 digits of the de Bruijn sequence are:\n~a\n\n"
(take-right seq 130))
(define (validate name seq)
(printf "Validating the ~ade Bruijn sequence:\n" name)
(define expected (for/set ([i (in-range 0 10000)]) i))
(define actual (for/set ([a (in-list seq)]
[b (in-list (rest seq))]
[c (in-list (rest (rest seq)))]
[d (in-list (rest (rest (rest seq))))])
(+ (* 1000 a) (* 100 b) (* 10 c) d)))
(define diff (set-subtract expected actual))
(cond
[(set-empty? diff) (printf " No errors found\n")]
[else (for ([n (in-set diff)])
(printf " ~a is missing\n" (~a n #:width 4 #:pad-string "0")))])
(newline))
(validate "" seq) (validate "reversed " (reverse seq)) (validate "overlaid " (list-update seq 4443 add1))</lang>
- Output:
The length of the de Bruijn sequence is 10003 The first 130 digits of the de Bruijn sequence are: (0 0 0 0 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5 0 0 0 6 0 0 0 7 0 0 0 8 0 0 0 9 0 0 1 1 0 0 1 2 0 0 1 3 0 0 1 4 0 0 1 5 0 0 1 6 0 0 1 7 0 0 1 8 0 0 1 9 0 0 2 1 0 0 2 2 0 0 2 3 0 0 2 4 0 0 2 5 0 0 2 6 0 0 2 7 0 0 2 8 0 0 2 9 0 0 3 1 0 0 3 2 0 0 3 3 0 0 3 4 0 0 3 5 0) The last 130 digits of the de Bruijn sequence are: (6 8 9 8 6 8 9 9 6 9 6 9 7 7 6 9 7 8 6 9 7 9 6 9 8 7 6 9 8 8 6 9 8 9 6 9 9 7 6 9 9 8 6 9 9 9 7 7 7 7 8 7 7 7 9 7 7 8 8 7 7 8 9 7 7 9 8 7 7 9 9 7 8 7 8 7 9 7 8 8 8 7 8 8 9 7 8 9 8 7 8 9 9 7 9 7 9 8 8 7 9 8 9 7 9 9 8 7 9 9 9 8 8 8 8 9 8 8 9 9 8 9 8 9 9 9 9 0 0 0) Validating the de Bruijn sequence: No errors found Validating the reversed de Bruijn sequence: No errors found Validating the overlaid de Bruijn sequence: 1459 is missing 4591 is missing 8145 is missing 5814 is missing
Raku
(formerly Perl 6)
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.
<lang perl6># Generate the sequence my $seq;
for ^100 {
my $a = .fmt: '%02d';
next if $a.substr(1,1) < $a.substr(0,1);
$seq ~= ($a.substr(0,1) == $a.substr(1,1)) ?? $a.substr(0,1) !! $a;
for +$a ^..^ 100 {
next if .fmt('%02d').substr(1,1) <= $a.substr(0,1);
$seq ~= sprintf "%s%02d", $a, $_ ;
}
}
$seq = $seq.comb.list.rotate((^10000).pick).join;
$seq ~= $seq.substr(0,3);
sub check ($seq) {
my %chk;
for ^($seq.chars) { %chk{$seq.substr( $_, 4 )}++ }
put 'Missing: ', (^9999).grep( { not %chk{ .fmt: '%04d' } } ).fmt: '%04d';
put 'Extra: ', %chk.grep( *.value > 1 )».key.sort.fmt: '%04d';
}
- The Task
put "de Bruijn sequence length: " ~ $seq.chars;
put "\nFirst 130 characters:\n" ~ $seq.substr( 0, 130 );
put "\nLast 130 characters:\n" ~ $seq.substr( * - 130 );
put "\nIncorrect 4 digit PINs in this sequence:"; check $seq;
put "\nIncorrect 4 digit PINs in the reversed sequence:"; check $seq.flip;
my $digit = $seq.substr(4443,1); put "\nReplacing the 4444th digit, ($digit) with { ($digit += 1) %= 10 }"; put "Incorrect 4 digit PINs in the revised sequence:"; $seq.substr-rw(4443,1) = $digit; check $seq;</lang>
- Sample output:
de Bruijn sequence length: 10003 First 130 characters: 4558455945654566456745684569457545764577457845794585458645874588458945954596459745984599464647464846494655465646574658465946654666 Last 130 characters: 5445644574458445944654466446744684469447544764477447844794485448644874488448944954496449744984499454546454745484549455545564557455 Incorrect 4 digit PINs in this sequence: Missing: Extra: Incorrect 4 digit PINs in the reversed sequence: Missing: Extra: Replacing the 4444th digit, (1) with 2 Incorrect 4 digit PINs in the revised sequence: Missing: 0961 1096 6109 9610 Extra: 0962 2096 6209 9620
REXX
The de Bruijn sequence generated by these REXX programs are identical to the sequence shown on the discussion page (1st topic).
hard-coded node to be removed
<lang rexx>/*REXX pgm calculates the de Bruijn sequence for all pin numbers (4 digit decimals). */ $= /*initialize the de Bruijn sequence. */
- =10; lastNode= (#-2)(#-2)(#-1)(#-2) /*this number is formed when this # ···*/
/* ··· is skipped near the cycle end. */
do j=0 for 10; $= $ || j; jj= j || j /*compose the left half of the numbers.*/
/* [↓] " right " " " " */
do k=jj+1 to 99; z= jj || right(k, 2, 0)
if z==lastNode then iterate /*the last node skipped.*/
if pos(z, $)\==0 then iterate /*# in sequence? Skip it*/
$= $ || z /* ◄─────────────────────────────────┐ */
end /*k*/ /*append a number to the sequence──◄─┘ */
do r= jj to (j || 9); b= right(r, 2, 0) /*compose the left half of the numbers.*/
if b==jj then iterate
$= $ || right(b, 2, 0) /* [↓] " right " " " " */
do k= b+1 to 99; z= right(b, 2, 0) || right(k, 2, 0)
if pos(z, $)\==0 then iterate /*# in sequence? Skip it*/
$= $ || z /* ◄─────────────────────────────────┐ */
end /*k*/ /*append a number to the sequence──◄─┘ */
end /*r*/
end /*j*/
@deB= 'de Bruijn sequence' /*literal used in some SAY instructions*/
$= $ || left($, 3) /*append 000*/ /*simulate "wrap-around" de Bruijn seq.*/
say 'length of the' @deB " is " length($) /*display the length of de Bruijn seq.*/
say; say 'first 130 digits of the' @deB":" /*display the title for the next line. */
say left($, 130) /*display 130 left-most digits of seq. */
say; say ' last 130 digits of the' @deB":" /*display the title for the next line. */
say right($, 130) /*display 130 right-most digits of seq.*/
say /*display a blank line. */ call val $ /*call the VAL sub for verification. */
@deB= 'reversed' @deB /*next, we'll check on a reversed seq.*/
$$= reverse($) /*do what a mirror does, reversify it.*/ call val $$ /*call the VAL sub for verification. */ $= overlay(., $, 4444) /*replace 4,444th digit with a period. */
@deB= 'overlaid' subword(@deB, 2) /* [↑] this'll cause a validation barf.*/
call val $ /*call the VAL sub for verification. */ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ val: parse arg $$$; e= 0; _= copies('─',8) /*count of errors (missing PINs) so far*/
say; say _ 'validating the' @deB"." /*display what's happening in the pgm. */
do pin=0 for 1e4; pin4= right(pin,4,0) /* [↓] maybe add leading zeros to pin.*/
if pos(pin4, $$$)\==0 then iterate /*Was number found? Just as expected. */
say 'PIN number ' pin " wasn't found in" @deb'.'
e= e + 1 /*bump the counter for number of errors*/
end /*pin*/ /* [↑] validate all 10,000 pin numbers*/
if e==0 then e= 'No' /*Gooder English (sic) the error count.*/
say _ e 'errors found.' /*display the number of errors found. */
return</lang>
- output:
length of the de Bruijn sequence is 10003 first 130 digits of the de Bruijn sequence: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 last 130 digits of the de Bruijn sequence: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 ──────── validating the de Bruijn sequence. ──────── No errors found. ──────── validating the reversed de Bruijn sequence. ──────── No errors found. ──────── validating the overlaid de Bruijn sequence. PIN number 1459 wasn't found in overlaid de Bruijn sequence. PIN number 4591 wasn't found in overlaid de Bruijn sequence. PIN number 5814 wasn't found in overlaid de Bruijn sequence. PIN number 8145 wasn't found in overlaid de Bruijn sequence. ──────── 4 errors found.
programmatically removing of a node
Programming note: instead of hardcoding the lastNode (that is elided from the sequence), the 5th to the last node could simply be deleted.
This method slightly bloats the program and slows execution. <lang rexx>/*REXX pgm calculates the de Bruijn sequence for all pin numbers (4 digit decimals). */ $= /*initialize the de Bruijn sequence. */
do j=0 for 10; $= $ j; jj= j || j /*compose the left half of the numbers.*/
$$= space($, 0) /* [↓] " right " " " " */
do k=jj+1 to 99; z= jj || right(k, 2, 0)
if pos(z, $$)\==0 then iterate /*# in sequence? Skip it*/
$= $ z /* ◄─────────────────────────────────┐ */
end /*k*/ /*append a number to the sequence──◄─┘ */
$$= space($, 0)
do r= jj to (j || 9); b= right(r, 2, 0) /*compose the left half of the numbers.*/
if b==jj then iterate
$= $ right(b, 2, 0) /* [↓] " right " " " " */
$$= space($, 0); do k= b+1 to 99; z= right(b, 2, 0) || right(k, 2, 0)
if pos(z, $$)\==0 then iterate /*# in sequence? Skip it*/
$= $ z /* ◄─────────────────────────────────┐ */
end /*k*/ /*append a number to the sequence──◄─┘ */
$$= space($, 0)
end /*r*/
end /*j*/
$= delword($, words($)-4, 1) /*delete 5th from the last word in $. */ $= space($, 0)
@deB= 'de Bruijn sequence' /*literal used in some SAY instructions*/
$= $ || left($, 3) /*append 000*/ /*simulate "wrap-around" de Bruijn seq.*/
say 'length of the' @deB " is " length($) /*display the length of de Bruijn seq.*/
say; say 'first 130 digits of the' @deB":" /*display the title for the next line. */
say left($, 130) /*display 130 left-most digits of seq. */
say; say ' last 130 digits of the' @deB":" /*display the title for the next line. */
say right($, 130) /*display 130 right-most digits of seq.*/
call val $ /*call the VAL sub for verification. */
@deB= 'reversed' @deB /*next, we'll check on a reversed seq.*/
$r= reverse($) /*do what a mirror does, reversify it.*/ call val $r /*call the VAL sub for verification. */ $= overlay(., $, 4444) /*replace 4,444th digit with a period. */
@deB= 'overlaid' subword(@deB, 2) /* [↑] this'll cause a validation barf.*/
call val $ /*call the VAL sub for verification. */ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ val: parse arg $$$; e= 0; _= copies('─',8) /*count of errors (missing PINs) so far*/
say; say _ 'validating the' @deB"." /*display what's happening in the pgm. */
do pin=0 for 1e4; pin4= right(pin,4,0) /* [↓] maybe add leading zeros to pin.*/
if pos(pin4, $$$)\==0 then iterate /*Was number found? Just as expected. */
say 'PIN number ' pin " wasn't found in" @deb'.'
e= e + 1 /*bump the counter for number of errors*/
end /*pin*/ /* [↑] validate all 10,000 pin numbers*/
if e==0 then e= 'No' /*Gooder English (sic) the error count.*/
say _ e 'errors found.' /*display the number of errors found. */
return</lang>
- output is identical to the 1st REXX version.
Visual Basic .NET
<lang vbnet>Imports System.Text
Module Module1
ReadOnly DIGITS As String = "0123456789"
Function DeBruijn(k As Integer, n As Integer) As String
Dim alphabet = DIGITS.Substring(0, k)
Dim a(k * n) As Byte
Dim seq As New List(Of Byte)
Dim db As Action(Of Integer, Integer) = Sub(t As Integer, p As Integer)
If t > n Then
If n Mod p = 0 Then
Dim seg = New ArraySegment(Of Byte)(a, 1, p)
seq.AddRange(seg)
End If
Else
a(t) = a(t - p)
db(t + 1, p)
Dim j = a(t - p) + 1
While j < k
a(t) = j
db(t + 1, t)
j += 1
End While
End If
End Sub
db(1, 1)
Dim buf As New StringBuilder
For Each i In seq
buf.Append(alphabet(i))
Next
Dim b = buf.ToString
Return b + b.Substring(0, n - 1)
End Function
Function AllDigits(s As String) As Boolean
For Each c In s
If c < "0" OrElse "9" < c Then
Return False
End If
Next
Return True
End Function
Sub Validate(db As String)
Dim le = db.Length
Dim found(10000) As Integer
Dim errs As New List(Of String)
' Check all strings of 4 consecutive digits within 'db'
' to see if all 10,000 combinations occur without duplication.
For i = 1 To le - 3
Dim s = db.Substring(i - 1, 4)
If (AllDigits(s)) Then
Dim n As Integer = Nothing
Integer.TryParse(s, n)
found(n) += 1
End If
Next
For i = 1 To 10000
If found(i - 1) = 0 Then
errs.Add(String.Format(" PIN number {0,4} missing", i - 1))
ElseIf found(i - 1) > 1 Then
errs.Add(String.Format(" PIN number {0,4} occurs {1} times", i - 1, found(i - 1)))
End If
Next
Dim lerr = errs.Count
If lerr = 0 Then
Console.WriteLine(" No errors found")
Else
Dim pl = If(lerr = 1, "", "s")
Console.WriteLine(" {0} error{1} found:", lerr, pl)
errs.ForEach(Sub(x) Console.WriteLine(x))
End If
End Sub
Function Reverse(s As String) As String
Dim arr = s.ToCharArray
Array.Reverse(arr)
Return New String(arr)
End Function
Sub Main()
Dim db = DeBruijn(10, 4)
Dim le = db.Length
Console.WriteLine("The length of the de Bruijn sequence is {0}", le)
Console.WriteLine(vbNewLine + "The first 130 digits of the de Bruijn sequence are: {0}", db.Substring(0, 130))
Console.WriteLine(vbNewLine + "The last 130 digits of the de Bruijn sequence are: {0}", db.Substring(le - 130, 130))
Console.WriteLine(vbNewLine + "Validating the deBruijn sequence:")
Validate(db)
Console.WriteLine(vbNewLine + "Validating the reversed deBruijn sequence:")
Validate(Reverse(db))
Dim bytes = db.ToCharArray
bytes(4443) = "."
db = New String(bytes)
Console.WriteLine(vbNewLine + "Validating the overlaid deBruijn sequence:")
Validate(db)
End Sub
End Module</lang>
- Output:
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
Wren
<lang ecmascript>import "/fmt" for Fmt import "/str" for Str
var deBruijn = "" for (n in 0..99) {
var a = Fmt.rjust(2, n, "0")
var a1 = a[0].bytes[0]
var a2 = a[1].bytes[0]
if (a2 >= a1) {
deBruijn = deBruijn + ((a1 == a2) ? String.fromByte(a1): a)
var m = n + 1
while (m <= 99) {
var ms = Fmt.rjust(2, m, "0")
if (ms[1].bytes[0] > a1) deBruijn = deBruijn + a + ms
m = m + 1
}
}
}
deBruijn = deBruijn + "000" System.print("de Bruijn sequence length: %(deBruijn.count)\n") System.print("First 130 characters:\n%(deBruijn[0...130])\n") System.print("Last 130 characters:\n%(deBruijn[-130..-1])\n")
var check = Fn.new { |text|
var res = []
var found = List.filled(10000, 0)
var k = 0
for (i in 0...(text.count-3)) {
var s = text[i..i+3]
if (Str.allDigits(s)) {
k = Num.fromString(s)
found[k] = found[k] + 1
}
}
for (i in 0...10000) {
k = found[i]
if (k != 1) {
var e = " Pin number %(Fmt.dz(4, i)) "
e = e + ((k == 0) ? "missing" : "occurs %(k) times")
res.add(e)
}
}
k = res.count
if (k == 0) {
res = "No errors found"
} else {
var s = (k == 1) ? "" : "s"
res = "%(k) error%(s) found:\n" + res.join("\n")
}
return res
}
System.print("Missing 4 digit PINs in this sequence: %(check.call(deBruijn))") System.print("Missing 4 digit PINs in the reversed sequence: %(check.call(deBruijn[-1..0]))")
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))")</lang>
- Output:
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
zkl
<lang zkl>dbSeq:=Data(); // a byte/character buffer foreach n in (100){
a,a01,a11 := "%02d".fmt(n), a[0,1], a[1,1];
if(a11<a01) continue;
dbSeq.append( if(a01==a11) a01 else a );
foreach m in ([n+1 .. 99]){
if("%02d".fmt(m)[1,1] <= a01) continue;
dbSeq.append("%s%02d".fmt(a,m));
}
} dbSeq.append("000");</lang> <lang zkl>seqText:=dbSeq.text; println("de Bruijn sequence length: ",dbSeq.len());
println("\nFirst 130 characters:\n",seqText[0,130]); println("\nLast 130 characters:\n", seqText[-130,*]);
fcn chk(seqText){
chk:=Dictionary();
foreach n in ([0..seqText.len()-1]){ chk[seqText[n,4]]=True }
(9999).pump(List,"%04d".fmt,'wrap(k){ if(chk.holds(k)) Void.Skip else k })
} println("\nMissing 4 digit PINs in this sequence: ", chk(seqText).concat(" ")); print("Missing 4 digit PINs in the reversed sequence: ",chk(seqText.reverse()).concat(" "));
println("\n4444th digit in the sequence: ", seqText[4443]); dbSeq[4443]="."; println("Setting the 4444th digit and reruning checks: ",chk(dbSeq.text).concat(" "));</lang>
- Output:
de Bruijn sequence length: 10003 First 130 characters: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350 Last 130 characters: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000 Missing 4 digit PINs in this sequence: Missing 4 digit PINs in the reversed sequence: 4444th digit in the sequence: 4 Setting the 4444th digit and reruning checks: 1459 4591 5814 8145