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.
