Scala for Project Euler

Scala logo, e^ipi + 1 = 0Project 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:

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:

Problem 1

Add all the natural numbers below one thousand that are multiples of 3 or 5.*

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

assert(r == 233168) // 7 ms

Problem 2

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.*

lazy val fs: Stream[Int] = 0 #:: fs.scanLeft(1)(_ + _)

val r = fs.view.takeWhile(_ <= 4000000).filter(_ % 2 == 0).sum

assert(r == 4613732) // 1 ms

Problem 3

Find the largest prime factor of a composite number.*

def factors(n: Long): List[Long] = (2 to math.sqrt(n).toInt)
  .find(n % _ == 0).fold(List(n))(i => i.toLong :: factors(n / i))

val r = factors(600851475143L).last

assert(r == 6857) // 1 ms

Problem 4

Find the largest palindrome made from the product of two 3-digit numbers.*

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

Problem 5

What is the smallest number divisible by each of the numbers 1 to 20?*

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

assert(r == 232792560) // 23 s

Problem 6

What is the difference between the sum of the squares and the square of the sums?*

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

Problem 7

Find the 10001st 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

Problem 8

Discover the largest product of five consecutive digits in the 1000-digit number.*

val s = """<raw input data>"""

val r = s.filter(_.isDigit).map(_.asDigit)
  .sliding(5).map(_.product).max

assert(r == 40824) // 33 ms

Problem 9

Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.*

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

assert(r == 31875000) // 32 ms

Problem 10

Calculate the sum of all the primes below two million.*

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

Problem 11

What is the greatest product of four numbers on the same straight line in the 20 by 20 grid?*

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

Problem 12

What is the value of the first triangle number to have over five hundred divisors?*

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

Problem 13

Find the first ten digits of the sum of one-hundred 50-digit numbers.*

val s = """<raw input data>"""

val r = s.split("\\s+").map(_.take(11).toLong).sum
  .toString.take(10).toLong

assert(r == 5537376230L) // 2 ms

Problem 14

Find the longest sequence using a starting number under one million.*

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

Problem 15

Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?*

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

Problem 16

What is the sum of the digits of the number 21000?*

val r = BigInt(2).pow(1000).toString.view.map(_.asDigit).sum

assert(r == 1366) // 1 ms

Problem 17

How many letters would be needed to write all the numbers in words from 1 to 1000?*

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

Problem 18

Find the maximum sum traveling from the top of the triangle to the base.*

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.length == 1) ss.head else f(rows.init, ss)
}

val r = f(grid.init, grid.last)

assert(r == 1074) // 2 ms

Problem 19

How many Sundays fell on the first of the month during the twentieth century?*

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.slice(12, 1212).count(_ == 0)

assert(r == 171) // 2 ms

Problem 20

Find the sum of digits in 100!*

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

Problem 21

Evaluate the sum of all amicable pairs under 10000.*

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

Problem 22

What is the total of all the name scores in the file of first names?*

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

Problem 23

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.*

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

Problem 24

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?*

def ps(s: String): Iterator[String] = if (s.length == 1) Iterator(s)
  else s.toIterator.flatMap(c => ps(s.filterNot(_ == c)).map(_ + c))

val r = ps("0123456789").drop(999999).next().toLong

assert(r == 2783915460L) // 712 ms

Problem 25

What is the first term in the Fibonacci sequence to contain 1000 digits?*

lazy val fs: Stream[BigInt] = 0 #:: fs.scanLeft(BigInt(1))(_ + _)

val r = fs.view.takeWhile(_.toString.length < 1000).length

assert(r == 4782) // 468 ms

Problem 26

Find the value of d < 1000 for which 1/d contains the longest recurring cycle.*

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

Problem 27

Find a quadratic formula that produces the maximum number of primes for consecutive values of 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)).length))
}

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

Problem 28

What is the sum of both diagonals in a 1001 by 1001 spiral?*

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

Problem 29

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and
2 ≤ b ≤ 100?*

val r = (2 to 100).flatMap(a => (2 to 100)
  .map(b => BigInt(a).pow(b))).distinct.length

assert(r == 9183) // 17 ms

Problem 30

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.*

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

Problem 31

Investigating combinations of English currency denominations.*

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

Problem 32

Find the sum of all numbers that can be written as pandigital products.*

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

Problem 33

Discover all the fractions with an unorthodox cancelling method.*

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

Tags: , , , , ,

This entry was posted on Saturday, August 21st, 2010 at 10:25 pm and is filed under Programming, Scala. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

