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

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.

Varying interview questions

I wonder if interviews for other professions are as varied as the interviews for software engineers.  I guess with all the charlatans and pretenders out there, companies have been burned.

With the change in ownership at my company, I have been interviewing with different companies, and the questions have been varied and interesting.  I thought I would share some experiences with you.  Here are a sample of some of the questions I have been posed with.

• How would you handle a situation where you were handed a deadline for some functionality and you KNEW it could not be done in that time frame?
• What is the difference between deleting rows, dropping a table, and truncating a table (NOTE: This was for a Java developer job, not a DBA job)
• How do you do String comparison?
• What is the difference between a Map, a List, a Set, and an Object Array (You mean besides the fact that an Object Array is a primitive part of the language and the others are not?)
• Describe how you would manage a software development project.
• Describe a time when you had to debug something and the tools you use.

I believe I've done reasonably well in the interviews I've been in, but the questions to me seem to be all over the place.  Perhaps employers have a variety of needs and are trying to determine where I would best fit.  Either way, its difficult to be prepared for interviews.  Last week I was reciting intricacies of JVM memory reclamation, language features and syntax, and constructs. This week I was describing my use of requirements, Use-Cases, UML and Sequence Diagrams.  I can't wait to see what next week brings.

Android Development – So Easy, Yet Not So Easy

I have recently started playing around with Android. Given the success of the Droid, Droid Eris, and what looks like a phone from Google, the NexusOne, I figure the Android is going to be either the number one or number 2 development platform for mobile devices. In either case, I want to be able to write apps for my Droid, which, I love.

So this week I have attempted to start development. I have read through the online documentation, which, in typical Google fashion, is fairly complete and detailed. The Android Developer Guide includes step by step instructions for installation of the SDK, Eclipse Plugin, and samples to get you programming quickly.

Of course, nothing is perfect. So here are a couple of issues with the tools.

• It appears that sometimes changed resources don’t get updated when the emulator is re-launched. Even though I’ve set the flag to Wipe User Data.
• I can get one version of the Google Maps sample to run correctly but not another. It seems that the Sample Tutorial on the Web site doesn’t work for 2.0 or 2.0.1 emulators on my machine, but the sample bundled with the toolkits do. To be honest, it appears that the only difference is WHERE the MapView is instantiated, but I am still a noob at this, so I am probably mistaken

Is this going to be enough to cause me to give up? Heck no. Even though these two items are frustrating, the toolkit is still well put together and I expect to be building apps in no time. My next posts will detail the building of an app.