Exercism's "Pythagorean triplets with given perimeter" problem

Show & Tell
1

I went down a rabbit hole coming up with a good algorithm to solve this Exercism Racket problem but in the end, their system doesn't let you (require math). But my algorithm is much faster than brute-force search, and I think is also pretty good Racket code. I don't want to let all my work go to waste, so here's my code:

I am interested in comments on my code and style.

And in particular, I have this question about #:do and #:when and such in for/list: if I have something like

(for/list ([x some-list]
           #:when (pred1? x)
           #:do [(define y (some-func x))]
           #:when (pred2? y)
           #:do [(define z (another-func x y))])
  z)

Do those "short-circuit"? That is, if pred1? fails, does that guarantee that the following dos and when not run?

The idea, of course, is that perhaps another-func is expensive; or, if pred1 fails very very often -- in either of those cases, we want to skip the loop iteration as soon as possible. Does for/list do that?

2 Likes
2

You have the right idea, they do short-circuit. In particular, according to the docs:

If any for-clause has the form #:when guard-expr, then only the preceding clauses (containing no #:when, #:unless, or #:do) determine iteration as above, and the body is effectively wrapped as

(when guard-expr
  (for (for-clause ...) body ...+))

using the remaining for-clauses. A for-clause of the form #:unless guard-expr corresponds to the same transformation with unless in place of when. A for-clause of the form #:do [do-body ...] similarly creates nesting and corresponds to

(let ()
  do-body ...
  (for (for-clause ...) body ...+))
2 Likes
3

@ddrake

You probably already know Project Euler - but just in case you missed it - it has a lot of similar exercises / challenges.

2 Likes
4

I think the code for your main function triplets-with-sum deserves some stylistic commentary.

  • list-of-positive-integer-triplets?: I would prefer using listof.
  • I would prefer to see the result of the for/fold saved in a variable and then apply sort. Or use a threading macro. Right now the #:key comes long after the sort, which I find hard to follow.
  • When you append, the last list doesn't need to be copied. This means it is better to put the accumulator triples last, because it is the longest.
  • The special case for odd perimeter triples occurs at least twice in your code. This is just aesthetic, but it seems ugly to me.
5

I do know Project Euler! And I'm avoiding it because I'm too likely to get caught going down rabbit holes trying to optimize things that I already solved. :slight_smile:

6

Those are excellent comments! Thank you.

  • I didn't know about listof and yes, that's obviously the correct way to write the contract.
  • yeah, that big for/fold stuffed in the middle of the sort was hard to read. Factored into a let.
  • Good point about append. I swapped those.

For the odd? check: there are two because I have two top-level functions that compute the triplets; the first does the brute-force search and the second uses some number theory to be much more sophisticated and fast.

There's a third odd?, but that's also necessary: the number-theoretic algorithm, as it tries to generate primitive Pythagorean triples, needs to verify that exactly one of m and n are odd`. That's downstream of checking to see if the overall perimeter is even, so we need that too.

I updated my gist. Thanks again!

7

In your code, you mention a conjecture you have regarding the uniqueness of each primitive triple for a given perimeter.

This might well be. Obviously, not a mathematician, but according to the Wikipedia link on constructing trees of primitive triples, the introductory paragraph states:

A tree of primitive Pythagorean triples is a mathematical tree in which each node represents a primitive Pythagorean triple and each primitive Pythagorean triple is represented by exactly one node. In two of these trees, Berggren's tree and Price's tree, the root of the tree is the triple (3, 4, 5), and each node has exactly three children, generated from it by linear transformations.

Furthermore,

The set of all primitive Pythagorean triples has the structure of a rooted tree, specifically a ternary tree, in a natural way.

This doesn't address the uniqueness of sums of triples, but sucking my thumb a bit on the section regarding generating the tree with two parameters:

a = m^2 - n^2
b = 2mn
c = m^2 + n^2

with m > n > 0 and m and n coprime and of opposite parity

we see that a + b + c = 2m^2 + 2mn, and given that each m,n appears exactly once (if I am reading correctly), there are no cases where a duplicate sum would occur, since m ≠ n.

8

Just as a note, I don't quite think that's right -- the overall perimeter is indeed 2m(m+n); the question is: is it possible to have two distinct pairs (m, n) and (m', n') that meet the inequality and coprimality requirements, and also give the same perimeter?

It's not clear that it's impossible, but I don't have a proof.

9

For sure, a very jazz-handsy argument. My number theory never was very strong :sweat_smile:

I guess, if you assume there exists some (u,v) ≠ (m,n) such that 2u(u + v) = 2m(m + n), you could rearrange it into

      u(u + v) = m(m + n)
     u^2 - m^2 = mn - uv
(u + m)(u - m) = mn - uv.

Then you would have to show that u + m is a factor of the RHS (assuming it is equivalent to show that either factor on the left divides the difference on the right).

It's not clear to me how you would do this, but I agree that there's nothing about it that seems obviously contradictory.

Geometrically, we're asking if we can shorten one of the sides of each of the two squares:

image
image241×243 179 Bytes

while keeping the purple area constant, with the restriction that the lengths of the shortened sides be coprime to their former lengths. Although this doesn't really constrain the problem enough, given the recurrent relationship in the "tree" of triples.

But yeah, I'm just talking nonsense at this point.

1 Like
10

from Wikipedia , there is seems to be a uniqueness proof of triplets giving 3,2 or 1 parameter (see Presence of every primitive Pythagorean triple exactly once in wikipedia) but the 1 parameter is from a half-angle tangent. (see wikipedia) and is not really developped enought to understand (at least for me) .
For a parameter being the perimeter i have no idea.

Interesting program and math indeed i will try to code a bit about this....