# Safe cracker string with all combinations

Imagine a safe with a 4-digit code, and accepting a continuous stream of code entries, such that when the 4 digits are seen in the right sequence, the safe opens. Generate a short string that contains all possible code combinations, so that when you feed it to the safe, it will inevitably open. The string should be as short as possible, and not contain the same code sequence twice.

As an exercise while learning Scala, I implemented a general version of this logic using an arbitrary symbol alphabet and customizable code length. For example, to generate a string for a 4-digit safe with numeric symbols, you would call SafeCracker.genCrackerString("0123456789", 4). I'm looking for a review of all aspects of this code, and the unit tests too.

object SafeCracker {

def genCrackerString(symbols: String, codeLength: Int) = {
require(symbols.nonEmpty)
require(codeLength > 0)

val combinations = math.pow(symbols.length, codeLength)

def cracker(prefix: String, used: Set[String]): String = {

def findSuffixCombo(num: Int): (String, String) = {
val suffix = getNth(symbols, num)
val combo = (prefix + suffix).takeRight(codeLength)

if (!used.contains(combo)) (suffix, combo)
else findSuffixCombo(num + 1)
}

if (used.size == combinations) prefix
else {
val (suffix, combo) = findSuffixCombo(0)
cracker(prefix + suffix, used + combo)
}
}

val first = symbols(0).toString * codeLength

cracker(first, Set(first))
}

def getNth(symbols: String, num: Int) = {
val base = symbols.length

def getNth(prefix: String, num: Int): String = {
if (num == 0) {
if (prefix.isEmpty) symbols(0).toString
else prefix
} else {
val index = num % base
val digit = symbols(index)
getNth(digit + prefix, num / base)
}
}
getNth("", num)
}
}


Unit tests:

import org.junit.runner.RunWith
import org.scalatest.FunSuite
import org.scalatest.junit.JUnitRunner

@RunWith(classOf[JUnitRunner])
class SafeCrackerTest extends FunSuite {

test("cracker invalid if no symbols") {
intercept[IllegalArgumentException](genCrackerString("", 1))
}

test("cracker invalid if code length < 1") {
intercept[IllegalArgumentException](genCrackerString("123", 0))
}

test("cracker 123, len=1") {
assert("123" == genCrackerString("123", 1))
}

test("cracker 1, len=3") {
assert("111" == genCrackerString("1", 3))
}

test("cracker 12, len=2") {
assert("112122" == genCrackerString("12", 2))
}

test("cracker 12, len=3") {
assert("111211221222" == genCrackerString("12", 3))
}

test("cracker 0123456789, len=4") {
assert(10294 == genCrackerString("0123456789", 4).length)
}

test("getNth 0123456789abcdef, 255") {
assert("ff" == getNth("0123456789abcdef", 255))
}
}


Your algorithm is suboptimal. According to this website, a de Bruijn sequence for SafeCracker.genCrackerString("0123", 3) should be 66 characters long:
000100200301101201302102202303103203311121131221231321332223233300

00010020030011012013011121021131031122022123023121320321330331322232332333

A simpler example is genCrackerString("12", 2), which your unit test says should be "112122". However, "11221" is shorter. So, your unit tests are invalid as well.