Friday, December 28, 2007

Fun with Project Euler and Scala

Project Euler is a site with mathematical puzzles that can be solved relatively quickly with an efficient algorithm. Randall Munroe (of xkcd fame), used Project Euler to become more acquainted with Python, so I thought I'd give it a shot in Scala. I'll be using the Scala interpreter, which comes with any standard Scala installation.

Familiarity with Scala is not necessarily required, as I've attempted to also make this a whirlwind tour of some of Scala's more interesting features: implicit conversions, anonymous functions, anonymous parameters, type inference, lazy evaluation, Pimped Libraries, and sequence comprehensions. I also go through some of the methods in Scala's standard library, particularly for some of the collection classes. I don't attempt to explain all these things in detail, but I've provided links for the curious.

Warning: Puzzle spoilers ahead. Also, these algorithms are by no means optimal, but they're "fast enough" and they get the job done.

Problem 1: Find the sum of all the multiples of 3 or 5 below 1000.

This is fairly easy. The until method (defined on Ints via an implicit conversion to RichInt) lets us construct ranges of numbers.


scala> 1 until 10
res5: Range = Range(1, 2, 3, 4, 5, 6, 7, 8, 9)

We can use the filter method to grab only those numbers that are multiples of 3 or 5.


scala> (1 until 10).filter(n => n % 3 == 0 || n % 5 == 0)
res6: Seq.Projection[Int] = RangeF(3, 5, 6, 9)

We're using Scala's syntax for anonymous functions. If you're unfamiliar with Scala, it might seem like "n" is dynamically typed. In fact, Scala's type inference allows "n" to be statically typed (as an Int) at compile time, even though we omitted the type declaration.

And finally we can use foldLeft to sum up all the numbers.


scala> (1 until 1000).filter(n => n % 3 == 0 || n % 5 == 0).foldLeft(0)(_ + _)
res2: Int = 233168

Here the underscores in (_ + _) act as anonymous parameters for an anonymous function. The first underscore represents the first parameter, and the second underscore represents the second parameter. Pretty cool!

Problem 2: Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed one million.

First we need to define the Fibonacci sequence. We'll define it lazily using Scala's "lazy" construct and the Stream class.


scala> lazy val fib: Stream[Int] = Stream.cons(0,
| Stream.cons(1, fib.zip(fib.tail).map(p => p._1 + p._2)))
fib: Stream[Int] = Stream(0, ?)

This manually defines the first two terms of the Fibonacci sequence, then recursively defines an infinite stream of the remaining Fibonacci terms. fib is the Fibonacci sequence starting at zero (0, 1, 1, 2, 3, ...). fib.tail is the Fibonacci sequence starting at one (1, 1, 2, 3, 5, ...). fib.zip(fib.tail) is the two sequences zipped into a sequence of pairs ((0, 1), (1, 1), (1, 2), (2, 3), ...). We then use map to sum the two parts of each pair (._1 and ._2) and complete the recursive definition of the rest of fib, after the first two terms (1, 2, 3, 5, ...).

Thanks to Stream, the terms of the Fibonacci sequence are only evaluated as they are needed, so we can represent an infinite stream without incurring infinite computation.

We can verify that we computed the Fibonacci numbers correctly by inspecting the first few terms of our Stream with take and print.


scala> fib.take(15).print
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, Stream.empty

That looks about right. Now lets filter so we only have the even-valued Fibonacci terms, use takeWhile to grab the terms below a million, and add them up. Since I'm getting tired of foldLeft, let's Pimp my Library and add a "sum" method to our Fibonacci sequence (indeed, to any Iterable[Int]).


scala> implicit def iterableWithSum(it: Iterable[Int]) =
| new { def sum = it.foldLeft(0)(_ + _) }
iterableWithSum: (Iterable[Int])java.lang.Object{def sum: Int}

scala> fib.filter(_ % 2 == 0).takeWhile(_ <= 1000000).sum
res8: Int = 1089154

Problem 3: What is the largest prime factor of the number 317584931803?

We could define an infinite stream of prime numbers using the Sieve of Eratosthenes or some other technique for finding prime numbers, but this example is simple enough that we don't have to bother.

Let's recursively define an infinite stream of natural numbers and verify that it works as we intend.


scala> lazy val naturals: Stream[Int] = Stream.cons(1, naturals.map(_ + 1))
naturals: Stream[Int] = Stream(1, ?)

scala> naturals.take(10).print
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, Stream.empty

