Euler Project Problems 1-3 in Scala

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:

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

4 thoughts on “Euler Project Problems 1-3 in Scala

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

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s