De Bruijn sequences: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
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.
<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++}}==
Line 210 ⟶ 336:
Validating the overlaid de Bruijn sequence:
4 errors found:
PIN number 1459 missing
Line 974:
Missing: 1459 4591 5814 8145
Extra: 1559 5591 5815 8155</pre>
=={{header|Phix}}==
Line 1,306 ⟶ 1,238:
5814 is missing
</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}}==
| |||