## Scala for Project Euler

Project Euler is a collection of interesting computational problems intended to be solved with computer programs. Most of the problems challenge your skills in algorithm design rather than your knowledge of mathematics.

Thanks to short concrete problems and number-only solutions you don’t have to thinker with IDEs, GUI designers, programming libraries and frameworks, so Project Euler is an excellent tool for learning a new programming language or improving your core programming skills.

### Why use Scala

Although all general-purpose programming languages are Turing-complete and thus suitable for Project Euler, each language has its own philosophy and set of tools. In spite of programming language “holy wars”, the truth is that different tasks demand different tools.

Since Scala is a multi-paradigm programming language, it allows programmers to efficiently express a wide range of common programming patterns. Most Project Euler problems imply advanced transformation of numeric or symbolic data and Scala’s functional programming features are the perfect tool for that purpose (moreover, unlike pure functional languages, being a hybrid language, Scala provides object-oriented capabilities when modeling or simulation is required).

So, what does Scala have to offer for Project Euler? Here is the list of most valuable features:

- scripting,
- type-inference,
- first-class functions,
- tail call optimization,
- lazy evaluation,
- excellent collection library,
- sequence comprehensions.

On the top of everything else, Scala brings enjoyment to your coding. According to The Right Tool Scala is ranked high in the following categories:

- I enjoy using this language (2/50)
- I use this language out of choice (1/50)
- This language is expressive (3/50)
- I find code written in this language very elegant (2/50)

Thus Scala is the right tool for those who want to mingle the useful with the pleasant.

### Sample solutions

This section contains solutions to the first 33 problems. You may use them either to size up how well Scala plays in Project Euler, or to compare your own solutions with the samples.

Keep in mind, that the purpose of these solutions is to demonstrate Scala in the first place, so the problems are just a “canvas” to show the elegance and expressiveness of the language. Many times I intentionally preferred a direct and concise solution (if it performs reasonably fast) to a “math-savvy” one.

All the code is available as a GitHub repository.

See also: Ninety-Nine Problems in Scala, Java, Clojure and Haskell.

val r = (1 until 1000).view.filter(n => n % 3 == 0 || n % 5 == 0).sum assert(r == 233168) // 7 ms

lazy val fs: Stream[Int] = 0 #:: 1 #:: fs.zip(fs.tail).map(p => p._1 + p._2) val r = fs.view.takeWhile(_ <= 4000000).filter(_ % 2 == 0).sum assert(r == 4613732) // 1 ms

def factors(n: Long): List[Long] = (2 to math.sqrt(n).toInt).find(n % _ == 0) .map(i => i.toLong :: factors(n / i)).getOrElse(List(n)) val r = factors(600851475143L).last assert(r == 6857) // 1 ms

val r = (100 to 999).view .flatMap(i => (i to 999).map(i *)) .filter(n => n.toString == n.toString.reverse) .max assert(r == 906609) // 102 ms

val r = Range(20, Int.MaxValue) .find(n => Range(2, 21).forall(n % _ == 0)).get assert(r == 232792560) // 23 s

val numbers = 1 to 100 def square(n: Int) = n * n val r = square(numbers.sum) - numbers.map(square).sum assert(r == 25164150) // 1 ms

^{st}prime.*

lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i => ps.takeWhile(j => j * j <= i).forall(i % _ > 0)) val r = ps(10000) assert(r == 104743) // 24 ms

val s = """<raw input data>""" val r = s.filter(_.isDigit).map(_.asDigit).sliding(5) .map(_.product).max assert(r == 40824) // 33 ms

val limit = (1 to 1000).find(n => n + math.sqrt(n) >= 1000).get val rs = for(b <- 2 until limit; a <- 1 until b; c = 1000 - a - b if a * a + b * b == c * c) yield a * b * c val r = rs(0) assert(r == 31875000) // 32 ms

lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i => ps.takeWhile(j => j * j <= i).forall(i % _ > 0)) val r = ps.view.takeWhile(_ < 2000000).foldLeft(0L)(_ + _) assert(r == 142913828922L) // 1 s

val s = """<raw input data>""" val ns = s.split("\\s+").map(_.toInt) def m(i: Int, p: Int, c: Int): Int = if(c > 0) ns(i) * m(i + p, p, c - 1) else 1 def ms(xs: Seq[Int], ys: Seq[Int], p: Int) = ys.flatMap(y => xs.map(x => m(20 * y + x, p, 4))) val ps = ms(0 to 19, 0 to 15, 20) ++ ms(0 to 15, 0 to 19, 1) ++ ms(0 to 15, 0 to 15, 21) ++ ms(3 to 19, 0 to 15, 19) val r = ps.max assert(r == 70600674) // 4 ms

lazy val ts: Stream[Int] = 0 #:: ts.zipWithIndex.map(p => p._1 + p._2 + 1) def p(t: Int) = Range(1, Int.MaxValue) .takeWhile(n => n * n <= t) .foldLeft(0)((s, n) => if(t % n == 0) s + 2 else s) val r = ts.find(p(_) > 500).get assert(r == 76576500) // 1 s

val s = """<raw input data""" val r = s.split("\\s+").map(_.take(11).toLong).sum.toString .take(10).toLong assert(r == 5537376230L) // 2 ms

def from(n: Long, c: Int = 0): Int = if(n == 1) c + 1 else from(if(n % 2 == 0) n / 2 else 3 * n + 1, c + 1) val r = (1 until 1000000).view.map(n => (n, from(n))) .reduceLeft((a, b) => if(a._2 > b._2) a else b)._1 assert(r == 837799) // 1 s

def f(row: Seq[Long], c: Int): Long = if (c == 0) row.last else f(row.scan(0L)(_ + _), c - 1) def r(n: Int) = f(Seq.fill(n + 1)(1L), n) assert(r(20) == 137846528820L) // 1 ms

^{1000}?*

val r = BigInt(2).pow(1000).toString.view.map(_.asDigit).sum assert(r == 1366) // 1 ms

val units = Array(0, 3, 3, 5, 4, 4, 3, 5, 5, 4, 3, 6, 6, 8, 8, 7, 7, 9, 8, 8) val tens = Array(0, 0, 6, 6, 5, 5, 5, 7, 6, 6) lazy val name: Int => Int = { case n if(n < 20) => units(n) case n if(n < 100) => tens(n / 10) + (if(n % 10 > 0) units(n % 10) else 0) case n if(n < 1000) => name(n / 100) + 7 + (if(n % 100 > 0) 3 + name(n % 100) else 0) case 1000 => 11 } val r = (1 to 1000).map(name).sum assert(r == 21124) // 1 ms

val s = """<raw input data""" val grid = s.trim.split("\n").map(_.split("\\s+").map(_.toInt)) def f(rows: Array[Array[Int]], bottom:Seq[Int]): Int = { val ms = bottom.zip(bottom.tail).map(p => p._1 max p._2) val ss = rows.last.zip(ms).map(p => p._1 + p._2) if(ss.size == 1) ss.head else f(rows.init, ss) } val r = f(grid.init, grid.last) assert(r == 1074) // 2 ms

val lengths = Array(31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31) val ls = for(y <- 1900 to 2000; m <- 1 to 12) yield if(m == 2) if (y % 4 == 0 && (y % 100 != 0 || y % 400 == 0)) 29 else 28 else lengths(m - 1) val fs = ls.scanLeft(1)((ws, l) => (ws + l) % 7) val r = fs.drop(12).take(1200).count(_ == 0) assert(r == 171) // 2 ms

def f(n: BigInt): BigInt = if(n < 2) 1 else n * f(n - 1) val r = f(100).toString.view.map(_.asDigit).sum assert(r == 648) // 1 ms