If we define the number we want to factor as a mutable var, we can use a combination of functional and imperative programming (fairly unique to Scala) to find the largest prime factor.


scala> var theNum = 317584931803L
theNum: Long = 317584931803

scala> naturals.drop(1).dropWhile(n => {while(theNum % n == 0) {theNum /= n}; theNum > 1})
res0: Stream[Int] = Stream(3919, ?)

We keep dividing down theNum until it has no factors left, then we return the last (largest) factor we used. By definition all the factors we divide by will be prime.

scala> naturals.dropWhile(n => if (theNum % n != 0) true else {theNum /= n; theNum > 1})

If a natural number is not a divisor of theNum, we drop it. If it is a divisor, we divide-and-update theNum, and drop it if theNum is still greater than 1. By updating theNum, we assure that all the divisors we find are prime. By stopping when theNum reaches 1, then the first number in our remaining stream will be the largest prime factor we want.


Problem 4: Find the largest palindrome made from the product of two 3-digit numbers.

We'll need to check for palindromes, so this could come in handy:


scala> def isPalindrome(s: String): Boolean = s.reverse.mkString == s
isPalindrome: (String)Boolean

scala> isPalindrome("1001")
res46: Boolean = true

We can use sequence comprehensions to generate all the products of three digit numbers that are palindromes.


scala> val palindromes = for (a <- (100 until 1000);
| b <- (a until 1000);
| val p = a*b if isPalindrome(p.toString))
| yield p
palindromes: Seq.Projection[Int] = RangeG(10201, 11211, 12221, 13231...

Now we can sort and grab the largest palindrome with head.


scala> palindromes.toList.sort(_ > _).head
res52: Int = 906609

Problem 5: What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

I'm going to cheat here, because this is easier to do by hand:


scala> 2*3*2*5*7*2*3*11*13*2*17*19
res0: Int = 232792560

And that's a little fun with Project Euler and Scala!

25 comments:

Daniel Green said...

Fantastic Blog!

Jörn Zaefferer said...

Great post and an interesting approach to learn Scala.

My solution to problem 6 (What is the difference between the sum of the squares and the square of the sums?):

var sum = (1 until 101).foldLeft(0)(_ + _);
var squareSum = sum * sum

var sumSquare: Int = 0
(1 until 101).foreach(n => sumSquare += n*n)
println(squareSum - sumSquare)

The output is correct, but I'm sure the solution could be improved a lot. I'm curious to see yours.

Daniel Green said...

scala> (1 until 1000).foldLeft(0)((old, next) => old + (if (next % 3 == 0 || next % 5 == 0) next else 0))
res5: Int = 233168

// Might run slightly faster as it only iterates through the array once

Jorge Ortiz said...

Jörn:

I would use "to" instead of "until", since it's inclusive.

Once again, pimping my Iterable[Int] with a "sum" method:

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

Except this time the result is coerced to be a BigInt, so I can take advantage of the "pow" method on BigInt.

Then:

(1 to 100).sum.pow(2) - (1 to 100).map(n => n*n).sum

Daniel:

Yes, that does use fewer instructions. The asymptotic complexity is unchanged though.

Also:

It has been brought to my attention that my original solution to Problem 3 was buggy, as it assumed that each prime factor only occurred once in the factorization. I've updated the blog post with a bug fix.

Oscar Picasso said...

A more imperative solution to problem 2 for a gentle introduction to scala for java programmers ;)

Your solution feels more idiomatic scala though.

class FiboIter extends Iterator[Int] {
var pp = 0
var p = 1
val hasNext = true
def next = {
val curr = pp + p
pp = p
p = curr
curr
}
}
println(new FiboIter().
takeWhile(_ <= 1000000).
filter(_ % 2 == 0).
foldLeft(0)(_ + _))
}

By the way the problem stated "... which do not exceed one million...". So I think that the takeWhile function argument should take the <= operator not <. But in that case it didn't change the result.

Jorge Ortiz said...

Oscar:

Thanks for catching the <= bug! I've fixed it in the post.

And you're correct, Scala allows for both functional and imperative approaches. An even -more- imperative solution (no iterators, anonymous functions, filters, or folds) would be:

var sum = 0
var curr = 1
var prev = 0

while (curr <= 1000000) {
if (curr % 2 == 0)
sum += curr

val next = curr + prev
prev = curr
curr = next
}

Console.println(sum)

Oscar Picasso said...

For problem 3, this one is very fast (75 ms on my computer).

