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)

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).