val ds = (0 until 10000).view .map(n => (1 to (n / 2)).filter(n % _ == 0).sum) val as = ds.zipWithIndex.collect { case (n, i) if n < 10000 && ds(n) != n && ds(n) == i => i } val r = as.sum assert(r == 31626) // 658 ms

val r = io.Source.fromFile("names.txt").mkString.split(",") .map(_.init.tail).sorted.map(_.map(_ - 64).sum) .zipWithIndex.map(p => p._1 * (p._2 + 1)).sum assert(r == 871198282) // 38 ms

val as = (0 to 28123).map(n => (1 to (n / 2)).filter(n % _ == 0).sum) .zipWithIndex.filter(p => p._1 > p._2).map(_._2) val exc = as.view.flatMap { a => as.takeWhile(_ <= (28123 - a)).map(a +) } val r = (1 to 28123 diff exc).sum assert(r == 4179871) // 5 s

def ps(s: String): Iterator[String] = if (s.length == 1) Iterator(s) else s.toIterator.flatMap(c => ps(s.filter(c !=)).map(c +)) val r = ps("0123456789").drop(999999).next().toLong assert(r == 2783915460L) // 712 ms

lazy val fs: Stream[BigInt] = 0 #:: 1 #:: fs.zip(fs.tail).map(p => p._1 + p._2) val r = fs.view.takeWhile(_.toString.length < 1000).size assert(r == 4782) // 468 ms

val ps = (2 until 1000).map(i => (1 to 2000) .find(BigInt(10).modPow(_, i) == 1)) val r = 2 + ps.indexOf(Some(ps.flatten.max)) assert(r == 983) // 2 s

`n`.*

lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i => ps.takeWhile(j => j * j <= i).forall(i % _ > 0)) def isPrime(n: Int) = ps.view.takeWhile(_ <= n).contains(n) val ns = (-999 until 1000).flatMap { a => (-999 until 1000).map(b => (a, b, (0 to 1000).view .takeWhile(n => isPrime(n * n + a * n + b)).size)) } val t = ns.reduceLeft((a, b) => if(a._3 > b._3) a else b) val r = t._1 * t._2 assert(r == -59231) // 6 s

def cs(n: Int, p: Int): Stream[Int] = (n * 4 + p * 10) #:: cs(n + p * 4, p + 2) val r = 1 + cs(1, 2).take(500).sum assert(r == 669171001) // 1 ms

val r = (2 to 100).flatMap(a => (2 to 100) .map(b => BigInt(a).pow(b))).distinct.size assert(r == 9183) // 17 ms

def max(d: Int) = math.pow(10, d).toInt - 1 def sum(n: Int) = n.toString.map(_.asDigit) .map(math.pow(_, 5).toInt).sum val limit = Stream.from(1).find(d => max(d) > sum(max(d))).get val r = (2 to max(limit)).view.filter(n => n == sum(n)).sum assert(r == 443839) // 2 s

def f(ms: List[Int], n: Int): Int = ms match { case h :: t => if (h > n) 0 else if (n == h) 1 else f(ms, n - h) + f(t, n) case _ => 0 } val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200) assert(r == 73682) // 15 ms

val ms = for { a <- 2 to 10000; b <- 2 to 10000 / a m = a * b; s = a.toString + b + m if s.length == 9 && (1 to 9).mkString.forall(s.contains(_)) } yield m val r = ms.distinct.sum assert(r == 45228) // 73 ms

val rs = for(i <- 1 to 9; j <- (i + 1) to 9; k <- 1 to 9; if k * (9 * i + j) == 10 * i * j) yield (10 * i + j, 10 * j + k) val p = rs.reduceLeft((n, d) => (n._1 * d._1, n._2 * d._2)) def gcd(n: Int, d: Int): Int = if (d == 0) n else gcd(d, n % d) val r = p._2 / gcd(p._1, p._2) assert(r == 100) // 5 ms

