De Bruijn sequences: Difference between revisions
→{{header|Julia}}
Line 596:
PIN number 8145 missing
</pre>
=={{header|Java}}==
{{trans|C++}}
<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>
{{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|Julia}}==
Line 659 ⟶ 796:
The sequence does not contain all PINs.
</pre>
=={{header|Kotlin}}==
| |||