Breaking nested while loops with boolean

Question

So my program tries to find Pythagorean Triplet, where a^2 + b^2 = c^2 AND a+b+c=1000. So everything works well, but program finds the answer quite early in the program runtime, so I would like to break somehow out of all the loops. I am trying simple boolean method, but for some reason my cycle stops after 1 second. If I remove exit = True then everything works (but no break obviously).

P.s. it's also same problem if I use simple 0 or 1 integers to check that. Can anyone give me ideas why this is not working?

i = 0
j = 0
k = 0
exit = False
while (i < 999 and exit == False):
    while (j < 999 and exit == False):
        while (k < 999 and exit == False):
            if i*i + j*j == k*k:                        
                if i + j + k == 1000:
                    exit = True
                    ii = i
                    jj = j
                    kk = k
            k += 1
        j += 1
        k = 1
    i += 1
    j = 1
i = 1
print('result: %d^2 + %d^2 = %d^2' % (ii, jj, kk))

Answer 1

The specific problem you have is simply that your code does meet the criteria you set, when

ii == 0
jj == 500
kk == 500

If you don't want this trivial solution, you should initialise to 1 at the start (or, better, spot the trivial opportunity to factor out duplication and set e.g. j = 1 in only one place).

Answer 2

Make it a Generator Function:

>>> def pythagorean_triangles(target):
...     for a in range(1, target):
...         for b in range(1, target):
...             for c in range(1, target):
...                 if a ** 2 + b ** 2 == c ** 2 and a + b + c == target:
...                     yield a, b, c
...
>>> triangles = pythagorean_triangles(1000)
>>> next(triangles)
(200, 375, 425)

Answer 3

Functions are a great way to do this early exit logic. I've also switched your loops to use the xrange() builtin, which cleans up some of your surrounding logic.

def triplet():
    for i in xrange(1000):
        for j in xrange(1000):
            for k in xrange(1000):
                if i*i + j*j == k*k:                    
                    if i + j + k == 1000:
                        return (i, j, k)

i, j, k = triplet()
print('result: %d^2 + %d^2 = %d^2' % (i, j, k))

Note that from here, there's a number of optimizations that you can make.

• Like that given an i and j, you only need to test one k, that is k == 1000 - i - j.
• Like that if you've tested i == 1 and j == 2, you don't need to test i == 2 and j == 1. They will have the same result.

Additionally, if you wanted to skip 0 in the loop, you could do xrange(1, 1000). xrange() allows you to pass a start and an end position.

Answer 4

Why not simply using a pythonic way to solve the problem:

[(a,b,c) for a,b,c in itertools.product(range(0,999), repeat=3) if (a**2 + b**2 == c**2) and (a + b + c == 1000)]

Answer 5

You have already been suggested how to refactor the code to avoid the need to break loops in the first place, and personally I would use a generator function solution of @pillmuncher (if still considering the use of loops at all).

Here is just an example of how you can break a loop without using a boolean flag:

i = 1
while i < 999:
    j = 1
    while j < 999:
        k = 1
        while k < 999:
            if i*i + j*j == k*k and i + j + k == 1000:
                ii, jj, kk = i, j, k
            else:
                k += 1
                continue
            break
        else:
            j += 1
            continue
        break
    else:
        i += 1
        continue
    break
print('result: %d^2 + %d^2 = %d^2' % (ii, jj, kk))

Or, using more neat for ... in range(...) (or better xrange in Python 2) loop:

for i in range(1, 999):
    for j in range(1, 999):
        for k in range(1, 999):
            if i*i + j*j == k*k and i + j + k == 1000:
                ii, jj, kk = i, j, k
            else:
                continue
            break
        else:
            continue
        break
    else:
        continue
    break
print('result: %d^2 + %d^2 = %d^2' % (ii, jj, kk))