De Bruijn sequences: Difference between revisions

=={{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>