De Bruijn sequences: Difference between revisions
→{{header|J}}
Line 1,094:
PIN number 8145 missing
</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}}==
| |||