As with when I learned Ruby, I find Project Euler to be an extremely useful way both to learn a language and its idioms and also flex my math muscles every once in a while. Since I’m starting to learn Scala, I decided to start answering the problems there again (the last time I got to 33) and thought I’d share what I came up with here.

## Problem #1

object problem1 { def run(number: Int): Int = { sum(number - 1) } def sum(number: Int): Int = { number match { case 0 => 0 case n => (if(n % 3 == 0 || n % 5 == 0) n else 0) + problem1.sum(n - 1) } } }

I had wanted to use `PartialFunction`

‘s functionality for the sake of some mental gymnastics (and the fact that filtering doesn’t occur until the inside of the case in the previous solution), so here’s another solution:

def problem1Runner(x: Int): Int = { val zeroCase: PartialFunction[Int, Int] = { case 0 => 0 } val otherNumbers: PartialFunction[Int, Int] = { case n => p1(n) } val runner = zeroCase orElse new Problem1PF orElse otherNumbers runner(x) } def p1(x: Int) = problem1Runner(x - 1) class Problem1PF extends PartialFunction[Int, Int] { def isDefinedAt(n: Int): Boolean = { (n % 3 == 0 || n % 5 == 0) } def apply(n: Int): Int = { n + p1(n) } } println(p1(1000))

Obviously, this is the less readable solution, but it taught me more to try and code it.

## Problem #2

def fibSum(): Int = fibSum(1, 2) def fibSum(a: Int, b: Int): Int = { var sum = 0 var x = a var y = b while (x <= 4000000) { if (x % 2 == 0) sum += x val z = x x = y y += z } sum } println(fibSum())

I tried to create an obvious recursive solution, but I quickly understood how it would overflow.

## Problem #3

Here I tried the obvious solution first, but it had horrible complexity, so I went and implemented the (unreadable) Shanks’ square forms factorization algorithm (and used Euclid’s greatest common divisor algorithm as part of it).

import collection.mutable.ListBuffer object problem3 { def apply(n: Long): Long = { var num = n val factors = ListBuffer[Long](problem3.findFactor(num)) while (factors.last != 1) { num /= factors.last factors.append(problem3.findFactor(num)) } factors.max } private def findFactor(n: Long): Long = { // initialize val k = 1 var p: ListBuffer[Long] = ListBuffer(math.floor(math.sqrt(k * n)).asInstanceOf[Long]) var q: ListBuffer[Long] = ListBuffer(1, (k * n - math.pow(p.head, 2.0)).asInstanceOf[Long]) var b: Long = 0L // repeat var i = 1 do { b = math.floor((math.floor(math.sqrt(k * n)) + p(i-1)) / q(i)).asInstanceOf[Long] p.append(b * q(i) - p(i-1)) q.append(q(i-1) + b * (p(i-1) - p(i))) i += 1 } while (!isPerfectSquare(q.last)) // initialize b = math.floor((math.floor(math.sqrt(k * n)) - p(i-1)) / math.sqrt(q(i))).asInstanceOf[Long] p = ListBuffer((b * math.sqrt(q(i)) + p(i - 1)).asInstanceOf[Long]) q = ListBuffer(math.sqrt(q(i)).asInstanceOf[Long], ((k * n - math.pow(p(0), 2.0)) / math.sqrt(q(i))).asInstanceOf[Long]) // repeat i = 0 do { i += 1 b = math.floor((math.floor(math.sqrt(k * n)) + p(i-1)) / q(i)).asInstanceOf[Long] p.append(b * q(i) - p(i-1)) q.append(q(i-1) + b * (p(i-1) - p(i))) } while (p(i-1) != p(i)) gcd(n, p(i)) } private def isPerfectSquare(n: Long): Boolean = { val root: Long = math.floor(math.sqrt(n)).asInstanceOf[Long] root * root == n } private def gcd(a: Long, b: Long): Long = { // Euclid's algorithm b match { case 0 => a case _ => gcd(b, a - b * math.floor(1.0 * a / b).asInstanceOf[Long]) } } } println(problem3(600851475143L))

### Notes:

- ListBuffers are better than Lists for appending items.
- Turns out you can’t do for on a range longer than Int.MAX_VALUE.
- The number of non-textual operators in Scala is insane!

Quick copy-paste from Twitter:

#1 can be more elegantly expressed with something like def p1f: PartialFunction[ Int, Int ] = { case n if (n%3==0) || (n%5==0) => n + p1(n) }.

#2 can be rewritten as recursive with tail optimization (use @tailrec to get a compiler warning if tail recursion optimization cannot be applied), and wrapped with Stream for a more elegant functional solution (“new FibbonachiStream() take sum” or mental equivalent).

Wonderful, thanks! I’ll give those a try and update with new solutions :)

Here’s the “functional” solution I showed you earlier, just in case you want to have it…

lazy val fibs:Stream[Int] = 0 #:: 1 #:: (fibs zip fibs.tail).map{ t => t._1 + t._2 }

println (fibs takeWhile(_ <= 4000000) filter (_%2 == 0) sum)

Tal: I’m pretty sure you can use fibs.foldRight(_+_) instead, although that may produce a scalar instead of a function. Either way, it’s butt ugly :-)