Project Euler Problem 10 in Scala

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


Problem 10 on project Euler is:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

Problem 10 posed an interesting issue for me.  I came up with a solution I thought would work well right away, but I couldn't seem to get the correct answer.  After poring over my code and playing around, I finally found my issue - my isPrime function had an error in it, causing me to be off by 2.  


What is interesting about this scenario is that I've been using that same function for lots of different problems, but since the function was only broken for the number 2, it didn't matter in those.  If I had some sort of test that say, verified the function against a random set of prime numbers, I would have found the issue much sooner. This speaks to how important it is to test even seemingly working things whenever you can.    


Another by product of the issue is that I did a little more research on calculating prime numbers.  Wikipedia had a nice article about the  Sieve of Eratosthenes.  This gave me a much better understanding of how it works.  While I am not changing my code (yet) to use a sieve, it was certainly valuable to learn more about how its done.  


Well, I did manage to finish it, and here is my solution.  Enjoy:


object Problem10 {
  def main(args: Array[String]): Unit = {
    var holder : BigDecimal = new BigDecimal(new java.math.BigDecimal("0"));
    (2 to 1999999).filter{next => val prime = isPrime(next);if(prime){holder = holder + new java.math.BigDecimal(new Integer(next).toString())};prime}
    println(holder)
  }
  
  /**
   * Brute force method.  Perhaps a better method 
   * can be implemented here?  
   */
  def isPrime(number: Long) : Boolean = {
    if(number == 2)
      return true
    if(number%2==0 || number % 3==0)
      return false;
    val sqrt:Int = Math ceil (Math sqrt number)  intValue;
    (true /: (3 to sqrt))((isPrime, next) => {
      if(number % next == 0) 
        return false 
      isPrime
    })
  }
}


Now that I've completed #10, I get a Euler award.  I have become a 'Decathlete' for finishing 10 problems in a row.  


And with that, I think I will finish blogging about my Euler solutions.  I still plan on working through the problems, but I think I've worn out my Euler solution posts and will move on to some other interesting topics.  

Project Euler Problem 9 in Scala

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


I've still been (slowly) working my way through the Project Euler Problems.  The next one is problem 9 which reads:

A Pythagorean triplet is a set of three natural numbers, a  b  c, for which,
a^2 + b^2 = c^2
For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.
There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

For this problem, I didn't use anything fancy.  Two for-comprehensions and basic math produced the solution in short order.  The only thing to mention about this solution is that it actually finds the solution twice since I'm iterating1 to 998 twice. I considered trying to optimize this, however, it runs plenty fast.  Since my goal in solving these isn't to come up with the fastest solution, but to come up with a solution that has no mutable state, I have met my goal.  Therefore, I present you the solution to problem 9:



object Problem9 {
  def main(args: Array[String]): Unit = {
    for (a <- 1 to 998) {
      for (b <- 1 to 998) {
        val c = 1000 - (a + b)
        if ((a * a) + (b * b) == (c * c)) {
          println("the triplet is " + a + " " + b + " " + c)
          println("the product is " + (a * b * c))
        }
      }
    }
  }
}


I think that's all for this one.  Problem 10 is in the hopper...

Project Euler Problem 7 in Scala

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


After a very successful solution to problem 6, we get to problem 7.  I couldn't figure out how to remove all mutable state from this solution.  The issue is that we have to find the 10,001st number which means that we do not know how long we have to iterate.  I used a while loop here, and it seems to work fine.  Perhaps someone has a solution without a while loop?  


Here's Project Euler problem 7:

 By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
 What is the 10,001st prime number?

object Problem7 {


  def main(args: Array[String]): Unit = {
var counter = 1L;
var number = new BigDecimal(new java.math.BigDecimal("0"));
var currentNum = 1l;

while(counter <= 10001) {
 if(isPrime(currentNum)) {
   number = new BigDecimal(new java.math.BigDecimal(currentNum));
   counter = counter + 1;
 }
 currentNum = currentNum + 1;
}
println("10001st prime " + number);
  }
    
  /**
   * Brute force method.  Perhaps a better method 
   * can be implemented here?  
   */
  def isPrime(number: Long) : Boolean = {
    if(number%2==0)
      return false;
    val sqrt:Int = Math ceil (Math sqrt number)  intValue;
    (true /: (3 to sqrt))((isPrime, next) => {
      if(number % next == 0) 
        return false 
      isPrime
    })
  }
} 


You should note that I've cleaned up my isPrime method.  I noticed that it wasn't very functionally written, so I changed it to use a fold left (By the way, foldLeft is turning out to be one of the handiest Scala constructs on the planet.)  I am now very comfortable with the isPrime method, at least as a brute force solution.

Project Euler Problem 2 in Scala

This is 2 in a series.  The Previous post is at, Project Euler and Scala Problem 1.

Here is the second problem on the Project Euler(PE) site.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Once again, I was able to solve this pretty easily, but I had lots of mutable state in my code.  Here was my first solution:


object Problem2 {
val fourMillion : Integer = 4000000;


var first : Integer = 0;
var second : Integer = 1;

def nextFib() : Integer = {
var returnValue:Integer = prev1+prev2;
return returnValue;
}

var sum : Long = 0;


def main(args: Array[String]): Unit = { 
 var next:Integer = 0;
 while( (next <= fourMillion) ) {
 next = nextFib();
 if(next % 2 == 0) {
   sum = sum + next;
 }
 
 }
 print(sum)
}
}


