This post originated from an RSS feed registered with Scala Buzz
by Jeff Heon.
Original Post: Cédric Beust's Coding Challenge
Feed Title: The Careful Programmer
Feed URL: http://thecarefulprogrammer.blogspot.com/feeds/posts/default
Feed Description: A (starting) collection of my musings about programming. I'll brush more often on Scala related topics since I am currently learning it.
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 precedent 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(precedent:Int, serie:List[int], f: (Int, Int) => Int): List[Int] = serie match { case Nil => Nil case head :: tail => (head - precedent)::pairMap(head, tail, (a:Int, b:Int)=>(b - a)) }
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 exerises 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
Previous Topic