Pavel, thanks so much for this post — I’m learning Scala and it is interesting to look at better solutions than my own to these problems. I referred to this page in this post about a generalization of problem 1.

I have a question, though — why do you call view() in your solutions? At least for problem 1, the code works without it — how does calling view() help?

Views allow to avoid constructing intermediate results of data transformations. This improves performance and optimizes memory usage.

Here’s an excellent explanation of how views work.

Super, thank you a lot for your solutions.

Great post! Thanks!

Great writeup :). I started learning Scala a few days ago and your Project Euler examples have been most helpful in understanding the functional aspect of the Scala syntax. I’m looking forward to reading more of your Scala related posts in the future (this was the first one, correct?). That being said, I also cooked up an alternative solution for problem 5 and figured you might like it

val r = (1l to 20l).reduceLeft {

(a,b) => {

def gcd(a: Long, b: Long): Long = if (b == 0) a.abs else gcd(b, a % b)

(a*b) / gcd(a,b) // least common multiple

}

}

I don’t know if the use of view really help, but for problem 1 the following code gives the same result and is clearly faster:

var r = 0; for(i <- 1 until 1000; if((i % 3 == 0) || ( i % 5 == 0))){ r += i }

It’s great that you’re advocating Scala use for Project Euler problems but they’ve asked that people not post the solutions to the problems on other websites. What’s the point of getting your fingers wet with the first few problems if you never really have to solve things. Granted, these problems are easy but it’s not like with a few minutes of thought they can’t be solved.

>It’s great that you’re advocating Scala use for Project Euler problems but they’ve asked that people not post the solutions to the problems on other websites.

I found no evidence that Project Euler team is opposed to sharing solutions on third-party sites. The solutions here is to demonstrate Scala in the first place, rather than Project Euler itself. I hope my examples will help people to understand Scala better (and will not be used for cheating).

> I also cooked up an alternative solution for problem 5 and figured you might like it

Nice! The code is still concise and “functional” but it runs much faster than mine.

> for problem 1 the following code gives the same result and is clearly faster…

“No vars” is the first rule of idiomatic Scala

Scala encourages “functional style” of programming, with no mutable states and no side-effects. I recommend you to check “Next steps in Scala / Learn to recognize the functional style” in “Programming in Scala” book.

Scala is an hybrid imperative/functional language, so even if the use of vals is encouraged, “No vars” is not an absolute rule.

Quoting “Programming in Scala”, you have to prefer using val as much as possible unless “you have a specific need and justification for them”. Well in this case it is just 2 to 3 times faster (a potentially valid justification to me), and the whole method still has no side effects.

Just to say that the pure functionnal style programming may be the most elegant, but not always the most efficient. When you deal with time critical code, it may be important to have this in mind.

To complement my previous message, an interesting project is ScalaCLPlugin:

https://code.google.com/p/scalacl/wiki/ScalaCLPlugin

“The ScalaCL Compiler Plugin optimizes simple generalistic Scala loop-like calls by transforming them into equivalent while loops, which are much faster.”

So even with pure functionnal programming, you could potentially obtain good performances.

It could be interesting to compare the performances with and without the use of this compiler plugin.

Some interesting code, but I was wondering why you are using lazy vals? The examples run the same without the vals being lazy…

Mark, lazy modifiers are needed to prevent “forward reference extends over definition of value” compilation error when such code is put into a method (like “main”).

Of course. I have a memory like a sieve. I was bitten by this a couple of years ago.

Thanks.

Hi, thanks for posting your solutions. They are very useful for comparing against my own and learning new techniques.

I have a mundane question: how do you run these? In the REPL, in an IDE? Do you package them in individual objects that extend App, or do you have a separate object that calls them and displays the result?

Rhys, I usually run such code directly, either from command line (“scala problem1.scala”) or from IntelliJ IDEA, which supports running Scala scripts.

