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)

Also:

* 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] = number.toString.toArray.map(_.toInt - 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)

## 2 comments:

I think you can do _ - '0'

>I think you can do _ - '0'

Indeed, thanks!

Post a Comment