31 Jan 2009

Project Euler problem 21 using Scala

Randomly picking another Euler challenge using Scala, I turned my attention to problem 21 this time. This asks to find the set of Amicable numbers under 10000 and sum them up.
This led to playing around with Scala's Sequence comprehension's a bit. Here's my solution:



object Euler21 {
def sumOfDivisors(number: Int): Int = {
List.range(1, number).filter{i => (number % i) == 0}.foldLeft(0){(a,b) => a+b}
}

def main(args: Array[String]): Unit = {
(for (i <- 0 until 10000; d_i = sumOfDivisors(i);
if(d_i > i && sumOfDivisors(d_i) == i))
yield (i + d_i)).foldLeft(0){(a,b) => a+b};
}
}



I like the brevity of this solution. The function sumOfDivisors first filters out all divisors of a given number and sums the resulting list using the foldLeft function. The main function first computes this sum for each number in the range 1 till 10000. The resulting number, d_i is used for further processing only if it's larger than the original number, this is to avoid double results of the same pair of amicable numbers twice (i.e if we have processed the number 220 and found 284 as its amicable pair, we don't have to go through the same exercise again if we process 284 next in our list). If this holds, we calculate the sum of divisors of the number d_i. If that's equal to our original number, we have a match, so we add the sum of the two numbers it to our output. The output is Scala's Projection trait, so we can obtain the desired sum by adding up all numbers using a foldLeft function again. Incidentally, you may want to check whether the generated sequence of numbers is actually correct. In this case, instead of doing the summing, use this line of code:


for (i <- 0 until 100000; di = sumOfDivisors(i); if(di > i && sumOfDivisors(di) == i) ) yield (Pair(i, di));


When executed this yields the following output:


scala> for (i <- 0 until 10000; di = sumOfDivisors(i); if(di > i && sumOfDivisors(di) == i) ) yield (Pair(i, di));
res2: Seq.Projection[(Int, Int)] = RangeMFM((220,284), (1184,1210), (2620,2924), (5020,5564), (6232,6368))

17 Jan 2009

Project Euler problem 3 using Scala

I've been looking at Euler problem number 3 for a while, and came up with the simplest solution I could imagine that works. So simple in fact, that the Scala experience was a bit disappointing, the same implementation could easily be done in Java, C, C#, Python, etc, etc. However, no real reason to complicate things unnecessary, so here's the code:


class Euler3 {

def maxFactor(number: Long, factor: Int): Int = {

if (factor >= number) factor
else if (number % factor == 0) maxFactor(number / factor, factor)
else maxFactor(number, factor + 1)
}
}
object Euler3 {

def main(args: Array[String]): Unit = {
println("maxFactor" + new Euler3().maxFactor(317584931803L, 2))
}
}


What it does is factorizing the given number by the natural numbers starting at 2. Whenever the number can be divided by the factor, the function is called recursively with the result of this division. If the number is cannot be divided by the factor, the factor is increased by one and again the function is called recursively. This continues until the factor and the resulting number are equal.
As a simple example, lets find the largest prime factor of 100.
First it is divided twice by 2, yielding 25. After this, it cannot be divided by 2 any longer, so the factor is increased to 3 and 4 (both not applicable) and eventually 5. Then 25 is divided by 5 exactly 5 times, yielding 5 as the resulting value.
Simple but effective.

16 Jan 2009

Project Euler problem 2 using Scala

I wanted to use Haskell's zipWith funtion to solve Euler's problem 2 using Scala. This provides an elegant way to generate Fibonacci sequences lazyily, as described here. However, no function zipWith is yet available in Scala until version 2.8.0, according to this ticket. On of Scala's beauties is that, if a function on a class is not available, you can easily add it yourself using an implicit function.
Code below is largely stolen from this post by Jorge Ortiz, in which he also explains in the functions and classes in more detail. My simple addition is just another bit of library pimping, by adding an implicit withZip function:


class Euler2 {

implicit def streamWithZipWith(stream: Stream[Int]) = new {
def zipWith(that: Stream[Int])(f: (Int, Int)=>Int) = {
stream zip that map { case (x, y) => f(x, y) }
}
}

def fib: Stream[Int] = {
lazy val fibs: Stream[Int] = Stream.cons(0, Stream.cons(1, (fibs.zipWith(fibs.tail)(_ + _)) ))
fibs
}

}

object Euler2 {

implicit def iterableWithSum(it: Iterable[Int]) = new {
def sum = it.foldLeft(0)(_ + _)
}

def main(args: Array[String]): Unit = {
val fibStream = new Euler2().fib
fibStream.take(10).print
fibStream.filter(_ % 2 == 0).takeWhile(_ <= 1000000).sum
}
}




The Stream class is handy to construct a List of elements that are evaluated lazily, i.e. only when they are actually needed. This allows us to construct an infinite list definition, and later only use a subset of our infinite list for the real calculation.

The zipWith implicit function definition, is defined so that we can call it on our fibs Stream variable. Our zipWith function operates on two Streams, first zips them, which creates a Stream of tuples of elements in both streams. On that resulting tuple Stream, the map function is applied to each tuple. The function that is applied is passed on as an argument. In our case what we want is to add the two elements from the tuple to construct the fibonacci sequence. Basically the same code as in Jorge's post, but it shows how you can quickly and cleanly add your desired functions to an existing class.

15 Jan 2009

Project Euler problem 1 using Scala

As a small exercise in getting to grips with the Scala language, here's a solution to Euler's problem nr 1.



class Euler1 {
def generateNumbers(): List[Int] = {
List.range(1, 1000).filter(isSatisfied(_))
}

def isSatisfied(i: Int): Boolean = {
i % 3 == 0 || i% 5 == 0
}
}

object Euler1 {
def main(args: Array[String]): Unit = {
val generatedNumbers = new Euler1().generateNumbers
println("Terms: " + generatedNumbers)
print("Sum of terms " + generatedNumbers.foldLeft(0)(_ + _))
}
}