Saturday, December 31, 2011

Project Euler Problem 6 in Scala

This is 6 in a series.  The previous post is at, Project Euler Problem 5 in Scala.


Problem 6 was particularly satisfying for me.  You will see why when you see the code below.  I think the code deserves some discussion because it takes advantage of some pretty nice Scala features.

Project Euler problem 6 reads:
The sum of the squares of the first ten natural numbers is,  12 + 22 + ... + 102 = 385The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10)2 = 552 = 3025Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is   3025-385 = 2640. Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
So reading this question, we want to come up with an algorithm that iterates all the numbers 1..100.  During each iteration, we want to capture the sum of the squares, and the sum of the number.  Finally, we want to square the sum of the number and subtract the two values.  

Using some of Scala's syntactic sugar and its excellent functional handling we get:


object Problem6 {
  def main(args: Array[String]): Unit = {
    val results = ((0, 0) /: (1 to 100))((i, s) => {
      (i._1 + (s * s), i._2 + s)
    })
    println((results._2 * results._2) - results._1);
  }
}

If we take out the object definition and main method call, you can see that this is a two-liner (I could make it a one-liner, but I think that would sacrifice readability).  Once again, I am using the foldeLeft operator (/:).  This time, however, I am folding left on a sequence of values instead of a single value.  Because of this, you see the (0,0) declaration.  Scala also infers this type inside the body of the function, so I am storing to values i._1 and i._2.  Finally, we square the sums and subtract the sum of the squares.


Note that I actually multiplied results._2 by itself.  the '^' operator in Scala seems to work differently than I expected, and was giving me weird results.  I might have to look into that, but for now, we have a very succinct solution to this problem. 

Tuesday, December 27, 2011

Project Euler Problem 5 in Scala

This is 4 in a series.  The previous post is at, Project Euler Problem 4 in Scala.


Here we are, arriving at problem 5 from the Project Euler site.  For those of you that may have stumbled in on these posts, and haven't read why I am doing this, you might want to go back to the beginning and find out here.  The long and short of it is, I'm using these exercises as a way to solve fun problems while learning a new language (Scala).  I've added a twist to try an help me think in a functional way - for each solution, I want my final version of code to have the least amount of mutable state possible.

As it turns out, this has been a fun and enlightening exercise, and I'm only a few problems in!  If you've read any of my previous posts, you know that they were concentrating on turning my Java-like, OO style code into more functional style code without any mutable state.  I must be improving slightly, because this post is going to focus more on creating the right algorithm than on functional vs. OO style.  Without further adieu, I present to you, Project Euler Problem 5:
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
Well, my first solution, as always, was a brute-force way to solve the problem.  I will simply find my 'upper limit' value, which is the product of all the numbers 11 to 20 (A very large number), and iterate all values up to that number, checking if each number has a remainder when divided by any of the numbers 11 to 20.  Simple right?  It was simple, but it also takes 2 minutes to run on my Lenovo ThinkPad running an Intel Dual Core i7 CPU @ 2.67GHz.  Here's the implementation:


object Problem5 {
  def divisible(number: BigDecimal): Boolean = {
    for (i <- 11 to 20 ) {
      if (number.remainder(new BigDecimal(i)).longValue > 0)
        return false
    }
    return true
  }

  def main(args: Array[String]): Unit = {
  var start = System.currentTimeMillis
    val upperBound = (new BigDecimal(1) /: (11 to 20))(_ multiply new BigDecimal(_))
    println("Upper bound is " + upperBound)
    var i = 1
    for (i <- 20 to upperBound.intValue() if divisible(new BigDecimal(i))) {
       println("Smallest # divisible by 1 .. 20 is " + i);
       println("Run time seconds " + ((System.currentTimeMillis()-start)/1000));
        return
    }
  }
}

After I solved the problem, I started thinking about it more.  Iterating through every number seems wasteful, doesn't it?  After all, there are a lot of numbers that will not evenly divide by ANY number in that sequence.  So, I thought, I should really be iterating through a list of numbers that is the product of at least ONE of the numbers in the sequence.  If I selected, 15, for instance,  I could iterate through the list: (15, 30, 45, 60...).  Of course, If I think about that more, the most efficient number to use will be the highest number in the list, 20.  So, I created a new version of the code that iterates in increments of 20, and then checks to see if 11 to 19 are also divisible.  This runs on my machine in about 2 seconds, making this about 60 times faster:


object Problem5 {
  /*Let's skin this cat a different way...*/


  def main(args: Array[String]): Unit = {
    for (i <- 1 to 320000000) {
      val mot = i * 20;
      val divisibleByAll = fitsAll(mot)
      if (divisibleByAll) {
        println("Smallest is " + mot);
        return
      }
    }


    def fitsAll(number: Int): Boolean = {
      for (i <- 11 to 19) {
        if (number % i > 0)
          return false;
      }
      return true
    }
  }
}


I think I can further improve this code with some of Scala's features.  For instance, I think I can iterate the sequence 1 to 320000000 by increments of 20 without needing the variable mot.  Notince, though, that I do not have any mutable variables in the code - I declare 2 variables, but they are both val and not var, and so cannot be re-assigned.  I don't think this is 'perfect functional thinking', but I suspect, I'm slowly catching on.



Friday, December 23, 2011

Project Euler Problem 4 in Scala

This is 4 in a series.  The previous post is at, Project Euler Problem 3 in Scala.

