def triplets_with_sum(n):

triplets = []

for a in range(1, n + 1):

for b in range(a + 1, n + 1):

for c in range(b + 1, n + 1):

if a**2 + b**2 == c**2 and a + b + c == n:

triplets.append([a, b, c])

return triplets

The strategy in this case is to scan through all three variables and test them in the innermost loop.

But the innermost loop will test all variables _every time_ the enclosing loop iterates.

And the enclosing loop up will iterate through all of its range _every time_ the outermost loop iterates.

So the 'work' this code has to do for each additional value in `range(1, n+1)` is `n**3`.

This gives code that is simple, clear, ...and so slow as to be useless for all but the smallest values of `n`.

We could tighten up the bounds on loop variables: for example, `a` is the smallest integer of a triplet that sums to `n`, so inevitably `a < n //3`.

However, this is not nearly enough to rescue an inappropriate algorithm.

def triplets_with_sum(n):

triplets = []

for a in range(1, n + 1):

for b in range(a + 1, n + 1):

for c in range(b + 1, n + 1):

if a**2 + b**2 == c**2 and a + b + c == n:

triplets.append([a, b, c])

return triplets

The main challenge in solving the Pythagorean Triplet exercise is to come up with a 'fast enough' algorithm.

The problem space can easily become very large, and 'naive' or more 'brute force' solutions may time out on the test runner.

There are three reasonably common variations to this problem

1. A [cubic time][approaches-cubic] solution, which uses highly nested loops and is non-performant.

2. A [quadratic time][approaches-quadratic] solution, which uses one nested loop, and is reasonably easy to figure out.

3. A [linear time][approaches-linear] solution, requiring some deeper understanding of the mathematics of finding trplets.

If those terms are unclear to you, you might like to read about [time complexity][time-complexity], and how it is described by [asymptotic notation][asymptotic-notation].

The basic idea is to study how algorithms scale (_in CPU/GPU run time, memory usage, or other resource_) as the input parameters grow toward infinity.

In this document we will focus on run time, which is critical for this exercise.

The goal of `Pythagorean Triplets` is to find combinations of three numbers `[a, b, c]` satisfying a set of conditions:

1. `a < b < c`

2. `a**2 + b**2 == c**2` (_otherwise known as the [Pythagorean theorem][Pythagorean-theorem]_)

3. `a + b + c == n`, where `n` is supplied as a parameter to the function.

For a given `n`, the solution should include all valid triplets as a list of lists.

def triplets_with_sum(n):

triplets = []

for a in range(1, n + 1):

for b in range(a + 1, n + 1):

for c in range(b + 1, n + 1):

if a**2 + b**2 == c**2 and a + b + c == n:

triplets.append([a, b, c])

return triplets

This is the most 'naive' or 'brute force' approach, scanning through all possible integers `<= n` that satisfy `a < b < c`.

This might be the first thing you think of when sketching out the algorithm on paper following the exercise instructions.

It is useful to see the steps of the solution and to look at the size of the problem space.

***Don't implement this in code!***

While it is a valid solution and it indeed works for small values of `n`, it becomes impossibly slow as `n` grows larger.

For any truly large values of `n`, this code might take over all the available processing power on your local computer and never complete.

For Exercism's online environment, the test suite will time out and fail.

def triplets_with_sum(n):

triplets = []

for a in range(1, n + 1):

for b in range(a + 1, n + 1):

c = n - a - b

if a ** 2 + b ** 2 == c ** 2:

triplets.append([a, b, c])

return triplets

Given the constraint that `a + b + c == n`, we can eliminate the innermost loop from the cubic approach and calculate `c` directly.

This gives a substantial speed advantage, allowing the tests to run to completion in a reasonable time, _locally_.

However, the Exercism online test runner will still time out with this solution.

Examining the code, it is clear that the upper bounds on the `loop` variables are far too generous, and too much work is bing done.

The solution below tightens the bounds and pre-calculates `c * c` in the outer `loop`.

This gives about a 4-fold speedup, but still times out on the online test runner:

def triplets_with_sum(n):

result = []

for c in range(5, n - 1):

c_sq = c * c

