5
\$\begingroup\$

I have finished Project Euler #9 on HackerRank:

Given \$N\$, Check if there exists any Pythagorean triplet for which \$a+b+c=N\$, \$a^2+b^2=c^2\$. Find maximum possible value of \$abc\$ among all such Pythagorean triplets, and if there is no such Pythagorean triplet print −1.

However, I feel uncomfortable about my code. I think it is sort of spaghetti code that is neither well organized nor fast (just a feeling).

Optimization and simplification is needed. (For example, there are many nested ifs).

#include <stdio.h>
#include <time.h>
int main()
{
  clock_t start = clock();
  unsigned int i,j,t,n;
  long p;
  scanf("%u",&t);
  while(t>0)
  {
    p =-1;
    i=2;
    j=1;
    scanf("%u",&n);
    while(1)
    {
      int s = 2*i*i+2*i*j;
      if(s ==n )
      {
        long o = 2*i*j*(i*i+j*j)*(i*i-j*j);
        if (p<o) p =o;
        if(i>j+1) j++;
        else
        {
          j=1;
          i++;
        }
      }
      else if(s>n)
      {
        if(j==1) goto end;
        j=1;
        i++;
      }
      else
      {
        int counter;
        for(counter =2; s*counter<=n;counter++)
        {
          if(s*counter == n)
          {
            long o = 2*i*j*(i*i+j*j)*(i*i-j*j)*counter*counter*counter;
            if (p<o) p =o; 
          }
        }
        if(i>j+1) j++;
        else 
        {
          j=1;
          i++;
        }
      }
    }
    end: printf("%li\n",p);
    t--;
  }
  clock_t end = clock();
  printf("time in milliseconds %lf\n",(double)(end-start)*1000/CLOCKS_PER_SEC);
  return 0;
}
\$\endgroup\$
  • \$\begingroup\$ I would argue that you should leave your timing code out of your program, as this is extra cruft that takes up a bit of time and isn't part of the challenge. Use the bash command time to check how long it takes your program to run instead. \$\endgroup\$ – syb0rg May 17 '15 at 21:15
5
\$\begingroup\$

No explanation for code

I realize that this is a programming challenge and therefore your solution will probably have a minimum of comments. But without comments and without any help in your question itself, it was hard to figure out what your code was doing. I eventually figured out that you were using a so-called "quadratic equation method" for finding pythagorean triples, but it would have been helpful to have some kind of explanation somewhere.

Variable names

The question asked about pythagorean triples with A, B, C, and N. But your code had all sorts of one letter variables i, j, s, o, p. Obviously, these are not the best of variable names. Even if you think you might not be showing this to someone else, you might come back a few years later to look at this code and have a hard time figuring out what all of these variables meant. It's not too hard to at least use "sum" and "product" instead of "s" and "p".

Variable scopes

It's a good idea to limit variable scopes to the blocks where they are used. Many of your variables such as i, j, and n could be reduced in scope. You did already do this for s and counter.

Goto end

You can replace your goto end with a simple break.

The algorithm

The first improvement to the algorithm is that the s == n case and the s < n case are identical.

The second improvement to the algorithm is that you don't need to have a loop in order to determine counter. What you are doing is essentially dividing n by s, so you can just use a single division instead of a loop.

The rewrite

I rewrote your code with comments and all of the above fixed up to show you what it would look like:

#include <stdio.h>
#include <time.h>
int main(void)
{
    clock_t start = clock();
    unsigned int numTests;
    scanf("%u",&numTests);
    // Finds pythagorean triples of the form: a^2 + b^2 = c^2, a + b + c = n
    //
    // Where:
    //
    // a = i^2-j^2
    // b = 2*i*j
    // c = i^2+j^2
    //
    // Therefore, n = a+b+c = 2*(i^2) + 2*i*j
    while (numTests > 0) {
        unsigned int i = 2;
        unsigned int j = 1;
        unsigned int n;
        long maxProduct = -1;

        scanf("%u",&n);
        while(1) {
            int sumABC = 2*i*i+2*i*j;
            if (sumABC > n) {
                if (j==1)
                    break;
                j=1;
                i++;
            } else {
                if (n % sumABC == 0) {
                    int counter = n / sumABC;
                    long product = 2*i*j*(i*i+j*j)*(i*i-j*j)*
                                    counter*counter*counter;
                    if (maxProduct < product)
                        maxProduct = product;
                }
                if (i>j+1) {
                    j++;
                } else {
                    j=1;
                    i++;
                }
            }
        }
        printf("%li\n", maxProduct);
        numTests--;
    }
    clock_t end = clock();
    printf("time in milliseconds %lf\n",(double)(end-start)*1000/CLOCKS_PER_SEC);
    return 0;
}
\$\endgroup\$
5
\$\begingroup\$

Just few remarks:

  1. Variables with meaningful names are more useful and make the code easier to read and understand.
  2. Comments add to code clarity and could possibly point to fragments that can be optimized.
  3. Use a more compact brace style.

    int foo()
    {
        for
          {
              //...
          }
    }
    

    could become

    int foo(){
        for{
             //...
           }
    }
    
  4. Add white space between operands and operations: (a + b; a == b; a = 1).

  5. Consistency and style: eliminate random white spaces/ indentations in expressions (p =1, p=1 or p= 1)
  6. Brake the code into functions, each with single task.
\$\endgroup\$
  • 1
    \$\begingroup\$ I think that breaking code into functions is not good idea (in case of running competition code) because function calling conventions will consume cpu cycles and thus increase the run time \$\endgroup\$ – oddcoder May 17 '15 at 22:04
  • 3
    \$\begingroup\$ @AhmedAbdElMawgood You should definitely break out at least one function maxPythagoreanProduct(int n). That isolates your computation code from the test case run loop. The overhead for that call is trivial to non-existent, and lumping everything into main() is a misguided optimization. \$\endgroup\$ – 200_success May 18 '15 at 5:47
  • 2
    \$\begingroup\$ The brace style in the original code is problematic not so much in that it wastes lines, but that it encourages the omission of braces in an effort to save lines — and that is certainly happening in this code. \$\endgroup\$ – 200_success May 18 '15 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.