exercism · BethanyG · Jan 20, 2024 · Jan 3, 2024 · Jan 4, 2024 · Jan 4, 2024
diff --git a/exercises/practice/pythagorean-triplet/.approaches/config.json b/exercises/practice/pythagorean-triplet/.approaches/config.json
@@ -0,0 +1,33 @@
+{
+  "introduction": {
+    "authors": ["colinleach",
+                "BethanyG"],
+    "contributors": []
+  },
+  "approaches": [
+    {
+      "uuid": "4d4b4e6c-a026-4ed3-8e07-6b9edfabe713",
+      "slug": "cubic",
+      "title": "Cubic",
+      "blurb": "Cubic-time approach with loops nested 3 deep.",
+      "authors": ["colinleach",
+                  "BethanyG"]
+    },
+    {
+      "uuid": "385c0ace-117f-4480-8dfc-0632d8893e60",
+      "slug": "quadratic",
+      "title": "Quadratic",
+      "blurb": "Quadratic-time approaches with doubly-nested loops.",
+      "authors": ["colinleach",
+                  "BethanyG"]
+    },
+    {
+      "uuid": "1addb672-6064-4a07-acad-4a08f92d9e43",
+      "slug": "linear",
+      "title": "Linear Loop",
+      "blurb": "Linear-time approaches with no nesting of loops.",
+      "authors": ["colinleach",
+                  "BethanyG"]
+    }
+  ]
+}
diff --git a/exercises/practice/pythagorean-triplet/.approaches/cubic/content.md b/exercises/practice/pythagorean-triplet/.approaches/cubic/content.md
@@ -0,0 +1,24 @@
+# Cubic-time triply-nested loops
+
+```python
+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.
diff --git a/exercises/practice/pythagorean-triplet/.approaches/cubic/snippet.txt b/exercises/practice/pythagorean-triplet/.approaches/cubic/snippet.txt
@@ -0,0 +1,8 @@
+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
diff --git a/exercises/practice/pythagorean-triplet/.approaches/introduction.md b/exercises/practice/pythagorean-triplet/.approaches/introduction.md
@@ -0,0 +1,192 @@
+# Introduction
+
+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.
+
+
+## General guidance
+
+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.
+
+
+## Approach: Cubic time solution with 3-deep nested loops
+
+```python
+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.
+
+
+## Approach: Quadratic time solution with 2-deep nested loops
+
+```python
+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:
+
+
+```python
+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.
+
+
+## Linear time solutions
+
+```python
+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:
+
+
+```python
+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`:
+
+```python
+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
+            ]
+```
+
+
+## Which approach to use?
+
+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
diff --git a/exercises/practice/pythagorean-triplet/.approaches/linear/content.md b/exercises/practice/pythagorean-triplet/.approaches/linear/content.md
@@ -0,0 +1,59 @@
+# Linear-time algorithms with no nested loops
+
+
+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`.
+
+```python
+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.
+
+
+```python
+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
diff --git a/exercises/practice/pythagorean-triplet/.approaches/linear/snippet.txt b/exercises/practice/pythagorean-triplet/.approaches/linear/snippet.txt
@@ -0,0 +1,8 @@
+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]
diff --git a/exercises/practice/pythagorean-triplet/.approaches/quadratic/content.md b/exercises/practice/pythagorean-triplet/.approaches/quadratic/content.md
@@ -0,0 +1,47 @@
+# Quadratic-time doubly-nested loops
+
+```python
+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:
+
+
+```python
+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`.
diff --git a/exercises/practice/pythagorean-triplet/.approaches/quadratic/snippet.txt b/exercises/practice/pythagorean-triplet/.approaches/quadratic/snippet.txt
@@ -0,0 +1,8 @@
+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