The comments for each optimization should be self explanatory.

package com.sam.twisters.euler;

/*

* A Pythagorean triplet is a set of three natural numbers,

* a < b < c, for which,

* a^(2) + b^(2) = c^(2)

* For example, 3^(2) + 4^(2) = 9 + 16 = 25 = 5^(2).

* There exists exactly one Pythagorean triplet for which a + b + c = 1000.

* Find the product abc.

*/

public class Prog9 {

public static void main(String[] args) {

long startTime = System.nanoTime();

for(int a=1;a<1000;a++){

/*

* Optimization -->for(int b=1;b<1000;b++){ (5 char deleted 1000 added 'a')

* In a Pythagorean triplet a > b & c

*/

for(int b=1;b<a;b++){

/*

* Optimization -->for(int c=1;c<1000;c++){(6 char deleted 1000 added '=b')

*/

for(int c=1;c<=b;c++){

if(a*a == b*b+c*c && a+b+c == 1000){

System.out.println(a*b*c);

/*

* Optimization -->a=1000; (7 char)

* At this point we have found our solution and we need to break out

* of the Loop. Breaking out of the outer for loop makes most sense

*/

a=1000;

}

}

}

}

long estimatedTime = System.nanoTime() - startTime;

System.out.println((float)estimatedTime/1000000000);

}

}

http://www.blogtrog.com/code.aspx?id=d83d3910-5e47-4c86-ae5e-b36ec47f7b57

There were a couple of solutions like,

for(int b=1;b<1000-a;b++){

for(int c=1000-a-b;c<1000;c++){

while this solution works when the sum is 1000 it fails when you go for higher numbers say 10,000 - truth is I think the algorithm at worst is incorrect or at least arbitrary - whats the reasoning behind 1000-b? However since it works for 1,000 I considered these solutions to be correct!

I usually don't reply to all the comments (too time consuming) - but there were plenty of good suggestions/solutions so here my 2 cent.

@Arshia - Nice use of the cut-paste rule. Pretty neat of you to align the code with the comments.

@Sebastian - I think my code is fine. I just renamed the variable - the 'c' in the comments correspond to the 'a' in my code -:). Hence I find a triplet where a*a = b*b + c*c instead of c*c = a*a+b*b - Same thing isn't it?

Reminds me, Trust only the code not the comments!!

@George Pólya - Your solution gets the award for the best abuse of rules -:)! Pretty neat!!

@TheMalkolm - Interesting Idea about posting the fastest code - but it would require analyzing the code - not just running all codes - after all the algorithm might be good for 1000 but what about 10,000 or 100,000?

Plus even if I just decided to run each solution - it's a lot of work - to run each solution to check the amount of time it takes!

@Makkhdn - How did you count 18. I made the exact same changes and counted 12.

I would also like to thank you folks for pointing out the problem you faced while

pasting the solution - with the '<' and '>'. I do have a suggestion folks - instead of posting the long code directly in the comments you could use the excellent service provided by Dave at www.blogtrog.com

You could just paste the link provided by at Blogtrog as the solution - could save a lot of trouble with illegal characters while adding them in comments here.

Re: The reasoning for 1000-b

ReplyDeleteThis is not arbitrary. The solution involved removing the unnecessary third loop making the algorithm something like 0(n^2) instead of O(n^3). There is no need to iterate over more than one value in the most inner loop. If you need to find a triplet whose sum is a given value, it is always enough to use all possible combinations of two of the values and determine the only possible for the 3rd one, which in this case is 1000 - a - b.

So the only check that needs to be performed in the loop is whether a*a = b*b + c*c. The way c has been assigned the sum constraint (a+b+c=1000) does not need to be checked.

This solution works very well for numbers other than 10000. You have to replace the other "1000" constants, too.

My solution took less then 14 seconds for 100.000, IIRC.