I started with something more complicated and realized that it was very slow for big numbers. The interesting thing is that I discovered a much simpler solution while trying to optimize.

def largestPrimeFactor(n: Long): Long = {
val p = Stream.from(2).
takeWhile(_ <= n).
filter((x) => n % x == 0).
head
if (p == n) n
else largestPrimeFactor(n / p)
}

println(largestPrimeFactor(317584931803L))

Oscar Picasso said...

Actually even the takeWhile method is unnecessary.

def largestPrimeFactor(n: Long): Long = {
val p = Stream.from(2).
filter(n % _ == 0).head
if (p == n) n
else largestPrimeFactor(n / p)
}

println(largestPrimeFactor(317584931803L))

Michel S. said...

Great article! Haven't noticed Project Euler before, and now I'm hooked. Having used functional languages for several years, your post serves as a nice introduction to Scala-isms.. I've been finding the syntax a bit unnatural, and having concrete examples to compare my solutions to, makes the learning process easier.

Any idea how to do problem 7 in Scala? In Haskell I can just use the Sieve of Eratosthenes and drop the first 10,000 prime numbers, but in Scala I ran out of heap space.

Jorge Ortiz said...

Michel:

I too found that the Sieve of Eratosthenes lost its usefulness after a while. Thankfully, Java's math library has a BigInteger class with a "nextProbablePrime" method. Converting between Java's BigInteger and Scala's BigInt is a bit of a pain, but you can do the following:

scala> lazy val primes: Stream[BigInt] = Stream.cons(BigInt(2), primes.map(b => new BigInt(b.bigInteger.nextProbablePrime)))
primes: Stream[BigInt] = Stream(2, ?)

scala> primes drop 10000
res1: Stream[BigInt] = Stream(104743, ?)

If you define some implicits than the definition for primes becomes a lot prettier.

scala> implicit def bigInt2BigInteger(b: BigInt) = b.bigInteger
bigInt2BigInteger: (BigInt)java.math.BigInteger

scala> implicit def bigInteger2BigInt(b: java.math.BigInteger) = new BigInt(b)
bigInteger2BigInt: (java.math.BigInteger)BigInt

scala> lazy val primes: Stream[BigInt] = Stream.cons(2, primes.map(_.nextProbablePrime))
primes: Stream[BigInt] = Stream(2, ?)

Hope this helps.

Michel S. said...

Ah, thanks. I guess that's good enough for the purpose of answering the question.

remco said...

is the answer of Problem 5: What is the smallest number that is evenly divisible by all of the numbers from 1 to 20
really the right answer?
9 is a number between 1 and 20 and your answer is not even divisible by 9. I am not sure what evenly divisible means.

Michel S. said...

evenly divisible is just divisible (i.e. producing no remainder when divided). Are you sure you checked the number properly? It is divisible by 9 -- if you look at the calculation, the number three appears twice in the multiplication list.

remco said...

You are right I was not looking good enough.

Seth Tisue said...

Thanks for this post — I've enjoyed comparing my solutions to yours.

I tried changing my solutions to use your implicit conversions, but hit the following problem getting my code to compile:

https://lampsvn.epfl.ch/trac/scala/ticket/733

As you can see, I thought it was a compiler bug, but Martin says the implicits ought be declared in such a way as to help the type inference a bit more. If I understand his suggestion correctly, it's better to write:

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

and in fact this made my compile problems go away.

Garrett Rowe said...

I know I'm a little late to the conversation. But I just wanted to present another take on the Sieve of Eratosthenes. Really its just a Scala translation of the Haskell algorithm posted here: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Caveat: I'm a Scala noob so this may not be idiomic Scala.

/**
* Returns an infinite stream of prime numbers.
* The algortihm is ported from the Haskell algorithm discussed in
* the "Genuine Sieve of Eratosthenes" by Melissa E. O'Neill
* fond here: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
*/
def primes : Stream[Int] =
{
def sieve(nums : Stream[Int], table : Map[Int, List[Int]])
: Stream[Int] =
{
val curr = nums.head
table.get(curr) match
{
case None => Stream.cons(curr
, sieve(nums.tail
, table.update(curr * curr, List(curr))))
case Some(v) => sieve(nums.tail
, v.foldLeft (table - curr)(reinsert (curr) _ ))
}
}

def reinsert(curr : Int) (table : Map[Int, List[Int]], prime : Int)
: Map[Int, List[Int]] =
{
val newVal = prime + curr
table.get(newVal) match
{
case None => table.update(newVal, List(prime))
case Some(v) => table.update(newVal, prime::v)
}
}
sieve(naturals tail, Map.empty)
}

Garrett Rowe said...

Ugh that looks horrible. See the formatted code here:
http://codepad.org/5RvHTTXB

Eastsun said...
This comment has been removed by the author.
Eastsun said...

My solution to Problem 7:
var ps:Stream[Int] = Stream.cons(2,
            Stream.from(3).filter{ n =>
              ps.takeWhile(p => p*p <= n).forall(n%_ !=0)
           })
ps(10000)
And there has some codes for Project Euler:
http://eastsun.javaeye.com/category/34059

Matt said...

Here's my solution to problem 5. I don't know if it gives correct results for all numbers, but it appears to work until the result exceeds the capacity of Int.

(1 to 20).foldLeft(1){ (product,n) =>
val r_raw = product % n
val r = if (r_raw == 0) n else r_raw
product * (if (n % r == 0) (n / r) else n)
}

David said...

I had fun with my solution to problem 6. By using implicits I made sum and square functions that work with either lists of numbers or single numbers, so they can be applied in either order:

implicit def int2list(i: Int) = List(i)
implicit def list2int(l: List[Int]) = l(0)

def sum(xs: List[Int]) = xs.foldLeft(0)(_+_)
def square(xs: List[Int]) = xs.map(x => x*x)

val xs = (1 to 100).toList
println((sum(square(xs)) - square(sum(xs))).abs)

ssmm987 said...

Awesome post, although I still prefer to use C#

inderjeet said...

Hello,

We are delighted to inform you that Codefest'11, the annual International online coding festival of Computer Engineering Society, IT-BHU, has been unveiled. CodeFest is a unique fest wherein concepts of mathematics, logic, artificial intelligence, algorithms, language syntax, etc. are required to be deployed in programming; these concepts manifest themselves in solving problems effectively and efficiently!

CodeFest was started last year. CodeFest'10 was a phenomenal success with participation from all over the globe. CodeFest'11 is geared up with some new and pepped up events, while maintaining the integrity of its standards.This year CodeFest has associated with Technex'11, the annual all India Technical Festival of IT-BHU, to expand its horizons.

Here is a brief description of the constituent online events:

* Mathmania: A mathematical puzzle contest that puts mathematical and computational skills to test.
* Manthan: An algorithm intensive programming contest that would require coders to tailor existing standard algorithms.
* Perplexed: A programming contest, aimed to test the knowledge of C, wherein codes will be rewarded against syntactic constraints.
* Ratespiel: A technical contest covering different areas of Computer Science.
* Virtual Combat: An educational game wherein teams of programmed robotic tanks will fight the battles for glory. Codes Do Fight! Watch this out.

Visit our website for more details.

Few exciting statistics about Codefest'10:

* 2354 registrations (including 128 professionals) from 680 different institutions, across 59 countries
* Some participants were among the winners of Google Code Jam, Top Coder SRMs and ACM ICPC
* Total prize money was a whopping amount of 260,000 INR!
* Codefest '10 was the largest online coding festival of the Indian subcontinent in 2010 in terms of prize money!
* Codefest'10 was the second largest online coding festival of the Indian subcontinent in 2010, next to Bitwise
* Gained recognition from several international organizations including Codechef, Adobe, British Telecom, TCS and IEEE

The Codefest'11 team has set out to unleash a yet another coding extravaganza. We hope that your participation would raise the level of competition in Codefest'11. Feel free to contact us at codefest@itbhu.ac.in or reach us personally at:

* Mohit Bansal mohit.bansal.cse06@itbhu.ac.in
* Saket Saurabh saket.saurabh.cse07@itbhu.ac.in

We wish you all the best for Codefest'11 and for your future endeavours.

Happy coding, and be free!

Regards,
Team Codefest
Visit us at http://itbhu.ac.in/codefest
Mail us at codefest@itbhu.ac.in
Check out our page at http://facebook.com/codefest
Follow us at http://twitter.com/c0defest/
Read our blog at http://itbhu.ac.in/codefest/blog

Do Watch The Virtual Combat Promotional Video:
http://www.youtube.com/watch?v=v1rY3tyTj50

Jason said...
This comment has been removed by the author.
scand1sk said...

For problem 5, an efficient algorithm using Euler's method to find GCD:

def gcd(a:Long,b:Long):Long={
val r=a%b
if(r==0)b else gcd(b,r)
}

(1l to 20l) reduce {(a,v)=>a*v/gcd(a,v)}