Shaun Abram
Technology and Leadership Blog
Subscribe to RSS FeedProject Euler: Problem 4 (in Groovy)
Problem 4 in Project Euler is as follows:
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.
I found this problem significantly easier than problem 3, thankfully.
My first step was to write a helper method:
boolean isPalindrome(int num)
My first attempt was, as usual, the brute force approach. Namely, go through every number from 100 to 999 and for each, multiply it by every number between 100 and 999. Check if the result of each of the roughly one million calculations is a palindrome – and store it if it is the biggest one yet.
My next approach was better and involved starting from the top (999 to 100) instead of the other way round. This means we can check if the largest palindrome we could possible find is smaller than what we have already found, thereby avoiding a large number of useless calculations.
This gave me a solution that runs in approx 500ms on my local PC.
Here is my final solution:
int largestPalindrome = 0;
for (i in 999..100) {
if ( (i*i) < largestPalindrome) {
//the largest possible number we can now find (i*i)
//is smaller than the biggest palindrome already found
break;
}
for (j in i..100) {
int candidate = i*j;
if ( candidate < largestPalindrome) {
//largest number we can now find in this inner loop
//is smaller than the biggest palindrome already found
break;
}
if (isPalindrome(candidate)) {
if (candidate>largestPalindrome) {
largestPalindrome = candidate;
break;//no point checking smaller numbers of j
}
}
}
}
println("largestPalindrome);
And finally, my isPalindrome method:
public static boolean isPalindrome(Integer num) {
boolean isPalindrome=true;
char[] numChars = num.toString().toCharArray();
int endPoint = numChars.length() - 1;
int midPoint = numChars.length() / 2;
for (i in 0..midPoint) {
char a = numChars[i];
char b = numChars[endPoint-i];
if (a != b) {
isPalindrome=false;
break;
}
}
return isPalindrome;
}
Groovy: Cool but slow
I have been learning Groovy recently (as part of Project Euler, a series of Maths programming problems). For the most part, I love it. I particularly like
the easy syntax. Java without the crud!
e.g.
System.out.printlnbecomes simplyprintlnfor (int i-0; i<10; i++)becomesfor ( i in 0..9 )- Accessor methods are autogenerated and used
Sure, the poor IDE support is a little annoying, especially the lack luster code completion and debugging capabilities, but I am sure it will improve soon (especially with SpringSource on the case).
But then I started to notice some slowness when using it. So, I performed a simple performance comparison and the results shocked me.
I wrote an identical loop in both Java and Groovy (see the code below) which simply loops a million times.
- The Java version took ~5ms
- The Groovy version took ~500ms
I was shocked! Could Groovy really be a 100 times slower? I had heard rumors about Groovy being a bit slower than Java, but I hadn't expected it to be this dramatic. Surely this is drastic enough to stop Groovy being used in serious, production quality projects?
I discussed this with a friend who is a Groovy advocate. He made the following points:
1. I was running with an older, slower version of Groovy
This is true. I ran the tests in Eclipse 3.5, with v1 of the Eclipse Groovy plugin, which uses v1.5.7 of the Groovy compiler.
However, when I downloaded the latest version of Groovy (Version: 1.6.3 with JVM: 1.6.0_13) and ran from the command line, it still took the Groovy code ~200 ms. A huge improvement, but still ~40 times slower than Java.
2. It is an artificial, unrealistic test, as these kind of huge loops are not normal in most programs
This is also true. But although artificial, it is still a straight comparison. Also, these kind of loops aren't so unusual in Project Euler type problems (at least in my crude brute force solutions!).
There are also some more detailed Java/Groovy performance test results here and here.
So, overall, I think the performance is a big issue. But not enough to stop me using it for pet projects. I am even going to keep trying to use it for Project Euler - it will be more motivation to avoid the brute force solutions. It is however, enough to stop me using it in any serious production apps.
For the record, here is the exact code I ran:
Java version
long max = 1000000;
long start = Calendar.getInstance().getTimeInMillis();
for(int i=0;i
Groovy version
long max = 1000000;
long start = Calendar.getInstance().getTimeInMillis();
for(int i=0;i
It is also worth pointing out that when I changed the Groovy code to use proper Groovy syntax, as in for (i in 1..1000000) is was substantially faster (although still significantly slower than Java), but I have left it as is, for a apples vs apples comparison.
Tags: groovy
Project Euler, Problem 2 (in Groovy/Java)
Problem 2 in Project Euler is as follows:
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Find the sum of all the even-valued terms in the sequence which do not exceed four million.
I found it fairly easy to code a basic solution to this problem:
def fibSeries = [0,1]
int sumOfEvenNums = 0
int i = 0
while (fibSeries[i]<=4000000) {
i = fibSeries.size
fibSeries[i] = fibSeries[i-1]+fibSeries[i-2]
if (fibSeries[i]%2==0) {
sumOfEvenNums+=fibSeries[i]
}
}
println("Total = " + sumOfEvenNums)
This ran relatively quickly (~100ms), so I submitted my answer on projecteuler.net and it was confirmed as correct.
With heinsight, I realise that it is unnecessary for me to store the entire sequence of numbers (in fibSeries). I just need to store 3 numbers: the latest and the previous 2.
After checking the solution notes, there is of course a more 'perfect' solution. Reaching it involves making 2 breakthroughs, which I admit I didn't make on my own!
Breakthrough 1
The first breakthrough is to see the pattern (how could I have missed it!) that only every 3rd number is even, meaning we can safely ignore the rest. The provided solution says that this is easy to prove (I have no idea how to - perhaps a step for another day). But assuming this to be true, the code can be rewritten to
int a,b,c
b = 1 //1st seed value
c = 1 //2nd seed value
int sumOfEvenNums = 0
while (c<=4000000) {
a=b+c
b=c+a
c=a+b
sumOfEvenNums+=a
}
println("Total = " + sumOfEvenNums)
Breakthrough 2
The second, and waaay more difficult breakthrough is to spot (and prove!) that there is a pattern in the even numbers. If you look at them,
2, 8, 34, 144, 610, ...
They obey following recursive relation:
E(n)=4*E(n-1)+E(n-2).
e.g. 144=4(34) + 8
and 34 = 4(8) + 2
It can be proved that for the Fibonacci numbers, the formula F(n)=4*F(n-3)+F(n-6) holds true (I even managed to get the proof of this myself, after a little prodding).
So, this leaves the following 'ultimate' solution:
int a = 0
int b = 8 //1st seed value
int c = 2 //2nd seed value
int sumOfEvenNums = b+c
while (true) {
a=(4*b)+c
if (a>4000000) break
sumOfEvenNums+=a
c=b
b=a
}
println("Total = " + sumOfEvenNums)
I am sure this could even be rewritten in a more elegant form. Especially if Groovy supported a do..while loop.
Anyway, on to Problem#3...
Project Euler, Problem 1 (in Groovy/Java)
I have been wanting to get up to speed with Groovy for while but hadn’t really found a good excuse. So when I came across Project Euler, I decided to try to solve the problems using Groovy.
I managed to solve Problem#1 today.
Note that I would describe the solutions below as being in Groovy/Java because I still fall back on my old Java habits rather than using all the Groovy language constructs available to me. Anyway…
The problem is:
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.
Unsurprisingly, I took the brute force approach first:
int n = 999, total=0;
for (int i in 1..n) {
if ( (i%3==0) || (i%5==0) ) {
total=total+i;
}
}
println("Total=" + total)
A good first start, but far from perfect as it loops through every number between 1 and n. I could improve it slightly by tweaking the start and end points (e.g. starting at 3), but it would still roughly involve n iterations.
My second attempt was this:
int n = 999, total=0;
Set nums = new HashSet();
for (int i=3; iProblem#2...
TheServerSide Java Symposium – Day 2
Day 2 at TSS Java Symposium.
The highlights of the second day at TSSJS2009 were a couple of interesting talks from Rod Johnson (Mr Spring) and a talk on Groovy from Scott Davis (Groovy.com).
I have included links to some of my (limited) notes below, which includes links to the actual presentation slides (PDFs) where available.
Keynote: How Spring Fits into the Java Landscape – Rod Johnson
Spring for the advanced developer – Rod Johnson
The Amazing Grrovy Weight Loss Plan – Scott Davis
Tags: groovy, spring, theserverside, tss