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 8 in Scala

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


So we saw problem 6 solved with a 'one-liner'.  Then we moved on to problem 7 and I had to have a while loop and control variables, which really disappointed me. Problem 8, however, was not only satisfying, but allowed me to explore even more features of Scala.  


Before I get into the actual problem, I want to comment on my language progress.  My 'native tongue' so-to-speak, is Java.  I use Java at work and have for 12 years. I expect it will be paying the bills for years to come.  We can debate the merits of Java as a language, and I'm sure every one reading this has an opinion about it, good or bad.  Regardless of opinion, I am most productive in Java.  Period.  Why?  Because I have used it so much, and am so familiar with the syntax and libraries that the language 'gets out of the way'.  I don't have to think about anything but what the code is intending to do.  This makes me very productive.  I'm finding that its taking a little longer to get to the point where I feel like the language has stepped back with Scala.  Part of it is the rather verbose API documentation, which, just seems to tell me too much and doesn't allow me to get right to 'how do I use this'.  Part of it is that Scala has a lot more power and expressiveness than Java, and that takes more time to learn.  At any rate, my Scala skills are slowing improving.  


Now, on to Problem 8:

Find the greatest product of five consecutive digits in the 1000-digit number.

 73167176531330624919225119674426574742355349194934
 96983520312774506326239578318016984801869478851843
 85861560789112949495459501737958331952853208805511
 12540698747158523863050715693290963295227443043557
 66896648950445244523161731856403098711121722383113
 62229893423380308135336276614282806444486645238749
 30358907296290491560440772390713810515859307960866
 70172427121883998797908792274921901699720888093776
 65727333001053367881220235421809751254540594752243
 52584907711670556013604839586446706324415722155397
 53697817977846174064955149290862569321978468622482
 83972241375657056057490261407972968652414535100474
 82166370484403199890008895243450658541227588666881
 16427171479924442928230863465674813919123162824586
 17866458359124566529476545682848912883142607690042
 24219022671055626321111109370544217506941658960408
 07198403850962455444362981230987879927244284909188
 84580156166097919133875499200524063689912560717606
 05886116467109405077541002256983155200055935729725
 71636269561882670428252483600823257530420752963450

 This problem is pretty straight forward.  Iterate the string literal and multiply sets of 5 numbers together.  Find the largest of those numbers and return it.  Now, in Java, this would take a couple of for loops, a String, possibly a string buffer, some variables to store the results, and an ugly System.out.println....

Not so in Scala.  The Collections facilities actually allowed me to solve this in one line, without any mutable state.  No, really, I mean it.  Check this out:

object Problem8 {
  def main(args: Array[String]): Unit = {
    val totalDigits = """[omitted the big string literal here, but you can add it back if you want to run the code...]"""
    println((for (i <- 5 to totalDigits.length()) yield totalDigits slice (i - 5, i)) collect {
      case i =>
        i.foldLeft(1)((product: Int, nextChar) => {
          (nextChar asDigit) * product
        })
    } max)
  }
}


Okay, its a 'one-liner' but there is a lot going on there.  Let's deconstruct the statement.  First, we see that everything is wrapped in a 'println', which is nice shorthand in Scala for System.out.println.  The second thing we see is that the result of the statement 'max' is what will be printed.  max is a collection function.  A couple of things to note.  Since max takes no arguments, we drop the '()'.  Since Scala can infer its a method call, we can even omit the '.'.  Now let's look at the rest of the code, shall we?


Let's go back to the beginning of the statement.  We are using the 'for' comprehension.  To be honest, the 'for' comprehension in Scala is much more powerful than the 'for' loop in other languages I've used.  You can see, we are going to iterate 5 to the length of the string.  For each iteration, we are going to yield the slice if i-5 and i.  slice is a nice string operator in Scala.  Essentially, we're getting 5 characters.  In turn we are going to collect the results of folding (There's that foldLeft again....) the 5 character Sequence.  The result of all of these will be a Sequence of Int values, on which we call 'max' function.


Boy, that was a mouthful.  It was cool, though, wasn't it?  It took a few minutes for me to weed through the API and figure out the syntax for this, but in the end, it is a succinct and stateless solution....


On to the next one...

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

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.

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.