46 Comments

  1. Nicholas Sterling says:
    September 11, 2010 at 11:20 pm

    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?

  2. Pavel says:
    September 13, 2010 at 3:00 pm

    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.

  3. sandobal says:
    October 31, 2010 at 7:30 pm

    Super, thank you a lot for your solutions.

  4. hbatista says:
    December 15, 2010 at 2:18 pm

    Great post! Thanks!

  5. MichielH says:
    December 15, 2010 at 3:54 pm

    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
      }
    }

  6. ndesmoul says:
    December 15, 2010 at 3:58 pm

    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 }

  7. wheaties says:
    December 15, 2010 at 4:01 pm

    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.

  8. Pavel says:
    December 15, 2010 at 10:46 pm

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

  9. Pavel says:
    December 15, 2010 at 10:47 pm

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

  10. Pavel says:
    December 15, 2010 at 10:50 pm

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

  11. ndesmoul says:
    December 16, 2010 at 3:26 pm

    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.

  12. ndesmoul says:
    January 3, 2011 at 12:57 pm

    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.

  13. Mark says:
    March 14, 2011 at 6:13 pm

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

  14. Pavel says:
    March 15, 2011 at 2:22 pm

    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”).

  15. Mark says:
    March 16, 2011 at 6:21 pm

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

    Thanks.

  16. Rhys says:
    June 2, 2011 at 12:20 am

    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?

  17. Pavel says:
    June 2, 2011 at 5:18 pm

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

  18. Tom Szczesny says:
    June 7, 2012 at 2:08 am

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

  19. Tom Szczesny says:
    June 7, 2012 at 5:38 pm

    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)

  20. Pavel says:
    June 8, 2012 at 11:31 am

    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.

  21. Learning Languages « agileblogs says:
    November 11, 2012 at 5:15 pm

    […] 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 […]

  22. Micheal says:
    June 27, 2013 at 6:35 pm

    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

  23. Pavel says:
    June 27, 2013 at 11:45 pm

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

  24. Stephane says:
    July 2, 2013 at 5:15 pm

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

  25. Pavel says:
    July 3, 2013 at 6:39 pm

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

  26. Power of Scala | Sudhish Rema's blog on Technology says:
    October 9, 2013 at 10:34 am

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

  27. Design Patterns in Scala says:
    October 12, 2013 at 3:35 pm

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

  28. Vitalii Tamazian says:
    October 14, 2013 at 3:58 pm

    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
    }

    }

  29. Pavel says:
    October 14, 2013 at 9:12 pm

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

  30. PeterX says:
    December 8, 2013 at 3:51 am

    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)

  31. PeterX says:
    December 8, 2013 at 4:11 am

    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)

  32. Pavel says:
    December 9, 2013 at 12:12 am

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

  33. Pavel says:
    December 9, 2013 at 12:47 am

    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 🙂

  34. seth2810 says:
    January 2, 2014 at 4:20 pm

    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)
    }

  35. Gaurav Abbi says:
    July 15, 2014 at 6:57 am

    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?

  36. Gaurav Abbi says:
    July 15, 2014 at 7:01 am

    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

  37. Pavel says:
    July 15, 2014 at 2:23 pm

    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.

  38. Gaurav Abbi says:
    July 15, 2014 at 4:15 pm

    Hi Pavel,
    Thanks for the reply. It helps.

  39. Jacek says:
    April 27, 2016 at 9:44 pm

    For problem 4, you can change “100” to “101” as follows:
    val r = (101 to 999).view

    You cannot have a palindrome that fits the problem description because a factor of 100 will always end in “00” (e.g. 100 * 858 = 85800). I assume here that leading zeros are not considered. Thus, you should start searching with 101.

    This version produces still produces the correct result and is arguably “cleaner” or what have you.

  40. Samar says:
    August 14, 2016 at 10:35 am

    Hi Pavel,

    From the scaladoc for views link that you mentioned: http://www.scala-lang.org/docu/files/collections-api/collections_42.html :

    “Scala collections are by default strict in all their transformers, except for Stream, which implements all its transformer methods lazily. However, there is a systematic way to turn every collection into a lazy one and vice versa, which is based on collection views. A view is a special kind of collection that represents some base collection, but implements all transformers lazily.”

    Since Streams anyways implement all their transformer methods lazily, why do we need to use a view for the stream examples above?

    Thanks for the excellent solutions showing the brevity and power of Scala.

  41. Pavel says:
    August 14, 2016 at 3:50 pm

    Hi Samar,

    Besides the “laziness”, there are two additional important characteristics of collection implementation: whether it holds all the elements in memory and whether it allows re-iteration. Depending on a particular case we may need different combinations of those 3 traits. See What is the difference between view, stream and iterator?.

    In some cases, we might want to avoid creation of temporary collections, yet Stream, despite of its laziness, still creates a new instances of Stream after each transformation. Look for “Don’t create temporary collections” in the Scala Collections Tips and Tricks (which is a great package of recipes on topic, by the way).

    In other cases, we might want to avoid storing values in memory at all, but Stream preserves all the computed values to allow re-iteration. See In Scala, what does “view” do?.

    It’s easy to spot the difference right in the Scala console: run Range(0, 100000000).view.max and the statement will complete just fine, but run Range(0, 100000000).toStream.max and it will produce an OutOfMemoryError.

  42. Samar says:
    August 15, 2016 at 2:19 pm

    Hi Pavel,

    Thanks for the explanation and the links. Lot of useful information in there.

  43. Tim says:
    January 1, 2017 at 9:03 pm

    Project 8 – Discover the largest product of five consecutive digits in the 1000-digit number.*
    Your answer of 40824
    has a “0” in it, which means the product is 0.
    That is not the right answer.

  44. Pavel says:
    January 1, 2017 at 11:37 pm

    Hi Tim!

    At the moment of writing the article Problem 8 was defined as “Discover the largest product of five consecutive digits in the 1000-digit number” and both the solution and the answer matched this definition. For some reason, the problem description has been changed since that time.

  45. Nader Ghanbari says:
    November 19, 2017 at 8:43 am

    Problem 4 can be solved much much faster. You can start a search in two-dimensional space from upper bounds (1000) and keep track of the largest palindrome found so far, then you can save time by not examining a product if you are sure that it won’t be larger than the largest found palindrome. I’m looking for ways to further improve this by iterating in a zigzag pattern making sure that the product is monotonically decreasing, then as soon as you find the first palindrome you can return (I could write a code without any mutation or vars using `return` statements in foldLeft.

  46. Nader Ghanbari says:
    November 23, 2017 at 11:46 pm

    I think the solution to problem 26 is wrong, it produces the correct result but it’s an accident. You have to check more than just remainder(10^p, n) == 1.