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