Wednesday, June 24, 2009

Puzzle 36 – Triple the fun (Optimization Series puzzle - 2)

Language – Java | Type – Concept | Last date 28-Jun-2009 9:00 p.m. IST | Points 3

If you have not looked at code optimization puzzle before – I would suggest having a look at the
first one!

Unlike the previous puzzle where the un-optimized code took over 30 minutes to run, I have already done a pretty good job on this one. It executes in about 5 seconds. Well 5 seconds is still a lot of time. Can you get it to execute in less than half a second?


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 each possible pair of numbers below 1000
* check if there is a Pythagorean triplet for which a + b + c = 1000.
*/
for(int a=1;a<1000;a++){
for(int b=1;b<1000;b++){
for(int c=1;c<1000;c++){
if(a*a == b*b+c*c && a+b+c == 1000){
System.out.println(a
*b*c);
}
}
}
}

long estimatedTime = System.nanoTime() - startTime;
System.out.println((
float)estimatedTime/1000000000);
}
}

http://www.blogtrog.com/code.aspx?id=bd1246e9-25f6-4f9a-b983-486745ae457c

Rules? Same as before –

1. This code takes about 5 seconds to run. Get it to run in under half a second.
2. You see while it’s really great that you have decided to help me – I really don’t want you to mess up my entire code. So here is the deal – you can change a maximum of 18 characters (yes that’s all).
3. What constitutes a character change?
a. Inserting a character – each character (including space) that you add to the existing code.

b. Deleting a character – each character (including space) that you delete from the existing code.

c. Over writing a character – well you cannot do that. You could delete and insert but you cannot over write.

d. Cut Paste - Special Rule for cut paste is you can cut code from the existing code and paste it somewhere (except inside a comment) else in the code without using up a single char.
Just remember its cut-paste and not copy-paste.

Hint – There are a few comments in the code, I sure there is something there that might help!

If optimizing a code that runs in 4 seconds does not sound like a challenge – try the same code expect that instead of the sum equaling 1000 (a+b+c=1000), try for 10,000 or 100,000.

Got an answer? Do leave it here.

