Tuesday, July 22, 2008

Project Euler with Scala

I came across this interesting post about solving some Project Euler questions using Scala. Being a fan of Project Euler myself, I though I'll outline some of the solutions that I came up using Scala. Of course, I have taken trivial examples and the objective is more to learn Scala than to have an efficient solution. So here are some examples:
Warning: Spoilers ahead.

Problem 13.
"Work out the first ten digits of the sum of the following one-hundred 50-digit numbers". And hundred 50-digit numbers are given. (Not listing the numbers here to avoid clutter).

One possible solution:


object P13 extends Application {
val s = "..." //The numbers as a string separated by space.
val numbers = for (number <- s.split(" ")) yield new BigInt(new java.math.BigInteger(number))
val zero:BigInt = 0
println ((zero /: numbers)(_+_).toString.substring(0, 10))
}


Hmm, pretty simple program. We define an object which extends Application, so that we don't have to write main method. Then we initialize the variable. Next line simply parses the string and creates a List of BigInts. We have a constant 'zero' which is BigInt 0. Finally we add the numbers using fold and take first 10 characters. If you don't like /:, you can also use (numbers.foldLeft(zero)(_+_).

Problem 22.

"Using names.txt, a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score."
One possible solution:


import java.io._
import scala.collection.jcl._

object P22 extends Application {
val res = new BufferedReader(new FileReader("c:\\names.txt")).readLine
val actualNames = res.split(",") map (_.filter(_.isLetter).mkString)
val sorted = new TreeSet[String]
sorted ++= actualNames
val nums = sorted map (_.foldLeft(0)(_+_-64))
var sum: BigInt = 0
var t = 0
for (j <- nums) {
t += 1
sum += (t * j)
}
println(sum)
}

First, we read the lines of the file (so easy with scala). Then split based on ',' and strip off the '"'. Create a sorted set (we are using the same TreeSet from Java) and add the names. Calculate the value using fold left (Since they are upcase chars, subtract 64 to get int values). Ok, now we need to multiply each number by its position. Easy thing to do in imperative fashion. So lets do a traditional for each loop and that's it.

Update: Seth Tisue pointed out that zipWithIndex can be used to do the final calculation. The problem considers index starting with 1, so we cannot directly use zipWithIndex. However zip can be used as below:


val l = nums toList
val indices = 1 to l.size toList
l.zip(indices).foldLeft(sum)((a,b) => a + b._1 * b._2)


Problem 42


import java.io._
import scala.collection.jcl._
object P42 extends Application {
val triangular = new TreeSet[Int]
for (i <- 0 until 40) triangular += i*(i+1)/2
val lines = new BufferedReader(new FileReader("c:\\words.txt")).readLine
val nums = lines.split(",") map (_.filter(_.isLetter).mkString) map (_.foldLeft(0)(_+_-64))
println((0 /: nums)( (result, num) => if (triangular contains num) result+1 else result ))
}

By now this should be obvious. This example is similar to the one above. First we cache first 40 triangular numbers in an Array. Then read the file. Split lines by ',', ignore special characters (by filtering) and find the required sum (using map). I've done it in one line as it appears natural. Finally, count the triangular numbers. I used a fold, but it can be done imperatively as well.

Hope you enjoyed it. Do let me know if you think there are better ways of doing this (Not in terms of performance, but in terms of elegance or functional style).

8 comments:

Seth Tisue said...
This comment has been removed by the author.
Seth Tisue said...

Problem 13, BigInt has a constructor that takes a String, so you don't need to go through java.math.BigInteger.

Problem 22 has a pretty compact functional solution. To "multiply this value by its alphabetical position in the list" it's helpful to use zipWithIndex. You can use scala.io.Source to do the same task the java.io stuff does.

The last part of Problem 42 seems more elegant and readable to me if you use filter followed by size, rather than doing the count using a fold. (The fold might run faster since you avoid constructing an intermediate data structure? Not sure.)

bodhi said...

Thanks for the suggestions, Seth.
P13: I couldn't find such a constructor in 2.7.1. Maybe its added later.

P22. I updated the post with your suggestion

P23. I agree, but both forms looks fine to me.

Seth Tisue said...

You're welcome.

The BigInt constructor that takes a string is in 2.7.1:

~> scala
Welcome to Scala version 2.7.1.final (Java HotSpot(TM) Client VM, Java 1.5.0_13).
Type in expressions to have them evaluated.
Type :help for more information.

scala> BigInt("123") + BigInt("456")
res0: BigInt = 579

bodhi said...

I see. I didn't check the companion object for BigInt. I just checked the constructors.

Seth Tisue said...

Oh, my mistake for using the word "constructor".

GrokCode said...

I just started learning Scala, and am also using the Project Euler problems to do it. Its a nice coincidence that I ran across this post. You might want to see my impressions of Scala and Project Euler here.

Víctor Martínez said...

Hello,
I realize this post its a bit old. Since then the new Scala API lets you solve this problem 22 in even an easier way:

val in = scala.io.Source.fromFile("names.txt").getLines.toList
val x = in(0).split(',').toList.sortWith(_.compareTo(_)<0).map(t => t.toList.map(_.toInt - 64).foldLeft(0.0)(_+_))
val r = x.zipWithIndex.foldLeft((a,b) => a + b._1 * (b._2+1))
println(r)

As you can see, we can now read the whole file in a single line without the use of java Buffers.

Thanks for this post for giving me some insight into the problem.