Look and say sequence (Scala)

From LiteratePrograms

Other implementations: C++ | dc | Eiffel | Haskell | J | Java | Lua | OCaml | Perl | PHP | Python | Ruby | Scala | sed | sh

This is a simple Scala program to generate look-and-say sequences such as the Conway sequence.

To begin with, given a string representing a number we need to be able to generate the next number. generateNext does that by consuming the string one character at a time: if the last character seen is the same as the previous one, then the last seen character remains unchanged, but its count goes up by one. Every time the current character no longer matches the previous one, the length of the current sequence curlen is written out together with the character that contains the digit we've seen that many times, and the character to match is now the new character with a count of 1.

<<generateNext>>=
    def generateNext(digits: String, prev: Char, curlen: Int): String = {
      if (digits=="") curlen.toString + prev
      else if (prev == digits.charAt(0)) generateNext(digits.substring(1),
						      prev,
						      (curlen + 1))
      else curlen.toString + prev + generateNext(digits.substring(1),
						 digits.charAt(0),
						 1)
    }

Now we can write the lookAndSay function. It just takes the seed to start the sequence, and the requested length of the sequence. lookAndSay would call generateNext and use the result to seed the recursive call to itself, with length decremented by one.

Note that Scala allows us to nest function definitions; generateNext is local to the scope of lookAndSay since we're not going to use it anywhere else.

<<lookAndSay>>=
  def lookAndSay(seed: String, length: Int): List[String] = {
    generateNext
    if (length == 0) Nil
    else {
      val next = generateNext(seed.substring(1), seed.charAt(0), 1)
      seed :: lookAndSay(next, length-1)
    }
  }

And for completeness, a driver main function that passes the first two arguments it received to lookAndSay.

<<LookAndSay.scala>>=
object LookAndSay {
  lookAndSay
  def main(args: Array[String]): Unit = {
    System.out.println(lookAndSay(args(0), Integer.parseInt(args(1))))
  }
}

Download code