De Bruijn sequences: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 78: | Line 78: | ||
:* An OEIS entry: [https://oeis.org/A166315 A166315 lexicographically earliest binary de Bruijn sequences, B(2,n)] --- Not B(10,4), but possibly relevant. |
:* An OEIS entry: [https://oeis.org/A166315 A166315 lexicographically earliest binary de Bruijn sequences, B(2,n)] --- Not B(10,4), but possibly relevant. |
||
<br><br> |
<br><br> |
||
=={{header|C sharp|C#}}== |
|||
{{trans|Kotlin}} |
|||
<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> |
|||
{{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|C++}}== |
=={{header|C++}}== |
||
Line 210: | Line 336: | ||
Validating the overlaid de Bruijn sequence: |
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</pre> |
|||
=={{header|C#}}== |
|||
{{trans|Kotlin}} |
|||
<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> |
|||
{{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: |
4 errors found: |
||
PIN number 1459 missing |
PIN number 1459 missing |
||
Line 974: | Line 974: | ||
Missing: 1459 4591 5814 8145 |
Missing: 1459 4591 5814 8145 |
||
Extra: 1559 5591 5815 8155</pre> |
Extra: 1559 5591 5815 8155</pre> |
||
=={{header|Perl 6}}== |
|||
{{works with|Rakudo|2019.07.1}} |
|||
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> |
|||
{{out|Sample output}} |
|||
<pre>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</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Line 1,306: | Line 1,238: | ||
5814 is missing |
5814 is missing |
||
</pre> |
</pre> |
||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{works with|Rakudo|2019.07.1}} |
|||
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> |
|||
{{out|Sample output}} |
|||
<pre>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</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |