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