Tuesday, November 4, 2008

ProjectEuler#42, aka Scala shines as a scripting language

I'm still playing with project Euler, and I'm going to love Scala more and more.
Yesterday, I solved the #42 problem, on which we need to parse a text file, and make some simple transformations and filtering on the results (it's why I choose this title, because it's generally the kind of things you expect to do in a scripting language, and well, I'm really
impressive, and I read this morning the post "Scala as a scripting language?", and I say "ho, it's exactly what I felt when I did pb#42 yesterday, let's blog on it, it's fashion :)

So, this problem is a simple Project Euler one (at least, there is no math on it), but just stop and think to what may look the Java's solution. Yes, you will have to deal with Files, input stream, and the like, filtering data, sorting things, and even if it's quite simple, it's always a little too heavy compared to what it may be.

So, there is the full solution in Scala, in a mixed imperative and functional style, as produced in the first sketch version (OK, I'm lying, in the first sketch, I didn't include comments and variables names looked more to 'lsv' and the like, these transformations are blog add-ons).

I'm sure there is a lot of optimizations available, but the important think is that Scala let you program as you think, whitout to much noise and boilerplate...

So let's go for the code:


package ex26_50
import scala.io.Source
/*
Problem#42
The nth term of the sequence of triangle numbers
is given by, tn = n(n+1);
so the first ten triangle numbers are:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its
alphabetical position and adding these values we form a word value.
For example, the word value for SKY is 19 + 11 + 25 = 55 = t10.

If the word value is a triangle number then we shall
call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'),
a 16K text file containing nearly two-thousand common English
words, how many are triangle words?

*/

object Problem42 extends Application {

/*
* iterate over all the lines of a file and
* split each one on ',', remove surronding ",
* and put the result in a list
*/
def parseWords(file:String): List[String] = {
for {
line <- Source.fromFile(file).getLines.toList
s <- line.split(",")
if(!s.isEmpty)
} yield s.replaceAll("\"","")
}

/*
* Simple mapping function that associate
* each char to it's value (position in the alphabet, begin to 1)
* and a word to the sum of its char value
*/
def wordValue(s:String) : Int = {
var sum = 0
for(c <- s) {
// iterate over the chars of the string
val cval = c.toInt
if(cval >= 64 && cval <= 90) {
// 64 = ascii val for 'A', 90 = ascii val for 'Z'
sum = sum + cval - 64
} else {
error("Unauthorized char: " + c.toString)
}
}
sum
}

/*
* That's the definition of the list number on witch we will work:
* - parse the file to a list of word
* - transform each word to it's word value
* - sort the resulting, so that we can know the
* upper bound of our triangle value to caluculate
*/

val list_wordValues =
parseWords("src/words.txt").map(wordValue(_)).sort(_ > _)

//we also see that in Scala, Format syntax is actually usable
println("Max value in %s words: %s (min: %s)".format(
list_wordValues.size,
list_wordValues.head,
list_wordValues.reverse.head))

/*
* Given the upper bound,
* generate the set of triangle number
*/
val set_triangles = {
var set = Set[Int]()
var n = 1
var i = 1
while (n < max ) {
n = (i * (i+1))/2
i = i + 1
set = set.+(n)
}
set
}

/*
* That's all, we just have to filter the list of words to
* only keep whose which are in the set of triangles value,
* and take the size of the resulting list.
*/
val nb = list_wordValues.filter( (i:Int) =>
set_triangles.contains(i)).size

println("Found %s triangles words !".format(nb))
}


I love scala :)

PS: It's the full working solution, appart from the leading "_", sorry for the formatting, it seems that blogger is not the most friendly for code formatting. If somebody has some hint on that subject, I will be glad to heard them (ok, perhaps I should have a look on the plugins)

EDIT: I found a way to highlight code thanks to SHJS. Thanks to the author for this plugin that wasn't to hard to make it work with blogger, and which the only Javascript highlighter that supports Scala :)

2 comments:

Landei

That looks not too bad, but you should try harder to take advantage of Scala's functional idioms, e.g.:

def wordValue(s:String) : Int = (0 /: s){ (sum:Int, c:Char) =>
if(c >= 64 && c <= 90) sum + c - 64
else error("Unauthorized char: " + c.toString)
}

Fanf

Well, this example was *really* written has thoughts came, and it seems that fold left was not my first thougth. But you're rigth, it's nicer than my ugly for :)

  © Blogger template 'Minimalist G' by Ourblogtemplates.com 2008

Back to TOP