Additionally, I used a simple application to measure code execution time (to exclude JVM and Scala startup time).

Where can I find information about the “simple application to measure code execution time”?

I guess that this always works (example for problem #1):

val timeBgn: Long = System.currentTimeMillis()

val r = (1 until 1000).view.filter(n => n % 3 == 0 || n % 5 == 0).sum

val timeRun = System.currentTimeMillis() – timeBgn

assert(r == 233168)

Tom, there are a lot of subtleties in benchmarking such code. Although I have used a plain main method with a preliminary “warming up” (5-10 idle iterations), you may also check something like caliper Microbenchmarking framework.

[...] the “official” solutions seemed a bit complex. This was a while ago and looking at some example solutions, I think it’s just a matter of understanding some new concepts, like what a Stream[int] is [...]

Hi,

I’m looking at your solution for problem 19 and it really buggles my mind why for last 3 months you have 31 days entered in lengths array. Moreover, it gives proper result, so I guess there must be some point which I don’t understand.

Greetigs

Micheal, there was a trick bug in the solution to Problem 19, which is now fixed Thank you for noticing it!

Problem 3 limit calculation is incorrect.

Assuming the limit is the square root of the value leads to excluding correct values.

Replacing “600851475143L” by “58″ is a perfect example of this. The code will return 2 as the largest prime divisor instead of 29.

All divisors for a number n are in (1 -> n/2) not in (1 -> sqrt(n)).

Stephane, that’s true. I’ve updated the solution. Thank you!

[...] learn more take a look at this blog -> Scala for Project Euler. [...]

[...] may also see Scala for Project Euler for more examples of Scala [...]

Your solution for problem 1 is naive.

Scala solution is elegant, but school math is faster

What about n=1000000000?

There is O(1) solution, just use three sums of arithmetic progressions.

Sum of elements (1 to n), with step 3 + Sum of elements (1 to n), with step 5, minus sum of elements with step 15

object One {

def main(args: Array[String]) {

sumMultiples(2)

sumMultiples(10)

sumMultiples(14)

sumMultiples(15)

sumMultiples(16)

sumMultiples(20)

sumMultiples(1000)

sumMultiples(10000000)

}

// Solution is O(1)

def sumMultiples(n: Long) {

println(“Sum(%s)=%s”.format(n, sum(n, 5) + sum(n, 3) – sum(n, 15)))

}

// sum of arithmetic progression from divider to N-1

def sum(N: Long, div: Long): Long = {

val a1 = div

val an = N – 1 – (N – 1) % div // last element of progression

val n = 1 + (an – a1) / div // num elements of progression

(a1 + an) * n / 2

}

}

Hi Vitalii! Thank you for the valuable addition. However, the purpose of these solutions is to demonstrate Scala in the first place, so the problems are just a “canvas” to show the elegance and expressiveness of the language. Many times I intentionally preferred a direct and concise solution (if it performs reasonably fast) to a “math-savvy” one (I’ve added this clarification to the post).

Your solution to 24 runs out of memory for me. I believe this issue is that String.flatMap is strict, so your ps generates all the permutations. This worked for me:

def ps(s: Seq[Char]): Seq[String] =

if(s.size == 1) Seq(s.head.toString) else s.flatMap(c => ps(s.filterNot(_ == c)).map(c +))

ps(“0123456789″.view)(999999)

Your solution to 15 is a great place to use scan:

def f(row:List[Long], c:Int):Long =

if (c == 0) row.last else f(row.scan(0L)(_+_), c-1)

def r(n:Int) = f(List.fill(n+1)(1L),n)

assert(r(20) == 137846528820L)

Hi Peter! That’s a good point. We neither need to compute all the permutations, nor we need to hold all the previous values in memory. However it’s better to avoid the implicit dependency on the initial sequence implementation by using iterators (which also significantly improves the performance of the algorithm).

Peter, as for the Problem 15, I agree that the “scan” method is most appropriate there. I’ve updated the solution. Thanks!

P. S. After more than 3 years, I can easily see many more potential improvements to the solutions

def specialPythagoreanTriplet: BigInt = {

@tailrec

def prods(a: Int, b: Int): BigInt = {

val c = 1000 – a – b

if ((a * a) + (b * b) == (c * c)) a * b * c

else if (a >= 1000) 0 // Not Found

else if (b >= 1000) prods(a + 1, a + 2)

else prods(a, b + 1)

}

prods(1, 2)

}

This is regarding problem 23.

I tried two versions of that problem:

Version 1:

def properDivisorsSum(n: Int): Int = (1 to n / 2).filter(n % _ == 0).sum

val abundantNumbers = (1 until 28123).filter(x => properDivisorsSum(x) > x)

val sumOfTwoAbundants = (for{

x <- abundantNumbers

y <- abundantNumbers.takeWhile(_ properDivisorsSum(x) > x)

val asView = abundantNumbers.view

val sumOfTwoAbundants = for{

x <- asView

y <- abundantNumbers.takeWhile(_ <= 28123 – x)

}yield x+y

(1 to 28123 diff sumOfTwoAbundants).sum

Both versions yield results and seems to be fine.

However, I am not clearly able to comprehend the exact optimisation of views here.

I went through the scala documentation on Views (http://docs.scala-lang.org/overviews/collections/views.html)

Trying to figure out where exactly the optimisation using views makes the difference.

Here are a few thoughts:

I believe in both cases, it is the last statement that makes the usage of "views" relevant. However, when I look at the statement,

y <- abundantNumbers.takeWhile(_ <= 28123 – x)

this should have already restricted my result values to less than 28123,

unless there is a good amount of repetition of same values and that is where optimisation using views help.

This are some ideas I have, but still feel something that is a clear picture is missing.

could you please let me know if this understanding is correct?

For some reasons,

versions did not come correctly:

here it is again:

Version 1:

def properDivisorsSum(n: Int): Int = (1 to n / 2).filter(n % _ == 0).sum

val abundantNumbers = (1 until 28123).filter(x => properDivisorsSum(x) > x)

val asView = abundantNumbers.view

val sumOfTwoAbundants = for{

x <- asView

y <- abundantNumbers.takeWhile(_ properDivisorsSum(x) > x)

val sumOfTwoAbundants = (for{

x <- abundantNumbers

y <- abundantNumbers.takeWhile(_ <= 28123 – x)

}yield x+y).view

//making it view helps us compute only the results until the 28123, not after that, so we

//are saved from computing numbers larger than 28123

(1 to 28123 diff sumOfTwoAbundants).sum

Hi Gaurav,

The whole point of using “views” is to avoid allocation of intermediate collections, and thus to save heap memory and to relieve GC from the excessive work.

We may consider using views when:

* collection size is relatively large,

* there’s no need for random-access or re-iteration.

The primary statement that relies on a view is the sumOfTwoAbundants calculation: for every abundant number we generate an additional _sequence_ of numbers (because the for-yield statement is translated into .flatMap call under the hood), so the total length of the resulting sequence is about (abundantNumbers.length ^ 2) / 2 (the exact length is 24294140).

Unless we use a view, we have to hold all those intermediate numbers in memory. As Scala collections don’t use specialization, every instance of Integer occupies 16 bytes of memory (VM implementation-dependent), requiring about 370 MB of heap memory, which, aside from being pointless, leads to an OutOfMemoryError under default JVM heap size (256 MB).

When we call .view beforehand, we guarantee that all subsequent monadic transformations (like .flatMap) of the sequence will be resulted in just another “view”, so they can be performed in constant space.

Another option here is to replace .view with .toSet, which can also help to reduce the number of allocated integers.

Hi Pavel,

Thanks for the reply. It helps.