Euler Project Problems 4-6 (with 1 and 2 revisited) in Scala

This is my continuing series on using Project Euler to learn Scala.
You can see the other posts in the series by visiting the Project Euler category.

Problem #4

val result = Range(999, 900, -1)
        .map(a => (a, Range(999, 900, -1).find(b => {
            val number = a * b
            val digits = number.toString.toCharArray.map(digit => Integer.valueOf(digit - 0x30))
            var found = true

            for (i <- 0 to digits.length / 2)
              if (digits(i) != digits(digits.length - 1 - i))
                found = false

            found
          })))
        .filter(pair => pair._2 != None)
        .map(pair => (pair._1, pair._2.get, pair._1 * pair._2.get))
        .maxBy(tuple => tuple._3)

println(result._1 + " * " + result._2 + " = " + result._3)

Gotta love writing one statement solutions.
I went with the brute-force solution here, because it was easy to write and debug and ran at a decent time.

Problem #5

import collection.mutable.{ListBuffer, HashMap}

object problem5 {
  val primes = new HashMap[Int, Int]()

  def collectPrimeDivisors(n: Int) {
    var current: Int = n
    var divisor: Int = 0

    // Find out the prime divisors and list them in divisorList
    val divisorList = ListBuffer[Int]()

    while (divisor != current && current != 1) {
      divisor = current

      val found = primes.find((prime: (Int, Int)) => current % prime._1 == 0)

      if (found != None) {
        divisorList.append(found.get._1)
        current /= found.get._1
        divisor = found.get._1
      }
    }

    if (divisor == current) {
      divisorList.append(current)
    }

    // Zip up the list of divisors
    val map = HashMap[Int, Int]()
    divisorList.foreach((prime: Int) => { map.put(prime, map.get(prime).getOrElse(0) + 1); map })

    // Collect the prime divisors
    map.foreach((tuple: (Int, Int)) => primes.put(tuple._1, math.max(tuple._2, primes.get(tuple._1).getOrElse(0))))
  }

  def run(number: Int): Int = {
    // Collect prime divisors from 2 to 20
    Range(2, number).foreach((i: Int) => collectPrimeDivisors(i))

    // Multiply all prime divisors
    primes.foldLeft(1)((seed: Int, prime: (Int, Int)) => seed * math.pow(prime._1, prime._2).asInstanceOf[Int])
  }

  def main(args: Array[String]) {
    println(run(20))
  }
}

It took me less time to do this with pen and paper than it did to code the solution. Here’s to math :)

Problem #6

object problem6 {
  def apply(n: Int): Int = {
    val sumOfSquares = n * (n + 1) * (2 * n + 1) / 6
    val sum = n * (n + 1) / 2
    val squareOfSum = sum * sum

    squareOfSum - sumOfSquares
  }

  def main(args: Array[String]) {
    println(apply(100))
  }
}

Another win goes to math. O(1) trumps O(n).

Problem #1 (two more solutions)

object problem1_b {
  def problem1Runner(x: Int): Int = {
    val zeroCase: PartialFunction[Int, Int] = { case 0 => 0 }
    val otherNumbers: PartialFunction[Int, Int] = { case n => p1(n) }
    val divisible: PartialFunction[ Int, Int ] = { case n if (n % 3 == 0) || (n % 5 == 0) => n + p1(n) }

    val runner = zeroCase orElse divisible orElse otherNumbers

    runner(x)
  }

  def p1(x: Int) = problem1Runner(x - 1)

  def main(args: Array[String]) {
    println(p1(1000))
  }
}

This solution is thanks to Tomer who told me about the case if pattern, in which the domain of the function is defined in the if clause instead of having to implement PartialFunction all over again.

However, after reading some more, I came to a more succinct solution:

println(Range(1, 1000).filter(n => n % 3 == 0 || n % 5 == 0).sum)

Gotta love one-liners :)

Problem #2 (another solution)

This solution uses the Tail Recursion optimization in Scala that was pointed out to me by Tomer.

object problem2_b {
  @tailrec
  private def sum(a: Int, b: Int, runningSum: Long): Long = {
    if (b > 4000000)
      runningSum
    else
      sum(b, a + b, if (b % 2 == 0) b + runningSum else runningSum)
  }

  def main(args: Array[String]) {
    println(sum(1, 1, 0))
  }
}
Advertisements

One thought on “Euler Project Problems 4-6 (with 1 and 2 revisited) in Scala

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