## exercism.io rust track: Pythagorean Triplet

May 30, 2021 – 100 days to offload countdown #97

One of my on-and-off technical relationships is with exercism.io. A look on my profile there reveals that I have an interest in interesting languages and not a lot of stamina w/r to keeping up my exercises.

Today I had a few brain-cycles to spare and took a look at the rust
track: I stopped a couple of years ago checking out the *Pythagorean
Triplet* exercise, never tackling it. The original exercise was
Project Euler #9: Find a pythagorean triplet so that it’s sum equals
1000 (i.e. `a^2 + b^2 = c^2`

and `a + b + c = 1000`

) and return the
product `a*b*c`

. I read up on algorithms to compute pythagorean
triplets and found dicksons way the easiest to implement – I didn’t
want to use the straight nested loop solution that was offering itself
as easiest to implement.

The first step in implementing dicksons algorithm was a factorization function. I found an implementation in a crate that found all prime factors of a given number – I took it and modified it to find all pairs of factors.

I than calculated all triples for values of `r`, checking if the sum is 1000 and returning the product of the matching triple.

The test passed and I submited my solution only to find out that the
exercise was updated. The code must now find and return all triples
whose sum is an arbitray value – as a `HashSet`

. That got me
scrambling for a bit – adapting my solution would have been easy
enough, but I used a Vector of `u32`

3-tuples as data structure and had
to figure out how to use `HashSet`

. That took a bit but I figured it
out as far as I needed to solve the problem without upsetting the rust
compiler.

The final obstacle was the last test: Finding all triplets with the
sum 30000. The code would simply take too long – I never let it run
through, stopped it after a couple of minutes. I tried to use
memoization for `factorize`

, but the test never ran in acceptable time.
I realized that I can limit the values for the smaller factor of the
pairs found and finish `factorize`

early – this ran in acceptable time.
I tried to run the code without memoization and found out it had no
real impact – the solution would solve the problem without it.

This is not elegant code, and not correctly optimized w/r to the limits that cut the necessary computations short - but for about 2 hours of my time figuring out the algorithm and the syntax I’m quite content.

use std::collections::HashSet; use std::iter::FromIterator; fn factorize(n: u32, limit: u32) -> Vec<(u32, u32)> { let mut pfs: Vec<(u32, u32)> = Vec::new(); let mut d = 2; let mut q; while d <= n { while n % d != 0 { d += 1; } q = n / d; pfs.push(if d < q { (d, q) } else { (q,d) }); d += 1; if d>=limit { d = n + 1 } } pfs.sort(); pfs.dedup(); pfs } fn dickson(r: u32, limit: u32) -> HashSet<[u32; 3]> { let u : u32 = (r.pow(2))/2; HashSet::from_iter(factorize(u, limit).into_iter().map(|pair| [r+pair.0,r+pair.1,r+pair.0+pair.1])) } fn test_sum(r: u32, sum: u32) -> HashSet<[u32; 3]> { dickson(r, sum/3).into_iter().filter(|x| x[0]+x[1]+x[2] == sum).collect() } pub fn find(sum: u32) -> HashSet<[u32; 3]> { (2..(sum/2)+1).step_by(2).flat_map(|r| test_sum(r, sum)).collect() }