pythagorean-triplet: new tests require non-trivial solution

[omer-g]

I recently rewrote the Python version of this exercise based on canonical data 1.0.0.

I wanted to update that the trivial solution for finding triplets in a range by brute force takes a very long time on the latest tests (for example this). Almost all solutions I saw used this method and will not finish in reasonable time (if at all). I think it would be difficult for people to find an efficient solution by themselves. Perhaps a hint should be given?

The previous example.py would not handle these tests as well. The new example.py solves the tests quickly. It generates triplets in range efficiently by building triplets from multiples of primitive triplets.

Overall I think the new tests make the exercise more interesting. However, I think it would be difficult for people to come up with an efficient enough solution to pass them in reasonable time. I would be happy to hear what others think.

(related to #1211 )

[petertseng]

I notice that https://github.com/exercism/docs/blob/master/you-can-help/improve-exercise-metadata.md#extracting-canonical-test-data has a sentence "Performance tests should not be included in the canonical test data."

The above sentence must not be taken as support for or opposition against the statement "There exists a performance test in the current canonical test data"

I recommend that the decision for this issue be also applied in a similar way to alphametics for #1024 .

[cmccandless]

@omer-g from your testing, was the only problematic test triplets for a large number? If so, unless we can prove that case tests for something the others do not, it should probably be removed.

After reviewing #1024, the primary difference between the alphametics example and this one is that the time complexity for solving a case in alphametics is linear with the number of unique letters. With this exercise, the time complexity is polynomial, causing "large" cases to require significantly more time to solve, without really testing for anything that a smaller case can't test.

[omer-g]

I ran the other tests, without the last triplets_for_large_numbers, on a brute force solution and it finished in 71.58 seconds. With the final test it seems it will take much (much) longer.

[omer-g]

If the tests remain as they are, perhaps something like this could be added alongside an explanation for how to generate primitive triplets? I think there is a good explanation for that in the previous iterations of the Python version.

(feel free to reword/correct as needed)

Hint:

Finding all Pythagorean triplets in a certain range by checking all possible integer combinations is a computationally heavy process.

Pythagorean triplets are divided into two groups: primitive and imprimitive.

Primitive triplets have a g.c.d. of 1. Each imprimitive triplet is equal to a certain primitive triplet factored by a positive integer.

It is therefore possible to find all triplets in a certain range by first finding the primitive triplets and then using them to find the other imprimitive triplets in range.

*** HERE EXPLAIN HOW TO FIND PRIMITIVE TRIPLETS ***

Read more about this here.

[petertseng]

time complexity for solving a case in alphametics is linear with the number of unique letters

Personally I was thinking it was factorial, as the number of number <-> letter assignments is the number of permutations of letters. But since I'm always looking for ways to improve my solutions, if you let me know of the way to do it linearly then I'd be able to improve my solution greatly

[cmccandless]

@petertseng No, you're correct. Yikes, I am getting rusty at algorithmic analysis.

[cmccandless]

In which case, I'm not honestly sure where I stand on this issue.