Safe cracker string with all combinations

Question

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))
  }
}

Answer 1

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

000100200301101201302102202303103203311121131221231321332223233300

However, your output is 74 characters long:

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.