Friday, August 13, 2010

Project Euler in Scala

I had recently bought Programming in Scala book. It's a good book but you have to get your hands dirty after a while, especially because of the depth of the language itself.

Project Euler is a website with all kinds of math and computer programming problems; great for trying things out with a new programming language.

I am not attempting to pull every Scala trick in the solutions. Besides, sometimes the good old way of doing things is more readable to the 'untrained' eye.

So far I have solved the first four problems.

Here they are:

package euler.problem1

/**
* If we list all the natural numbers below 10 that are multiples of 3 or 5,
* we get 3, 5, 6 and 9. The sum of these multiples is 23.
*
* Find the sum of all the multiples of 3 or 5 below 1000.
*/
object SumOfMultiples {

def main(args : Array[String]) {

var sum = 0
1 to 999 filter (x => x % 3 == 0 || x % 5 == 0 ) foreach(x => sum += x)
println(sum)

}


package euler.problem2

/**
* Each new term in the Fibonacci sequence is generated
* by adding the previous two terms. By starting with 1 and 2,
* the first 10 terms will be:
*
* 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
*
* Find the sum of all the even-valued terms in the
* sequence which do not exceed four million.
*/
object Fibonacci {

def main (args : Array[String]) {
var s : Int = 0
fibonacci(0, 1, x => {if (x % 2 == 0) { s += x }; x <= 4000000} )
println(s)
}

def fibonacci (x : Int, y : Int, sum : (Int) => Boolean) {
val z = x + y
if (sum(z)) {
fibonacci(y, z, sum)
}
}
}


package euler.problem3

/**
* The prime factors of 13195 are 5, 7, 13 and 29.
*
* What is the largest prime factor of the number 600851475143 ?
*/
object PrimeFactor {

def main (args : Array[String]) {

var value = 600851475143L
var factorial = 2

while(value != 1) {
if(isFactorial(factorial, value)) {
value /= factorial
}
factorial += 1
}

println(factorial)
}

def isFactorial(factorial:Long, value:Long) : Boolean =
isPrime(factorial) && value % factorial == 0

def isPrime(n:Long) : Boolean =
(2L until Math.sqrt(n).asInstanceOf[Long]) forall (n % _ != 0)

}


/**
* A palindromic number reads the same both ways.
* The largest palindrome made from the product of two
* 2-digit numbers is 9009 = 91 × 99.
*
* Find the largest palindrome made from the product of
* two 3-digit numbers.
*/
package euler.problem4

object Palindrome {

def main (args : Array[String]) {

var largest = 0;
for(x <- 1 to 999 reverse; y <- 1 to 999 reverse) {
val prod = x * y
if(prod > largest) {
val pStr = String.valueOf(prod)
if (pStr == pStr.reverse) largest = prod
}
}
println(largest)
}
}

No comments: