I stumbled across an interesting web-site called
ProjectEuler. The
Wiki page gives a very good overview of the site.
I realized it would be a very interesting way for me to learn Scala syntax in a low risk and fun environment, small puzzles. Additionally, my son has expressed an interest in learning how to program. I figured this might be a great way to get him started, too. I will get back to the Scala-life series again, I promise.
My intention is to show the exact text of the problem from the web-site. Then, I would go through the process of taking the word problem and "visualizing" it; draw and possibly even animate it. Once the problem is visual, then I would then talk about possible solution approaches centering on declarative, imperative and functional. And then finally, I will transform it into both mathematical notation and Scala code.
So, let's jump right in. This post may be subjected to some frequent edit/update cycles after being published as I find my way to the right balance in working through designing this.
Problem Statement - 001:
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.
Visualization/Examples:
- numbers below 10 with multiples of 3 or 5
- Natural numbers below 10 = 1 2 3 4 5 6 7 8 9
- Multiples of 3 = 1 2 3 4 5 6 7 8 9
- Multiples of 5 = 1 2 3 4 5 6 7 8 9
- Multiples only = 3 5 6 9
- Sum = 3 + 5 + 6 + 9 = 23
- numbers below 20 with multiples of 3 or 5
- Natural numbers below 20 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
- Multiples of 3 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
- Multiples of 5 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
- Multiples only = 3 5 6 9 10 12 15 18
- Sum = 3 + 5 + 6 + 9 + 10 + 12 + 15 + 18= 78
Mathematical Notation:
TBD
Test Cases:
- floor = 1, ceiling = 10, multiples = 3 and 5, answer = 3 + 5 + 6 + 9 = 23 (provided in problem statement)
- floor = 1, ceiling = 20, multiples = 3 and 5, answer = 3 + 5 + 6 + 9 + 10 + 12 + 15 + 18 = 78 (produced by hand)
- floor = 1, ceiling = 1000, multiples = 3 and 5, answer = ? (produce from code)
Code Implementation Approaches:
The first and most intuitive approach for me at this time is to go one by one for each number from floor (1) to ceiling (10) and test a number for whether it is divisible by 3 or divisible by 5. If so, add it to a total I am keeping. And when the loop is finished, I will have my answer. Here's the small Scala Object class I created to perform the work:
object Problem001 extends App {
//http://projecteuler.net/index.php?section=problems&id=1
override def main(args : Array[String]) : Unit = {
javaWithoutSemicolons
}
def javaWithoutSemicolons : Unit = {
val floor = 1
val ceiling = 10
val multiple3 = 3
val multiple5 = 5
var sum = 0
for (i <- floor until ceiling)
if ((i % multiple3 == 0) || (i % multiple5 == 0))
sum = sum + i
Console.println("javaWithoutSemicolons.sum=" + sum);
}
}
This code looks almost identical to the Java code I would write, essentially Java without semicolons. Note the presence of the "var" for "sum". This is referred to as the "imperative" approach (as contrasted with the "functional" approach) to composing a solution. So, how might one go about moving this towards the more functional approach which is gently promoted by advanced Scala developers (and not so gently by functional programmers who have recently, if not reluctantly, adopted Scala)? We find a way to ensure everything remains "immutable"; i.e. there are no "var" entities defined. Additionally, we don't explicitly loop, but leave that to the internal implementations of appropriate classes and functions. Here's an updated version of a Scala class Problem001 with the new method "headedTowardsFunctional" demonstrating a version of the code moved substantially closer towards the functional goal:
object Problem001 extends App {
//http://projecteuler.net/index.php?section=problems&id=1
override def main(args : Array[String]) : Unit = {
javaWithoutSemicolons
headedTowardsFunctional
}
def javaWithoutSemicolons : Unit = {
val floor = 1
val ceiling = 10
val multiple3 = 3
val multiple5 = 5
var sum = 0
for (i <- floor until ceiling)
if ((i % multiple3 == 0) || (i % multiple5 == 0))
sum = sum + i
Console.println("javaWithoutSemicolons.sum=" + sum);
}
def headedTowardsFunctional : Unit = {
val floor = 1
val ceiling = 10
val multiple3 = 3
val multiple5 = 5
val numberRange = floor until ceiling
val validMembers = numberRange.filter(n => {(n % multiple3 == 0) || (n % multiple5 == 0)})
val sum = validMembers.sum
Console.println("headedTowardsFunctional.sum=" + sum);
}
}
In this new method, everything from "numberRange" down is actually a function. As such, we can can use function chaining to reduce the last four lines of code down to one. Here's a new method "mostlyFunctional" with this simplification:
def mostlyFunctional : Unit = {
val floor = 1
val ceiling = 10
val multiple3 = 3
val multiple5 = 5
Console.println("mostlyFunctional.sum=" + (floor until ceiling).filter(n => {(n % multiple3 == 0) || (n % multiple5 == 0)}).sum)
}
Now, to find out the answer to the ProjectEuler problem, I will leave you to figure out how to run this code in either Scala's REPL and/or in your favorite IDE with a Scala plug-in. For those of you who are brand new to programming period, here's a link to a separate page where I take you step-by-step through the process of getting set up so you can get started. And now for a "real world" surprise, a requirements change...
Requirements change (keeping it real):
Or said a slightly different way, slightly changing and expanding the original problem so as to explore code design, refactoring and performance. Using the same basic model in the original problem, find the answer for the following set of problems:
- floor = 1, ceiling = 1000, multiples 2 and 5
- floor = 1, ceiling = 10000, multiples 3, 7 and 10
- floor = 100, ceiling = 1100, multiples 3 and 5
- floor = 1, ceiling = 1000, multiples 2 through 10
- floor = 1, ceiling = 1000000, multiples 2, 3, 5, 7 and 11
Code Refactoring (fancy way of saying "adapting"):
So, how might we go about arranging the code so as to more optimally handle these problems while exploiting other features of Scala. And maybe even adding some more function programming?
The very first and most obvious refactoring is to move the variable definitions out of the body of the function and into the method definition. Luckily, Scala makes this both simple to do and even simpler to use. Here's the first pass at doing so.
mostlyFunctionalWithParameters(1, 10, 3, 5)
...
def mostlyFunctionalWithParameters(floor: Int, ceiling: Int, multiple3: Int, multiple5: Int) : Unit = {
Console.println("mostlyFunctionalWithParameters.sum=" + (floor until ceiling).filter(n => {(n % multiple3 == 0) || (n % multiple5 == 0)}).sum)
}
And it is more functional design to remove the side-effects, of which Console.println() is in this case. The result of this change looks like this:
Console.println("functionalWithParameters.sum=" + functionalWithParameters(1, 10, 3, 5))
...
def functionalWithParameters(floor: Int, ceiling: Int, multiple3: Int, multiple5: Int) : Int = {
(floor until ceiling).filter(n => {(n % multiple3 == 0) || (n % multiple5 == 0)}).sum
}
Most of the time, the value for floor is going to 1. So, wouldn't it be nice to be able to provide a default so it doesn't have to be supplied unless it's different. Here's how that looks:
Console.println("functionalWithParametersDefaultFloor.sum=" + functionalWithParametersDefaultFloor(10, 3, 5))
...
def functionalWithParametersDefaultFloor(ceiling: Int, multiple3: Int, multiple5: Int, floor: Int = 1) : Int = {
(floor until ceiling).filter(n => {(n % multiple3 == 0) || (n % multiple5 == 0)}).sum
}
Optional parameters (any for which a default is provided) must appear at the end of the method's list of parameters. This enables the client to specify by name or position all the required parameters and then selectively specify the optional parameters by name.
So, we now have a pure functional method. However, we are still only allowing for two multiples to be specified. And two of our new problems identify more than two multiples. So, we must re-arrange things so as to enable any number of multiples to be passed in. Scala's simplest and most preferred way to do this is with a List. Rather than try to explain it, here's the code that initially implements it.
Console.println("functionalWithParameters2Multiples.sum=" + functionalWithParameters2Multiples(10, List(3, 5)))
...
def functionalWithParameters2Multiples(ceiling: Int, multiples: List[Int], floor: Int = 1) : Int = {
(floor until ceiling).filter(n => {(n % multiples.head == 0) || (n % multiples.tail.head == 0)}).sum
}
So, the method's signature (parameter specification) is now allowing n multiples. We must now figure out how to check against all of the entries in "multiples" to see if the modulo is 0. The first number that returns a modulo of 0 means we need to indicate the number is valid to be added to the sum. The most obvious way to change this is to create a function which takes the current number as a parameter and then returns true if any entry in the multiples list can be evenly divided by it. That looks something like this.
Console.println("functionalWithParametersNMultiples.sum=" + functionalWithParametersNMultiples(10, List(3, 5)))
...
def functionalWithParametersNMultiples(ceiling: Int, multiples: List[Int], floor: Int = 1) : Int = {
def isMultiple(n: Int) : Boolean = {
var result = false
var list = multiples
while (!result && (list != Nil)) {
result = (n % list.head == 0)
list = list.tail
}
result
}
(floor until ceiling).filter(n => {isMultiple(n)}).sum
}
I like the fact that Scala allowed me to create a helper function within the method that needed it. And notice how the helper function had access to the method's parameters. I didn't have to pass it the "multiples" parameter. It was already in scope for my function.
Now, the "isMultiple" function is still of the imperative style (note there are two variables defined as var). So, what's required to convert this function to be much more of the "functional style"? Not relying upon the vars. And from what I can tell, not being an experienced functional programmer myself, it will tend in the direction of being recursive, i.e. a method that calls itself. If that confuses you, don't worry, it does me too. And for me, it's also an ingrained big NO-NO! For stack based languages (which Java is), it's problematic to use recursion as a stack overflow is so easy to bumble into. However, Scala is not Java and so one is encouraged to find the functional recursive way to resolve a method like "isMultiple". Here's my first bash at it:
Console.println("functional.sum=" + functional(10, List(3, 5)))
...
def functional(ceiling: Int, multiples: List[Int], floor: Int = 1) : Int = {
def isMultiple(n: Int) : Boolean = {
def isMultipleA(list: List[Int]) : Boolean = {
if (list == Nil)
false
else
if (n % list.head == 0)
true
else
isMultipleA(list.tail)
}
isMultipleA(multiples)
}
(floor until ceiling).filter(n => {isMultiple(n)}).sum
}
And there you have it. Moving all the way from the original hard coded "Java without Semicolons" original to the fully functional conclusion. A full version of the final Scala Object class is just beyond the "Extra Bonus Thinking Credit" section.
UPDATE 2011/Jul/16 - 14:21 CDT:
While I was happy with being able to write the recursive loop above when implementing isMultiple(), I was annoyed as it still had a imperative feel to it. The Scala collection library offers numerous ways to solve this kind of problem. And I am just new enough to Scala, it seemed a better way to solve it was just outside my reach of understanding (partly my intuition has not developed around the collections and partly because the Scala syntax is still pretty distracting to me with all the "optional" aspects). However, my mind kept drifting back to this particular aspect of this solution and I continued to be irritated by it.
So, today I decided to try and scratch the itch. I wanted to see if there was some way to write a Scala one-liner for this. There is for the original problem (you can see it above in the mostlyFunctional() implementation - instead of defining the constants above, just place the literals into the 5th line which does all the processing). However, I wanted a one-liner for my "extended requirements" version.
I quickly stumbled upon the "exists()" method in the collections library on List. That seemed to be the right method to use. Now, how to get the two collection library methods, "filter" and "exists" to work together in a single line. I got the right solution the first time. However, I had to take a couple stabs at it as I kept getting the syntax incorrect. Man, am I looking forward to having all the syntax occur as automatic and intuitive to me. It's SO distracting right now.
Anyway, here's the solution where the recursive isMultiple() has been replaced with the exists() method:
Console.println("functional.sum=" + functional(10, List(3, 5)))
...
def functional2(ceiling: Int, multiples: List[Int], floor: Int = 1) : Int = {
(floor until ceiling).filter(n => {multiples.exists(x => (n % x) == 0)}).sum
}
I am very excited about Scala and leveraging it's collections library. It's freaking AWESOME!
Extra Bonus Thinking Credit:
For extra bonus credit, there is a solution that is O(1) for this particular problem. Care to see if you can figure it out?
All Code Collected in Once Place (from above):
object Problem001 extends App {
//http://projecteuler.net/index.php?section=problems&id=1
override def main(args : Array[String]) : Unit = {
javaWithoutSemicolons
headedTowardsFunctional
mostlyFunctional
mostlyFunctionalWithParameters(1, 10, 3, 5)
Console.println("functionalWithParameters.sum=" + functionalWithParameters(1, 10, 3, 5))
Console.println("functionalWithParametersDefaultFloor.sum=" + functionalWithParametersDefaultFloor(10, 3, 5))
Console.println("functionalWithParameters2Multiples.sum=" + functionalWithParameters2Multiples(10, List(3, 5)))
Console.println("functionalWithParametersNMultiples.sum=" + functionalWithParametersNMultiples(10, List(3, 5)))
Console.println("functional.sum=" + functional(10, List(3, 5)))
}
def javaWithoutSemicolons : Unit = {
val floor = 1
val ceiling = 10
val multiple3 = 3
val multiple5 = 5
var sum = 0
for (i <- floor until ceiling)
if ((i % multiple3 == 0) || (i % multiple5 == 0))
sum = sum + i
Console.println("javaWithoutSemicolons.sum=" + sum)
}
def headedTowardsFunctional : Unit = {
val floor = 1
val ceiling = 10
val multiple3 = 3
val multiple5 = 5
val numberRange = floor until ceiling
val validMembers = numberRange.filter(n => {(n % multiple3 == 0) || (n % multiple5 == 0)})
val sum = validMembers.sum
Console.println("headedTowardsFunctional.sum=" + sum)
}
def mostlyFunctional : Unit = {
val floor = 1
val ceiling = 10
val multiple3 = 3
val multiple5 = 5
Console.println("mostlyFunctional.sum=" + (floor until ceiling).filter(n => {(n % multiple3 == 0) || (n % multiple5 == 0)}).sum)
}
def mostlyFunctionalWithParameters(floor: Int, ceiling: Int, multiple3: Int, multiple5: Int) : Unit = {
Console.println("mostlyFunctional.sum=" + (floor until ceiling).filter(n => {(n % multiple3 == 0) || (n % multiple5 == 0)}).sum)
}
def functionalWithParameters(floor: Int, ceiling: Int, multiple3: Int, multiple5: Int) : Int = {
(floor until ceiling).filter(n => {(n % multiple3 == 0) || (n % multiple5 == 0)}).sum
}
def functionalWithParametersDefaultFloor(ceiling: Int, multiple3: Int, multiple5: Int, floor: Int = 1) : Int = {
(floor until ceiling).filter(n => {(n % multiple3 == 0) || (n % multiple5 == 0)}).sum
}
def functionalWithParameters2Multiples(ceiling: Int, multiples: List[Int], floor: Int = 1) : Int = {
(floor until ceiling).filter(n => {(n % multiples.head == 0) || (n % multiples.tail.head == 0)}).sum
}
def functionalWithParametersNMultiples(ceiling: Int, multiples: List[Int], floor: Int = 1) : Int = {
def isMultiple(n: Int) : Boolean = {
var result = false
var list = multiples
while (!result && (list != Nil)) {
result = (n % list.head == 0)
list = list.tail
}
result
}
(floor until ceiling).filter(n => {isMultiple(n)}).sum
}
def functional(ceiling: Int, multiples: List[Int], floor: Int = 1) : Int = {
def isMultiple(n: Int) : Boolean = {
def isMultipleA(list: List[Int]) : Boolean = {
if (list == Nil)
false
else
if (n % list.head == 0)
true
else
isMultipleA(list.tail)
}
isMultipleA(multiples)
}
(floor until ceiling).filter(n => {isMultiple(n)}).sum
}
def functional2(ceiling: Int, multiples: List[Int], floor: Int = 1) : Int = {
(floor until ceiling).filter(n => {multiples.exists(x => (n % x) == 0)}).sum
}
}
