This puzzle has loads of possible optimization – here are my action packed 18 characters!
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);
}
}
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.