for a in range(3, (n - c + 1) // 2):

b = n - a - c

if a < b < c and a * a + b * b == c_sq:

result.append([a, b, c])

return result

If a quadratic-time algorithm was the best available option, there are other ways to squeeze out small performance gains.

For bigger problems outside Exercism, there are third-party packages such as [`numpy`][numpy] or [`numba`][numba] which replace Python

loops (_versatile but relatively slow_) with routines written in C/C++, perhaps with use of the GPU.

The runtime is still proportional to `n**2`, but the proportionality constant (_which would be measured in C/C++ as opposed to Python_) may be much smaller.

Fortunately for the present discussion, mathematicians have been studying Pythagorean Triplets for centuries: see [Wikipedia][wiki-pythag], [Wolfram MathWorld][wolfram-pythag], or many other sources.

So mathematically there are much faster algorithms, at the expense of reduced readability.

from math import sqrt

def triplets_with_sum(n):

N = float(n)

triplets = []

for c in range(int(N / 2) - 1, int((sqrt(2) - 1) * N), -1):

D = sqrt(c ** 2 - N ** 2 + 2 * N * c)

if D == int(D):

triplets.append([int((N - c - D) / 2), int((N - c + D) / 2), c])

return triplets

_All clear?_ 😉

After some thoughtful mathematical analysis, there is now only a single loop!

Run time is now much faster, especially for large `n`, but a reasonable person could find it quite difficult to understand what the code is doing.

If you do things like this out in the 'real world' ***please*** document your code carefully.

It might also be helpful to choose variable names that are more descriptive to help readers understand all of the values and operations.

In a few weeks, the bare code will puzzle your future self.

People reading it for the first time are likely to struggle even more than you will.

The code above uses fairly 'generic' programming syntax.

Another submission used the same basic algorithm but in a more 'Pythonic' way:

def triplets_with_sum(n):

def calculate_medium(small):

return (n ** 2 - 2 * n * small) / (2 * (n - small))

two_sides = ((int(medium), small) for small in range(3, n // 3)

if small < (medium := calculate_medium(small))

and medium.is_integer())

return [[small, medium, (medium ** 2 + small ** 2) ** 0.5]

for medium, small in two_sides]

Although it is important to note that this solution could have chosen a better name for the `n` parameter, and clearer formatting for the `generator-expression` and the `list-comprehension`:

def triplets_with_sum(number):

def calculate_medium(small):

# We have two numbers, but need the third.

return (number ** 2 - 2 * number * small) / (2 * (number - small))

two_sides = (

(int(medium), small) for

small in range(3, number // 3) if

#Calls calculate_medium and assigns return value to variable medium

small < (medium := calculate_medium(small)) and

medium.is_integer()

)

return [

[small, medium, (medium ** 2 + small ** 2) ** 0.5]

for medium, small in two_sides

]

If we could be sure that the code only had to handle small values of `n`, a quadratic method would have the advantage of clarity.

However, the test suite goes up to 30_000, and the online test runner quickly times out.

We therefor need to accept some less readable code and use a linear-time implementation.

Full details of run-time benchmarking are given in the [Performance article][article-performance].

Overall, the results confirm the expectation that the linear-time methods are _very much_ faster.

More surprisingly, the first example of the linear implementation (_with an explicit loop_) proved slightly faster than the more 'Pythonic' code.

This is likely due to the overhead of creating and tracking the iterator for the `generator-expression`, calculating the 'expensive' `calculate_medium()` function call within that generator, and the additional 'expensive' conversions to `int()`.

[Pythagorean-theorem]: https://en.wikipedia.org/wiki/Pythagorean_theorem

[approaches-cubic]: https://exercism.org/tracks/python/exercises/pythagorean-triplet/approaches/cubic

[approaches-linear]: https://exercism.org/tracks/python/exercises/pythagorean-triplet/approaches/linear

[approaches-quadratic]: https://exercism.org/tracks/python/exercises/pythagorean-triplet/approaches/quadratic

[article-performance]:https://exercism.org/tracks/python/exercises/pythagorean-triplet/articles/performance

[asymptotic-notation]: https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation

[numba]: https://numba.pydata.org/

[numpy]: https://numpy.org/

[time-complexity]: https://yourbasic.org/algorithms/time-complexity-explained/

[wiki-pythag]: https://en.wikipedia.org/wiki/Pythagorean_triple

[wolfram-pythag]: https://mathworld.wolfram.com/PythagoreanTriple.html

The key point with this approach is that we only loop over the variable `c` in a specific range.

Some mathematical analysis (_essentially, [solving simultaneous equations][simultaneous-equasions]_) then allows us to find valid values of `a` and `b`.

Other than that, the code syntax below is fairly mainstream across programming languages.

A related approach instead loops over `a`.

from math import sqrt

def triplets_with_sum(n):

N = float(n)

triplets = []

for c in range(int(N / 2) - 1, int((sqrt(2) - 1) * N), -1):

D = sqrt(c ** 2 - N ** 2 + 2 * N * c)

if D == int(D):

triplets.append([int((N - c - D) / 2), int((N - c + D) / 2), c])

return triplets

This second code example has no explicit `for` loop (_in Python syntax_), but the `generator-expression` and the `list-comprehension` both translate to `FOR_ITER` at the bytecode level.

So this solution is essentially the same as the first, written in a more 'Pythonic' syntax -- but that syntax does incur a small overhead in performance.

The performance hit is likely due to the extra instructions in the bytecode used to manage the `generator-expression` (_pausing the loop, resuming the loop, yielding results_) and then calling or unpacking the generator in the `list comprehension`.

However, you would have to carefully profile the code to really determine the slowdown.

With all that said, using a `generator` or `generator-expression` with or without a `list-comprehension` might be a better strategy if your code needs to process a very large number of triplets, as it avoids storing all the results in memory until they need to be returned.

Using a `generator` or `generator-expression` by itself can also nicely set up a scenario where results are "streamed" or emitted 'on demand' for another part of the program or application.

For more details on what these two solutions look like at the byte code level, take a look at Pythons [`dis`][dis] module.

def triplets_with_sum(n):

def calculate_medium(small):

return (n ** 2 - 2 * n * small) / (2 * (n - small))

two_sides = ((int(medium), small) for small in range(3, n // 3)

if small < (medium := calculate_medium(small))

and medium.is_integer())

return [[small, medium, (medium ** 2 + small ** 2) ** 0.5]

for medium, small in two_sides]

Some implementation details to notice:

- Nested functions, with the inner function able to reference variables such as `n` passed into the outer function.

- The generator expression creates `two_sides` as a lazily-evaluated iterator (_smaller memory footprint_)

- The [`walrus operator`][walrus-operator] `:=` is new in Python 3.8.

- The `is_integer()` method replaces `if D == int(D)`.

- Using `** 0.5` to calculate the square roots avoids a `math` import.

[dis]: https://docs.python.org/3/library/dis.html

[simultaneous-equasions]: https://thirdspacelearning.com/gcse-maths/algebra/simultaneous-equations/

[walrus-operator]: https://mathspp.com/blog/pydonts/assignment-expressions-and-the-walrus-operator

def triplets_with_sum(n):

def calculate_medium(small):

return (n ** 2 - 2 * n * small) / (2 * (n - small))

two_sides = ((int(medium), small) for small in range(3, n // 3)

if small < (medium := calculate_medium(small))

and medium.is_integer())

return [[small, medium, (medium ** 2 + small ** 2) ** 0.5]

for medium, small in two_sides]

def triplets_with_sum(n):

triplets = []

for a in range(1, n + 1):

for b in range(a + 1, n + 1):

c = n - a - b

if a ** 2 + b ** 2 == c ** 2:

triplets.append([a, b, c])

return triplets

Because `a + b + c == n`, we only loop over `a` and `b`.

The third variable `c` is then predictable.

The above code loops over the full range of both variables.

This means the 'work' this code has to do for each additional value in `range(1, n+1)` is `n**2`.

We know enough about the problems to tighten this up a bit.

For example:

- The smallest pythagorean is (famously) `[3, 4, 5]`, so `a >= 3`

- `a + b == n - c` and `a <= b`, so `a <= (n - c) // 2`

We can also avoid, to some extent, repeating the same multiplication many times.

This gets us to the code below:

def triplets_with_sum(n):

result = []

for c in range(5, n - 1):

c_sq = c * c

for a in range(3, (n - c + 1) // 2):

b = n - a - c

if a < b < c and a * a + b * b == c_sq:

result.append([a, b, c])

return result

We could have done a bit better.

Though not stated in the problem description, `a + b > c`, otherwise they could not form a triangle.

This means that `c <= n // 2`, reducing the iterations in the outer loop.

However, these optimizations only reduce the run time by a small factor.

They do almost nothing to make the algorithm scale to large `n`.

def triplets_with_sum(n):

triplets = []

for a in range(1, n + 1):

for b in range(a + 1, n + 1):

c = n - a - b

if a ** 2 + b ** 2 == c ** 2:

triplets.append([a, b, c])

return triplets