views:

1270

answers:

6

I am solving problem 9 on the Project Euler. In my solution I use a "goto" statement to break out of two for loops. The Problem is the following:

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 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

My solution is in c++:

int a,b,c;
const int sum = 1000;
int result = -1;
for (a = 1; a<sum; a++){
 for (b = 1; b < sum; b++){
   c = sum-a-b;
   if (a*a+b*b == c*c){
    result = a*b*c;
    goto found;
   }
 } 
}
found:
std::cout << "a:" << a << std::endl;
std::cout << "b:" << b << std::endl;
std::cout << "c:" << c << std::endl;
std::cout <<"Result:" << result << std::endl;

Since "goto" statements are not very popular among c++ programmers, i would like to know, if this could be considered a reasonable use of "goto". Or if there is a better solution for the problem that doesn't need "goto". By that I don't mean a solution which just avoids "goto", but which avoids "goto" in a way that improves the algorithm.

+3  A: 

I can't think of a better alternative. But one alternative not using goto would be modifying the first for-loop:

for (a = 1; a<sum && result == -1; a++){

Then break out of the second for-loop. That will work assuming the result will never be -1 after the second for-loop has been broken by break.

Blixt
I don't see this as better. You are making the code harder to read as you are adding more conditions to the test.
Martin York
And you're right. As I said, I couldn't think of a better alternative, I just showed a way to avoid the goto loop without altering the code considerably.
Blixt
I'd like to add that Alex Martelli's solution is of course better. Encapsulating it in a function is probably the best solution in this case.
Blixt
+2  A: 

You could declare a bool found = false at the top and then add && !found to your for loop conditionals (after a < sum and b < sum) and then set found to true where your current goto is. Then make your output conditional on found being true.

jeffamaphone
+3  A: 

I just found this on the "Related" sidebar. An interesting thread overall, but in particular, this is an answer to my question.

Lucas
+4  A: 

See this question about breaking out of 2 loops. There are much better answers provided than using a goto.

The best answer provided is to place your second loop into a function, and call that function from inside your first loop.

code copied from mquander's response

public bool CheckWhatever(int whateverIndex)
{
    for(int j = 0; j < height; j++)
    {
        if(whatever[whateverIndex][j]) return false;
    }

    return true;
}

public void DoubleLoop()
{
    for(int i = 0; i < width; i++)
    {
        if(!CheckWhatever(i)) break;
    }
}

Though I do feel that using a goto in this case isn't quite as bad as killing kittens. But it's close.

Matthew Vines
How have we all got brain washed? :) The resulting structure of this code is more "complex" than using goto (due to the additional 'if-statement' in DoubleLoop). Splitting the code out may also reduce the set of optimisations that a compiler can make - for example a variable that is local to "CheckWhatever" potentially could have been optimised to be outside the enclosing loop.
Richard Corden
+34  A: 

return is a "structured" goto which many programmers find more acceptable! So:

static int findit(int sum, int* pa, int* pb, int* pc)
{
    for (int a = 1; a<sum; a++) {
        for (int b = 1; b < sum; b++) {
            int c = sum-a-b;
            if (a*a+b*b == c*c) {
                *pa = a; *pb = b; *pc = c;
                return a*b*c;
        }
    }
    return -1;    
}

int main() {
    int a, b, c;
    const int sum = 1000;
    int result = findit(sum, &a, &b, &c);
    if (result == -1) {
        std::cout << "No result!" << std::endl;
        return 1;
    }
    std::cout << "a:" << a << std::endl;
    std::cout << "b:" << b << std::endl;
    std::cout << "c:" << c << std::endl;
    std::cout <<"Result:" << result << std::endl;
    return 0;
}
Alex Martelli
+1: if it's complex enough to consider a goto, it's complex enough to encapsulate in a function and avoid the goto.
John Pirie
Yep. Don't complicate the loops.Just get out. Perfect solution. But you could pass a,b,c by reference. Then you don't need to mess around with pointers.
Martin York
Thank you, this is a nice solution. It doesn't make the code less readable.
Lucas
@Lulu, glad you liked it. @Martin, sure, you can use references instead of pointers -- having been with Google for many years now, I tend to mostly like and use our style guide, see http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Reference_Argumentsfor more discussion of why and how, anyway the style boils down to "input arguments are values or const references while output arguments are pointers. Input parameters may be const pointers, but we never allow non-const reference parameters".
Alex Martelli
@Alex, I agree coding standards are great and should be followed where appropriate. But: They are only guidelines, this is a situation that screams for the use of references. Otherwise you should be checking for NULL!
Martin York
Alex Martelli
The only downside to this approach is that, in ducking a fight with the "NEVER USE GOTO!!!" crowd, you run straight into a fight with the "FUNCTIONS MUST ONLY HAVE ONE RETURN!!!" crowd. So taking this approach because you like it, feel that "findit" is a good abstraction, and are willing to defend it, is fine. Taking this approach solely in order to avoid a goto is futile.
Steve Jessop
@Alex: if you want your function to be a good citizen of the world, then you might consider standard (C) functions like "time()", which allows the outparam to be NULL just in case some caller only needs the return value. If it's a private function which will only ever be called from one place, in order to make the calling function body be fewer loc, then obviously you do whatever. It may well get inlined anyway...
Steve Jessop
@onebyone, sure, there's all sort of fundamentalists;-), but "single return"ites are pretty thin on the ground at any place I'd care to work for: differently from gotophobia (a benign ailment which has been observed in excellent programmers, due to being scarred by past encounters with spaghetti code), monoreturnitis is a malignant (though fortunately rare) syndrome requiring drastic therapy...;-)
Alex Martelli
@onebyone again, making it `static` to indicate it's not supposed to be called from "outside" is a good idea -- editing the answer now to add that bit.
Alex Martelli
Excellent. So all that's left is the battle to the death and blood-feud-to-the-seventh generation, about how multiple return values should be handled. I'm saying you need "class PythagoreanTriple : private boost::tuple<int,int,int>" ;-)
Steve Jessop
Personally I like returning tuples (I'm a Python developer after all!-), but "output parameters" have a long and proud tradition (and can save some machine cycles) so I doubt they'll be eradicated from C and C++ any time soon (or ever;-).
Alex Martelli
+9  A: 

IMO using a goto is fine in these situations.

Btw, the condescending preaching against goto usually comes from people who just parrot what they heard others say or read somewhere..

StackedCrooked
Java has named loops, which are pretty much identical to this
Casebash