{ by david linsin }

July 02, 2008

Coding Challenges

Cedric Beust posted a little coding challenge on his blog, where he is asking to do the following:
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=10000

Actually I'm not a big fan of coding challenges. I guess it's probably because I'm rather slow at coding. In most of the cases there's a time constraint involved and I'm simply not the kind programmer who slaps out some junk of code in no time. I like to take my time when approaching a problem. It's a process and any none technical form of process is inherently slow! I like to code a little and then take a step back to take a look at it, probably tweak it or dispose it, because it's not good enough! It's funny, because Bob Lee seems to follow the same approach on this challenge. If you take a look at the comments on Cedric's blog, you'll see that he tweaked his solution a couple of times.

Since there is no time constraint on Cedric's puzzle, I thought I'd give it a try. For me it was the perfect opportunity to do some Scala. So I came up with the following solution:
class Counter(lower:Int, upper:Int) {
printMaxGapAndCount(filterDuplicates(new Range.Inclusive(lower, upper, 1)))
def hasNoDuplicate(charvals:Array[Char]):Boolean = {
charvals.takeWhile(charval => charvals.filter(el => el == charval).size == 1).size == charvals.size
def filterDuplicates(range:Range):List[Int] = {
range.toList.filter(num => hasNoDuplicate(num.toString.toArray))
def printMaxGapAndCount(list:List[Int]) = {
println("count: " + list.size + ", max gap: " + list.map(el => list.dropWhile(num => num x > y).head)

I'm pretty sure it's horrible Scala style and frankly I have no idea if it even works correctly or does what it's supposed to do. However, I get decent results for Cedric's examples - at least something. The downside is performance! My approach is brute force and takes over 5 minutes on my Mac Book Pro. It's doing a lot of collection manipulation and I tried very hard to not have any mutable state.

If you take a look at the comments on Credrics blog you'll see all sorts of other solutions in various languages. There's another Scala approach by DavidLG which completes on my machine in a couple of seconds and produces the same results as my approach. I'm not to sure if I'm allowed to post his code, so go take a look at it and try to grasp what he's doing. It must be some math magic, cause I kinda don't get it.

As for coding challenges, I'm still not a fan, because I'm simply too slow. As with all of it in live, there's an exception to the rule: JavaBlackBelt. It's a site where you are being asked questions to certain topics (not only Java) in form of exams. If you pass an exam, you collect knowledge points. Those points are represented as colored belts. It's a really nice concept with a great community behind it and definitely worth a look, if you haven't heard of it before.

I love to get my hands dirty with Java and so far I've learned something new in every exam I've taken. And off the record: I really want that black belt!


Blogger said...

thanks to your post - i found out about this challenge =)
My solutions (java) takes about 0.5 sec, but it uses collections too (

I am not a fast challenge solver too, but we have to practise and improve our speed )

good site to improve algorithmic skills is http://icpcres.ecs.baylor.edu/onlinejudge/

David Linsin said...

Thx for the link, looks interesting! Actually it looks like a not so web 2.0 kind of topcoder.


  • mail(dlinsin@gmail.com)
  • jabber(dlinsin@gmail.com)
  • skype(dlinsin)