10 comments:

  1. Cut and paste c*c to where a*a is followed by another cut and paste of a*a to where c*c originally was. Add 2 characters so b=a+1 and another 2 characters to set c=b+1. Add a conditional on the second for loop as " && a+b<1000" which is another 12 characters with spaces for a total of 16 characters to get:

    for(int a=1;a<1000;a++){
    for(int b=a+1;b<1000 && a+b<1000;b++){
    for(int c=b+1;c<1000;c++){
    if(c*c == b*b+a*a && a+b+c == 1000){
    System.out.println(a*b*c);
    }
    }
    }
    }

    With the resultant output as follows:

    31875000
    0.479309

    ReplyDelete
  2. line 20: b(smallerThan)1000 && b(smallerThan)a
    line 21: c(smallerThan)1000 && c(smallerThan)b

    That should do it =)
    (replace smallerThans by correspondant Java operator)

    ReplyDelete
  3. This is a solution that uses about 17 changes and runs in less than 5 milliseconds:

    for(int a=1;a<;1000;a++){
    for(int b=a;b<;1000;b++){
    /*for(*/int c=1000-a-b;//c<;1000;c++){
    if(a*a + b*b == c*c && a+b+c == 1000){
    System.out.println(a*b*c);
    //}
    }
    }
    }

    (That same code still runs in just two tenths of a second for 10.000)

    The problem is that there is a bug in the original code which needed to be fixed. The theoreme states that a < b < c and the code checks for a^(2) = b^(2) + c^(2) instead of
    a^(2) + b^(2) = c^(2) (as shown in the comments).
    Note there is no triplet that fulfills this because the sum of the squares of two values that are greater than another value will always be greater and thus it will never work. So the initial code is wrong (although it generates the right product).
    I had to do more than the allowed number of changes but that was just to correct the code check!

    The probably anticipated solution that runs in about half a second and requires 10 character changes would have been:

    for(int a=1;a<;1000;a++){
    for(int b=1;b<;a;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);
    }
    }
    }
    }

    But the triplet that is found is not ordered correctly either. However all of this is just a matter of reinterpreting (renaming) the variables.

    So using the the cut-paste special rule (for switching variables in the loops) I get this solution:

    for(int c=1;c<;1000;c++){
    for(int b=c;b<;1000;b++){
    //for(
    int a=1000-c-b;//a<;1000;a++){
    if(a*a == b*b+c*c && a+b+c == 1000){
    System.out.println(a*b*c);
    }

    }
    }

    Which makes 15 changes if my count is correct and runs in 1.5 milliseconds (I had to run the code a hundred times because nanotime is not accurately enough for just one run)

    BTW: the comment field does not accept the < sign - escaping them by hand is pretty annoying

    ReplyDelete
  4. From 2.70s to 0.05s with a total of 17 changes:

    triplet: // added colon: 1 change, cut&pasted "triplet" from comments
    for(int a=1;a<1000;a++){
    for(int b=1;b<a;b++){ // delete "1000", add "a": 5 changes
    for(int c=1;c<b;c++){ // delete "1000", add "b": 5 changes
    if(a*a == b*b+c*c && a+b+c == 1000){
    System.out.println(a*b*c);
    break triplet; // add "break;": 6 changes, cut&pasted " triplet" from comments
    }
    }
    }
    }

    ReplyDelete
  5. 20 for(int b=1;b<1000-a;b++){
    21 for(int c=1000-a-b;c<1000;c++){
    ...
    24 }break;

    Changes: 2 (line 20) + 7 (line 21) + 6 (line 24) = 15

    Time: 0.0086187925

    ReplyDelete
  6. for (int a = 1; a < 1000; a++) {
    for (int b = 1; b < 1000-a; b++) {
    for (int c = 1000-a-b; c <= 1000 -a-b; c++) {
    if ((a * a == b * b + c * c) && (a + b + c == 1000)) {
    System.out.println(a * b * c);
    }
    }
    }
    }

    This code runtime is about 0.2% of original at my comp. A lot better than u asked (10%)

    Would u write the fastest one in the solution post?

    ReplyDelete
  7. I found two ways

    17 moves and keep the original result:
    for (int a = 1; a < 1000; a++) {
    for (int b = 1; b < 1000-a; b++) {
    for (int c = 1; c <= 1000-a-b; c++) {
    if (a + b + c == 1000 && a * a == b * b + c * c) {
    System.out.println(a * b * c);
    }
    }
    }
    }

    18 moves and go slightly faster :
    for (int a = 1; a < 1000; a++) {
    for (int b = 1; b < a; b++) {
    for (int c = 1; c < b; c++) {
    if (a + b + c == 1000 && a * a == b * b + c * c ) {
    System.out.println(a * b * c);
    }
    }
    }
    }

    ReplyDelete
  8. for(int a=1;a<1000;a++){
    for(int b=1;b< a;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);
    }
    }
    }
    }

    ReplyDelete
  9. b and a aren't good variable names for blogspot, because you'll get such messages:

    Your HTML cannot be accepted: Tag is broken

    ReplyDelete
  10. Also we could calculate that A is less than 500 actually. It comes from:

    a + b + c = 1000;
    a**2 = b**2 + c**2;

    a = 500 - b*c/1000;

    So my previosly solution could be optimized even more :)

    for (int a = 1; a < 500; a++){
    for (int b = 1; b < 1000-a; b++){
    for (int c = 1000-a-b; c <= 1000 -a-b; c++){
    if ((a * a == b * b + c * c) && (a + b + c == 1000)){
    System.out.println(a * b * c);
    }
    }
    }
    }

    ReplyDelete

Solution for this question?