Long time since last update now. I have been out traveling in Americaland again, but I am now back. Not that there are many reading this blog, but I at least try and keep myself busy working through these Euler problems to practice my Scala.
Problem 5 in project euler deals with finding the smallest number that divides with a range off numbers:
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 number that is evenly divisible by all of the numbers from 1 to 20?
This is actually pretty easy to just solve directly. We start with just multiplying all the numbers from 1 to 20:
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20
If you examine this, 20 is 10*2, and we allready have that in our set, so we can drop it. 18 is 2*9, so we can drop that as well. 16 is 2*2*2*2, 8 is 2*2*2, 4 is 2*2 and 2 is just 2. Since 16 covers all those divisors, we can drop 2,4 and 8. With that, we are reduced to:
1 * 3 * 5 * 6 * 7 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 19
Still, we can remove more numbers. 15 is 3*5, 14 is 2*7, 12 is 2*6, and 10 is 2*5, leaving us with:
1 * 3 * 5 * 6 * 7 * 9 * 10 * 11 * 13 * 16 * 17 * 19
2 and 3 are factors of 16 and 9 respectivly, which means we can remove both 3 and 6. 10 is 5*2, we have 5 and 2 as a factor off 16. This finally leaves us with:
5*7*9*11*13*16*17*19
Which proves to be the right answer. So this can be pretty easily solved just using conventional math.
Now for a Scala solution. What I intend to do here is to create a list of 1 to 20. For each value at index n in the list, I divide the value at n+1 -> max by n if it’s divisible by n. For the first number, 1, nothing changes. But applying the same to the list using 2, results in the following updated list:
1,2,3,2,5,3,7,4,9,5,11,6,13,7,15,8,17,9,19,10
Every even number after 2 gets divided by 2. This produces a new list, and we repeat this process for the next number, 3:
1,2,3,2,5,1,7,4,3,5,11,2,13,7,5,8,17,3,19,10
Since 6 was divisible by both, it’s now reduced to 1. If we keep repeating this process, we will end up with a list of unique factors in the final answer. Now for the code applying this to a list.
1
2
3
4
5
6
7
8
| def reduceMuls(src:List[Int]):List[Int] = {
src.head :: reduceMuls(src.head, src.tail)
}
def reduceMuls(div:Int, target:List[Int]):List[Int] = {
if (target.tail.isEmpty) return target
val res = target map(a=>if(a%div==0) a/div else a)
res.head :: reduceMuls(res.head, res.tail)
} |
Ok, the first function here is just a simple wrapper that extracts the first and reminder off the list, and passes it on to the second method. Line 5 is just a check for empty lists. Line 6 does the magic, it maps the target list by dividing all numbers in it if it’s divisible by div, the first argument. This new list is then modified by applying the same function to all but it’s first element, and adding the first element to the start. The argument at each stage off the process looks as follows:
List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
List(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
List(3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
List(2, 5, 3, 7, 4, 9, 5, 11, 6, 13, 7, 15, 8, 17, 9, 19, 10)
List(5, 1, 7, 4, 3, 5, 11, 2, 13, 7, 5, 8, 17, 3, 19, 10)
List(1, 7, 2, 3, 5, 11, 1, 13, 7, 5, 4, 17, 3, 19, 5)
List(7, 2, 3, 1, 11, 1, 13, 7, 1, 4, 17, 3, 19, 1)
List(2, 3, 1, 11, 1, 13, 7, 1, 4, 17, 3, 19, 1)
List(3, 1, 11, 1, 13, 1, 1, 4, 17, 3, 19, 1)
List(1, 11, 1, 13, 1, 1, 2, 17, 3, 19, 1)
List(11, 1, 13, 1, 1, 2, 17, 1, 19, 1)
List(1, 13, 1, 1, 2, 17, 1, 19, 1)
List(13, 1, 1, 2, 17, 1, 19, 1)
List(1, 1, 2, 17, 1, 19, 1)
List(1, 2, 17, 1, 19, 1)
List(2, 17, 1, 19, 1)
List(17, 1, 19, 1)
List(1, 19, 1)
List(19, 1)
List(1)
The final list returned will actually look like this:
1, 2, 3, 2, 5, 1, 7, 2, 3, 1, 11, 1, 13, 1, 1, 2, 17, 1, 19, 1
Now we need to call this method, and multiply all the numbers to get the smallest number divisible by all numbers from 1 to 20. The numbers reduced to 1 in the above list will of course not have any effect on the result, as they are included in other factors.
1
2
| val res = reduceMuls(1 to 20 toList).foldLeft(1) (_*_)
println(res) |
We need to convert the Seq to a list so it can properly be used in our function. I actually discovered after doing most off the code in this post that I could also do this with a Seq[Int], however it doesn’t work for how I intend to evolve the code a bit later. What we can do first, is to replace the foldLeft method with the fold left operator, /:. Though it is actually a method rather than an operator, as there are no operators in Scala, just methods. The code is then:
1
| val res = (1 /: reduceMuls(1 to 20 toList)) (_*_) |
This post is already quite long, but now I am actually coming to the part I want to demonstrate a bit more here, Scala’s pattern matching. When we have if/else constructs (though technically the else is missing), they can often be simplified with match expressions. Here is the same method rewritten to use Scala’s match operator:
1
2
3
4
5
| def reduceMuls(src:List[Int]):List[Int] = src match {
case 1::rest => reduceMuls(rest)
case a::rest => a::reduceMuls(rest map(x=>if(x%a==0) x/a else x))
case _ => src
} |
The match expressions look a bit similar to Javas switch, but it’s much more powerful. It takes any object and compares it to the expression in the case statement. The case statement can also use variable names that can then be used in the resulting handler. One important thing here is that for methods you need to handle all cases, which usually ends with a default case at the end. There are partial functions and case classes that allows you to work around this, but I won’t go into that here. Let’s look at the cases in the above example. There is also no fall through and breaks. Each handler is separate.
The first cases say the number 1 followed by a list. This will match all lists that have at least 1 element, and the first element is 1. I say 1 element because the rest off the list can be the empty list. The rest keyword then refers to a variable name that is in scope for the handler. For this case, we can drop the 1, and just reduce the rest of the list.
The second case is any value followed by a list of values. This will match all other entries except the empty list. For this we create a new list of a, and then rest divided by a where the values are divisible by a.
The final case handles anything. _ is the wildcard operator for Scala, and this just simply returns the src as is. This will be hit when we try reduceMuls on the empty list, which has no element followed by a tail.
Now we are almost done, but I have one more trick to show first:
1
2
3
4
5
6
| def divBy(div:Int)(x:Int) = if(x%div==0) x/div else x
def reduceMuls(src:List[Int]):List[Int] = src match {
case 1::rest => reduceMuls(rest)
case a::rest => a::reduceMuls(rest map divBy(a))
case _ => src
} |
I have added a divBy method here, which takes 2 sets of arguments. A divisor, and a value to divide by. This is Scala’s way of doing something called Currying. This has a lot of uses, but here we use it in the reduceMuls map to make it more readable. divBy(a) returns a partial function that is missing it’s last argument, x, before it can be called. This method is then applied for each element in rest using the map function.
Our final program is then:
1
2
3
4
5
6
7
8
9
| object Euler005 extends Application {
def divBy(div:Int)(x:Int) = if(x%div==0) x/div else x
def reduceMuls(src:List[Int]):List[Int] = src match {
case 1::rest => reduceMuls(rest)
case a::rest => a::reduceMuls(rest map divBy(a))
case _ => src
}
println ((1 /: reduceMuls(1 to 20 toList))(_*_))
} |
A bit sorry for this long post, I actually started it over 2 weeks ago at an airport while a bit bored. However, I have been really busy so this post didn’t get done until now. I will try to get back with more posts more regularily, as I have solved quite a few more Euler problems in Scala already. It’s also getting easier and easier to think in more Scala like terms for this, producing ever shorter programs faster than I would in Java.
2 grid, there are 6 routes (without backtracking) to the bottom right corner.