Monday, July 21, 2008

Cédric Beust's Coding Challenge

I finally got around finishing Cédric Beust's coding challenge in Scala.

It didn't help that I got sidetracked by Tony Morris Scala and Haskell exercises for beginners.
Scala exercises for beginners
Haskell exercises for beginners

But back to the coding challenge!

From Cédric's website: Coding Challenge

Here is an interesting coding challenge: write a counter function that counts from 1 to max but only returns numbers whose digits don't repeat.

For example, part of the output would be:

* 8, 9, 10, 12 (11 is not valid)
* 98, 102, 103 (99, 100 and 101 are not valid)
* 5432, 5436, 5437 (5433, 5434 and 5435 are not valid)


* Display the biggest jump (in the sequences above, it's 4: 98 -> 102)
* Display the total count of numbers
* Give these two values for max=1000

Since my solution is in Scala, I tried to make it as functional as I could instead of doing a standard imperative exercise.

It has been an worthwhile exploration of Scala for me.

So here it is.

First, the necessary functions to determine if a number has repeated digits or not:

def getDigits(number: int): Array[int] = - 48)

def hasRepeatedDigits(number: int): boolean = {
    val digits = getDigits(number)
    val digitPresent = Array.make[int](10, 0)
    digits.foreach(digit => digitPresent(digit) += 1)
    digitPresent.exists(_ > 1)

Now, to generate the list itself. That is the part I feel the most imperative. I tried different ways, including a recursive function, but this seemed the simplest way in the end:

def getNonRepeatedDigitNumbers(max:Int): List[Int] = List.range(1,max+1).filter(!hasRepeatedDigits(_))

Next has been the most interesting part for me. I started with the idea that I would use a list of the gaps and simply get the maximum from it.
Here is the idea:

def maximum(x: List[Int]): Int = (x.head /: x.tail)((a:Int, b:Int)=>(if (a>b) a else b))

But how to get the gap list? I needed something similar to a fold operation, but I wanted to operate always with the current and previous element instead of accumulating a result to operate with the current element.

Maybe I am just reinventing the wheel here, but here is my "pair" map function:

def pairMap(previous:Int, serie:List[int], f: (Int, Int) => Int): List[Int] = serie match {
    case Nil => Nil
    case head :: tail => f(
previous, head)::pairMap(head, tail, f)

An here is how I get the gap list:

def getGapList(serie: List[int]) = serie match {
    case Nil => Nil
    case head :: tail => pairMap(head, tail, (a:Int, b:Int)=>(b - a))

As an aside, I realized from Tony Morris exercises that I tended to include a superfluous match in my recursive list functions.
For example, here is how I first wrote the preceding function:

def getGapList(serie: List[int]) = serie match {
    case Nil => Nil
    case head :: Nil => Nil
    case head :: tail => pairMap(head, tail, (a:Int, b:Int)=>(b - a))

At last, here is how I used the functions to solve the code challenge:

val serie = getNonRepeatedDigitNumbers(1000)
val totalCount = serie.size

println("Biggest jump: " + maximum(getGapList(serie)))
println("Total count of numbers: " + totalCount)


jau said...

I think you can do _ - '0'

The Careful Programmer said...

>I think you can do _ - '0'

Indeed, thanks!