## 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()
}
```