De Bruijn sequences: Difference between revisions
Add Scala implementation
m (→{{header|Wren}}: Minor tidy) |
(Add Scala implementation) |
||
Line 3,161:
PIN number 5814 missing
PIN number 8145 missing</pre>
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="Scala">
import scala.collection.mutable.ListBuffer
object DeBruijn {
def deBruijn(k: Int, n: Int): String = {
val a = Array.fill[Byte](k * n)(0)
val seq = new ListBuffer[Byte]()
def db(t: Int, p: Int): Unit = {
if (t > n) {
if (n % p == 0) {
seq ++= a.slice(1, p + 1)
}
} else {
a(t) = a(t - p)
db(t + 1, p)
for (j <- (a(t - p) + 1).until(k)) {
a(t) = j.toByte
db(t + 1, t)
}
}
}
db(1, 1)
val sb = new StringBuilder
seq.foreach(i => sb.append("0123456789".charAt(i)))
sb.append(sb.subSequence(0, n - 1)).toString
}
private def allDigits(s: String): Boolean = s.forall(_.isDigit)
private def validate(db: String): Unit = {
val found = Array.fill(10000)(0)
val errs = ListBuffer[String]()
for (i <- 0 until db.length - 3) {
val s = db.substring(i, i + 4)
if (allDigits(s)) {
val n = s.toInt
found(n) += 1
}
}
for (i <- found.indices) {
if (found(i) == 0) errs += s" PIN number $i is missing"
else if (found(i) > 1) errs += s" PIN number $i occurs ${found(i)} times"
}
if (errs.isEmpty) println(" No errors found")
else {
val pl = if (errs.size == 1) "" else "s"
println(s" ${errs.size} error$pl found:")
errs.foreach(println)
}
}
def main(args: Array[String]): Unit = {
val db = deBruijn(10, 4)
println(s"The length of the de Bruijn sequence is ${db.length}\n")
println(s"The first 130 digits of the de Bruijn sequence are: ${db.take(130)}\n")
println(s"The last 130 digits of the de Bruijn sequence are: ${db.takeRight(130)}\n")
println("Validating the de Bruijn sequence:")
validate(db)
println()
println("Validating the reversed de Bruijn sequence:")
validate(db.reverse)
val overlaidDb = db.updated(4443, '.')
println()
println("Validating the overlaid de Bruijn sequence:")
validate(overlaidDb)
}
}
</syntaxhighlight>
{{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 reversed 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|Visual Basic .NET}}==
| |||