De Bruijn sequences: Difference between revisions
Content deleted Content added
Line 1,094: | Line 1,094: | ||
PIN number 8145 missing |
PIN number 8145 missing |
||
</pre> |
</pre> |
||
=={{header|Groovy}}== |
|||
{{trans|Java}} |
|||
<lang groovy>import java.util.function.BiConsumer |
|||
class DeBruijn { |
|||
interface Recursable<T, U> { |
|||
void apply(T t, U u, Recursable<T, U> r); |
|||
} |
|||
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({ int t, int 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) |
|||
} |
|||
} |
|||
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, '.' as char) |
|||
System.out.println() |
|||
System.out.println("Validating the overlaid de Bruijn sequence:") |
|||
validate(sb.toString()) |
|||
} |
|||
}</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 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</pre> |
|||
=={{header|J}}== |
=={{header|J}}== |