You will see that I have 3 mutable variables in there -  first, second, and sum.  I also have a rather ugly while loop.  I'd like to get rid of the iteration here and use recursion instead.  While doing so, I can also get rid of the mutable state.  Here is the rewritten code:


object Problem2 {
//Tail recursive...
def fibList(currentList : Array[Int], limit : Int, previous : Int) : Array[Int] = {
 if(previous > limit) {
  return currentList;
} 
 return fibList((currentList :+ previous), limit, (currentList.last + previous));
}


def main(args: Array[String]): Unit = { 
 print((0 /: fibList(Array[Int](0,1), 4000000, 1))((total, next)=> {
     if(next % 2 == 0) { 
         next + total
  } else {
 total
  }  
}))
}
}



I hope you notice the comment in there - Tail Recursive.  This is a very interesting feature of Scala, and most other functional languages.  You see, the big concern in Java when using recursion is that you run out of stack space for all your recursions.  In Scala, the compiler can optimize this code and get rid of the stack if you don't need to keep state in your method.  I've carefully constructed the fibList here so that it can be optimized.  This way, we can't fill up the stack.  go ahead, change 4000000 to 4000000000.  While you may overflow the int values, the recursive function won't blow up the memory.  


This feature of the language is really quite interesting, and from my understanding not a small feat to pull off given the current bytecode standard.  This could allow for some very long-running calculations that might otherwise have caused memory problems if done other ways.  


That's all for this problem.  On to #3...   

Project Euler and Scala problem 1

I recently found a Web site called, Project Euler (PE).  Its a site full of problems that are intended to be solved by coding.  As I am also experimenting with Scala, I figured this would be a fun way to keep my skills sharp solving problems while learning the nuances of another language.


What I am finding is very interesting.  First, my 'functional' skills need work.  I'm attempting to solve each problem with no mutable state, but as you will see, my first iteration usually has some sort of mutable state and it takes me a little bit to refactor it.  Part of this is due to the fact that I spend my day job programming in an OO language, part of it is due to learning Scala, but part of it is just that I need more practice in the functional way of thinking.


I am fortunate in that I have two friends who are also interested in PE and who have started working through the problems as well, so we swap notes after we solve the solutions, which further helps understanding.  


I thought I would blog about the problems as I work through them.  The format I have settled on this this:

1. I will present my first, rough, solution to the problem, along with a brief summary of the PEdocumentation.
2. I will present a refactored version of the same problem that makes the code much more functional and maintainable.
3. If the PE documentation reveals a math or programming concept that would improve the code, another version of the algorithm may be posted.

It's my hope that presenting my progress in this fashion is both interesting and revealing for other programmers. I work primarily in Java, so this might also be a good way for Java programmers to see how things translate to Scala.  Of course I am not a Scala expert, so I'm sure there will be lots of comments with room for improvement.  At least, that's my hope.


Here is PE's first problem:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.Find the sum of all the multiples of 3 or 5 below 1000.

Well, this seems simple enough.  Simply iterate all the numbers to 1000, testing if they are divisible by 3 or 5 along the way.  The first version of my code looks like this:

object Problem1 {


  def main(args: Array[String]): Unit = {  
    var sum = 0;
    for( i <- Iterator.range(0,1000) if i % 3 == 0 || i % 5 == 0) {
      sum += i;
    }
    print(sum);
  }
}


There's nothing inherently wrong with the code above.  Except I have that mutable variable, sum,  in there.  So, what's a more functional way to think about this?  Thanks to the inspiration from my co-worker, Sean, we have a more functional version of the code above:


object Problem1 {
  def main(args: Array[String]): Unit = {
    val count = (1 to 999);
    val sum = (0 /: count)((total, next) =>
      {
        if (next % 3 == 0 || next % 5 == 0) {
          total + next;
        } else {
          total;
        }
      });
    println(sum);
  }
}


In this version, we've made the sum immutable (by using val instead of var), so it can only be assigned once.  We've also used the left-fold operator, \:, to iterate the range.  Finally, we've converted the contents of the for loop to a function block that gets executed on each 'fold'.  This version looks pretty good, but after reviewing the PE docs, we pick up another little math trick.  


Instead of iterating the numbers, we can take the sum of all the multiples of 3, sum of all the multiples of 5 and then subtract all the multiples of 15.  There's also a proof that demonstrates how to find the sum (I won't reprint it here, if you are interested, unlock the problem on the PE site).


The final version of our code looks like:


object Problem1 {
  def main(args: Array[String]): Unit = {
println(sumDivisibleBy(999,3) + sumDivisibleBy(999, 5) - sumDivisibleBy(999, 15));
  }
  
  def sumDivisibleBy(limit:Int, divisor:Int) : Int =  {
val p = limit/divisor;  
divisor * (p*(p+1))/2; 
  }
}


So in the end, we don't iterate the range at all.  This solution would also scale well (what if we wanted to add all the multiples of 3 and five for all numbers under 1 million...)


So there it is. A brief walk through my process on Project Euler problem 1. Let me know what you think.