Euler was groovy too
I recently stumbled across Project Euler, which is a hip website containing quite a few different math challenges. The idea being that people can attempt to solve any particular challenge which ever way they can (that is, in any language and with any algorithm) — the site doesn’t provide answers either — you must create an account and submit your answer. Project Euler will then check your answer and issue a response — correct or incorrect. If it’s your bag and you Google the project, you’ll find some interesting posts solving various problems in various languages ranging from F# to Scala to C (and everything in between). What’s also interesting is that each post for a problem usually is different in some way or another, which of course provides some interesting learning opportunities.
Problem 1 entails figuring out the sum of numbers divisible by 3 and or 5:
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.
I thought it would be interesting to see if I could solve this in Groovy as the solution clearly deals with iterating over a series of numbers — and as everyone who has played with Groovy (or some other dynamic language for that matter) knows, iteration is a blast, baby!
Accordingly, my first pass yielded the following code:
def sum = 0
(1..<1000).each{
if((it % 5 == 0) || (it % 3 == 0)){
sum += it
}
}
assert sum == /* do it yourself, baby! */Note that I’m using Groovy’s exclusive range feature to easily iterate over all numbers less than 1000. I then proceed to use Groovy’s it variable, which represents the current value in the iteration (i.e. 1, 2, 3, etc) and test the instance with Java’s modulo operator (that is, modulo returns the remainder of division — 10 modulo 5 is 0, but 11 modulo 5 is 1). If there is a match, I add it to the sum variable. This is programming 101 and brought me back to the Age of Aquarius, baby!!
That was easy enough; however, I wanted to see if I could do away with the sum variable by using one of Groovy’s many hip magic methods attached to collections. Thus, my second attempt leverages Groovy’s findAll method, which permits putting a condition in the resulting closure, which then returns a collection meeting that criteria. Accordingly, with the returned collection of numbers meeting my criteria (that is, any number that is divisible by 5 or 3), I then have to issue the sum method like so:
def val = (1..<1000).findAll{(it % 5 == 0) || (it % 3 == 0)}
assert val.sum() == /* you gotta figure it out yourself, man! */Groovy’s sum method is straight forward — it takes all the values in a collection (presumably add-able) and adds them up!
Admittedly, the second example is a bit harder to read (at first glance, that is) but it sure is a bit more aesthetic than the first brute force bogue example, isn’t it?
| Related odds and ends | ||
|---|---|---|
16 comments Wednesday 01 Jul 2009 | Groovy, Languages, Software Development
16 Responses to “Euler was groovy too”
[...] via The Disco Blog [...]
You can also use groovy’s inject() and a ternary operator:
(1.. (i%5 == 0 || i%3 == 0) ? total + i : total }
Make that:
(1..<1000).inject(0){ total, i -> (i%5 == 0 || i%3 == 0) ? total + i : total }Good call on using inject Joe!
Sprinkle in some Groovy Truth and we can boil it down to:
(1.. sum += (n % 5 && n % 3) ? 0 : n }
http://groovy.codehaus.org/Groovy+Truth
Lets try that again with HTML formatting…
(1.. sum += (n % 5 && n % 3) ? 0 : n }[...] This post was Twitted by groovytweets [...]
I have a whole bunch of the Euler examples solved in Groovy if anyone is interested. I haven’t published them yet though might some day – happy to share if anyone is interested.
Yeah, solving with groovy is fun, but, unfortunately, for some tasks (after 50′th or so) is too slow
Yeah, iterating is an option, but you can think more mathematically
The multiples of 3 under 1000 are 3, 6, 9, …, 999, right? The multiples of 5 under 1000 are 5, 10, 15, …, 1000, right? The sums of the multiples (actually, an arithmetical progression) are:
(firstElement + lastElement) * (numberOfElements / 2)
But there are numbers both multiple of 3 and of 5, so we have to subtract them from the total.
My implementation got bigger than what I thought at first, but the bigger part is the gcd and lcm values, which are important to find the multiples of both 3 and 5. Have fun
int gcd(int a, int b) {
// http://www.idevelopment.info/data/Programming/data_structures/java/gcd/GCD.java
// If a is lesser then b, swap them
if (a < b) {
int t = a;
a = b;
b = t;
}
r = a % b
r == 0 ? b : gcd(b, r)
}
int lcm(int a, int b) {
(a * b) / gcd(a, b)
}
int sumOfMultiples(int base, int ceiling) {
// The biggest multiple below the ceiling is the last number
// of the sequence
int biggestMultiple = ceiling – (ceiling % base)
int multiplesCount = ceiling / base
(base + biggestMultiple) * (multiplesCount / 2)
}
sumOfMultiplesOf3 = sumOfMultiples(3, 1000)
sumOfMultiplesOf5 = sumOfMultiples(5, 1000)
lcmOf3And5 = lcm(3, 5)
sumOfMultiplesOfLcm = sumOfMultiples(lcmOf3And5, 1000)
println “The result is ${sumOfMultiplesOf3 + sumOfMultiplesOf5 – sumOfMultiplesOfLcm}”
Oops, there are some places thar need int coertion to use the integer division correctly. New version (it realy messes the indentation):
package teste
int gcd(int a, int b) {
// http://www.idevelopment.info/data/Programming/data_structures/java/gcd/GCD.java
// If a is lesser then b, swap them
if (a < b) {
int t = a;
a = b;
b = t;
}
r = a % b
r == 0 ? b : gcd(b, r)
}
int lcm(int a, int b) {
(int)((a * b) / gcd(a, b))
}
int sumOfMultiples(int base, int ceiling) {
// The biggest multiple below the ceiling is the last number
// of the sequence
int biggestMultiple = ceiling – (ceiling % base)
int multiplesCount = (int)(ceiling / base)
(base + biggestMultiple) * (int)(multiplesCount / 2)
}
sumOfMultiplesOf3 = sumOfMultiples(3, 1000)
sumOfMultiplesOf5 = sumOfMultiples(5, 1000)
lcmOf3And5 = lcm(3, 5)
sumOfMultiplesOfLcm = sumOfMultiples(lcmOf3And5, 1000)
println “The result is ${sumOfMultiplesOf3 + sumOfMultiplesOf5 – sumOfMultiplesOfLcm}”
> Yeah, solving with groovy is fun, but, unfortunately, for some tasks (after 50?th or so) is too slow
I have solved up to around 70 with no problems on timing – well lots of problems if you try brute force hence the goal of Euler to apply mathematics too.
((3..<1000).step(3) + (5..<1000).step(5)).unique().sum()
will also do the trick.
I’ve been using groovy to solve Euler problems too. I find it a good way to learn groovy.
[...] Euler was groovy tooAsserting Ajax actionsBethinking Java’s past and prospects [...]
Hehehe – I think you’ve been out discoing too late. A classic real world requirements mix-up:
YOur summary above:
“Problem 1 entails figuring out the sum of numbers divisible by 3 *and* 5:”
is significantly different to “3 *or* 5″….
Sorry, couldn’t resist :->
Good catch, Rich– indeed, a slight difference in meaning changes everything. For the record, it should read or and not and. I’ll make the correction in this post too. Thanks!