So I've already worked through 3 problems in Euler in hopes of using the exercises to help me learn some Scala.  In each of the previous solutions, I had a LOT of mutable state in my code.  As I get more comfortable with the language, however, I think I'm improving quite a bit.  Even so, it appears I still had a mutable variable in my first solution to this problem.  Problem 4 on the Project Euler site reads:

 A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91  99.
 Find the largest palindrome made from the product of two 3-digit numbers.
This doesn't seem too difficult to solve.  We can cast our integer values to strings, reverse them, and compare them to determine if they are a palindrome, and iterating all the 3 digit numbers, 100-999 is easy.  So, here's my first solution:

 object Problem4 {


  def main(args: Array[String]): Unit = {  
var highestPalendrome = 0;
    for(i <- 100 to 999) {
for(y <- 100 to 999) {
 var product = i * y;
 var productStr = product toString;
 
 if(productStr.reverse equals(productStr)) { 
   println(productStr)
   highestPalendrome = highestPalendrome max product;
 }
}
}
    println("Highest is " + highestPalendrome);
  }
}


In this solution I iterate the numbers and store the highest palendrome as I go.  Of course, the purpose of doing these exercises is to try and code without mutable state, so I had to get rid of that pesky highestPalendrome variable.  To do this, I took advantage of the Scala fold left facilities.  Turns out, this is a handy way to iterate a list and record results.  Here's version 2:



object Problem4 {
  def main(args: Array[String]): Unit = {  
val highestPalendrome = (0 /: (100 to 999))((highest, next)=>{
(0 /: (100 to 999))((tot2, nex2)=>{
 val product = next*nex2;
 if(product.toString.reverse.equals(product.toString)) {
     next*nex2
 } else {
 tot2
 }
}) max highest 
})
    println("Highest is " + highestPalendrome);
  }
}


You'll notice that this is essentially 1 statement, if you remove the main method and println.  You should also notice that I'm using some of Scala's syntactic goodness to make the code easier to read - the end of that statement, 'max highest' would be much uglier in Java - .max(highest).

Well, on to #5.  Maybe this time, I won't need a second iteration of the code...

Project Euler Problem 3 in Scala

This is 3 in a series.  The previous post is at, Project Euler Problem 2 in Scala.


I've been busy again this fall, but now that I have a couple of days off over the holiday, I thought I'd play around with some more Scala.  It is pretty slow going learning the language at this pace, but the day job calls...


Problem 3 on the Euler site states:
The prime factors of 13195 are 5, 7, 13 and 29.  What is the largest prime factor of the number 600851475143 ?
For this solution, I reused the isPrime method from an earlier problem.  Essentially I end up looping through all the values up to the square root of the number and record the primes.  The largest prime is the last one.


Here's my first solution:

object Problem3 {
  val number : Long =  600851475143L;

  def main(args: Array[String]): Unit = {  
val sqrt = Math.sqrt(number);
    var largest = 0L;
var current : Long = 2L;
while(current < sqrt.toLong) {
 if(number % current == 0) {
 if(isPrime(current)) {
    largest = current;
 }
      }
 current = current + 1L;

println("Largest " + largest);

  }

  
  *//**
   * Brute force method.  Perhaps a better method 
   * can be implemented here?  
   *//*
  def isPrime(number: Long) : Boolean = {
    var half = Math.sqrt(number) 
    var current = 2;
    while(current < half) {
      if(number % current == 0) {
        return false;
      }
      current = current+1;
    }
    return true;
  }
}


After looking at my first solution to this problem, you can see that I have mutable state AGAIN.  Something about my Object Oriented brain just can't seem to get into the stateless-state-of-mind.  This is interesting for another reason, though. Mutable state, in general, isn't a particularly good thing.  That is, if you can solve a programming problem without mutable state, it is better than the solution with mutable state.  It shouldn't matter if you are using OO languages or Functional ones.  It seems the industries years of OO teachings have led to we engineers sort of ignoring this fact.  I guess mutable state isn't as clear in an OO language if you have good Encapsulation in your code, but its still something we should be paying attention to.  Luckily, I was able to refactor my solution.  Here's a better version:


object Problem3 {
  val number : Long =  600851475143L;

  def main(args: Array[String]): Unit = {  
 println("Largest is " + largestPrime(2L, Math.sqrt(number), 2L));
  }
  
  @tailrec def largestPrime(initialPrime : Long, limit : Double, currentNumber : Long) : Long = {
    if(currentNumber >= limit.toLong) {
      initialPrime
    } else {
      if(isPrime(currentNumber) && number % currentNumber == 0) {
        largestPrime(currentNumber, limit,  currentNumber + 1);
      } else {
        largestPrime(initialPrime, limit,  currentNumber + 1);
      }
    }
  }
  
 /**
   * Brute force method.  Perhaps a better method 
   * can be implemented here?  
   */
 def isPrime(number: Long) : Boolean = {
    var root = Math sqrt number
    var current = 2;
    while(current < root) {
      if(number % current == 0) {
        return false;
      }
      current = current+1;
    }
    return true;
  }
}


Here we have a new solution where all our mutable state has been removed.  I start by declaring the number for which we are trying to find the largest prime.  It is declared as a val, though, so we are guaranteed that the value can't change.  This is different than any other language I've used, but it seems a handy facility.  Next, I call the recursive largestPrime method, which uses Tail recursion to iterate the list.  


Of course, I still think there is a better way to determine if a number is prime or not, but this method is pretty efficient the way it is.


That's my solution for now.  Stay tuned for Problem 4....