112 lines
3.5 KiB
Groovy
112 lines
3.5 KiB
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())
|
|
}
|
|
}
|