How to resolve the algorithm De Bruijn sequences step by step in the C# programming language
How to resolve the algorithm De Bruijn sequences step by step in the C# programming language
Table of Contents
Problem Statement
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: distinct de Bruijn sequences B(k, n).
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.
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.
(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.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm De Bruijn sequences step by step in the C# programming language
This C# code generates and validates a De Bruijn sequence, which is a circular list of all possible strings of a given length and alphabet. In this case, the code generates a De Bruijn sequence of length 4 and alphabet size 10.
Key Functions and Variables:
- DeBruijn: Generates the De Bruijn sequence using a recursive algorithm.
- AllDigits: Checks if a given string contains only digits.
- Validate: Validates the De Bruijn sequence by checking if all possible 4-digit combinations appear exactly once.
- Reverse: Reverses a given string.
Main Program Flow:
- Generate a De Bruijn sequence of length 4 and alphabet size 10 using
DeBruijn. - Display the first and last 130 digits of the sequence.
- Validate the sequence using
Validate. - Reverse the sequence using
Reverseand validate it again. - Overlay a dot at position 4443 of the sequence and validate it.
DeBruijn Sequence Generation:
The DeBruijn function uses a recursive algorithm to generate the De Bruijn sequence. It takes two parameters:
k: Alphabet size (10 in this case).n: Sequence length (4 in this case).
The algorithm works by constructing the sequence incrementally. It starts with an empty sequence and gradually adds characters to it. The db function within DeBruijn recursively explores different possibilities by incrementing the position t and testing different characters j from the alphabet.
Validation:
The Validate function verifies that the De Bruijn sequence contains all possible 4-digit combinations of the digits 0-9 exactly once. It iterates through the sequence, checking that each substring of 4 consecutive digits is a unique combination and within the expected range.
Reversal and Overlaying:
The reversed sequence is validated for correctness to ensure that it still satisfies the De Bruijn property. Additionally, an overlaid version of the sequence is created by replacing one character with a dot and validated to check if the property still holds.
Output:
The program displays the following output:
- Length of the De Bruijn sequence.
- First and last 130 digits of the sequence.
- Validation results for the original, reversed, and overlaid sequences.
Source code in the csharp programming language
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);
}
}
}
You may also check:How to resolve the algorithm Apply a callback to an array step by step in the Lua programming language
You may also check:How to resolve the algorithm Polyspiral step by step in the Processing programming language
You may also check:How to resolve the algorithm Strip a set of characters from a string step by step in the Swift programming language
You may also check:How to resolve the algorithm Execute HQ9+ step by step in the PureBasic programming language
You may also check:How to resolve the algorithm Arithmetic/Integer step by step in the LSE64 programming language