Avatar of mkatychev

mkatychev's solution

to Pythagorean Triplet in the Rust Track

Published at Jan 06 2020 · 0 comments
Instructions
Test suite
Solution

A Pythagorean triplet is a set of three natural numbers, {a, b, c}, for which,

a**2 + b**2 = c**2

and such that,

a < b < c

For example,

3**2 + 4**2 = 9 + 16 = 25 = 5**2.

Given an input integer N, find all Pythagorean triplets for which a + b + c = N.

For example, with N = 1000, there is exactly one Pythagorean triplet for which a + b + c = 1000: {200, 375, 425}.

Rust Installation

Refer to the exercism help page for Rust installation and learning resources.

Writing the Code

Execute the tests with:

$ cargo test

All but the first test have been ignored. After you get the first test to pass, open the tests source file which is located in the tests directory and remove the #[ignore] flag from the next test and get the tests to pass again. Each separate test is a function with #[test] flag above it. Continue, until you pass every test.

If you wish to run all ignored tests without editing the tests source file, use:

$ cargo test -- --ignored

To run a specific test, for example some_test, you can use:

$ cargo test some_test

If the specific test is ignored use:

$ cargo test some_test -- --ignored

To learn more about Rust tests refer to the online test documentation

Make sure to read the Modules chapter if you haven't already, it will help you with organizing your files.

Further improvements

After you have solved the exercise, please consider using the additional utilities, described in the installation guide, to further refine your final solution.

To format your solution, inside the solution directory use

cargo fmt

To see, if your solution contains some common ineffective use cases, inside the solution directory use

cargo clippy --all-targets

Submitting the solution

Generally you should submit all files in which you implemented your solution (src/lib.rs in most cases). If you are using any external crates, please consider submitting the Cargo.toml file. This will make the review process faster and clearer.

Feedback, Issues, Pull Requests

The exercism/rust repository on GitHub is the home for all of the Rust exercises. If you have feedback about an exercise, or want to help implement new exercises, head over there and create an issue. Members of the rust track team are happy to help!

If you want to know more about Exercism, take a look at the contribution guide.

Source

Problem 9 at Project Euler http://projecteuler.net/problem=9

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

pythagorean-triplet.rs

use pythagorean_triplet::find;
use std::{collections::HashSet, iter::FromIterator};

fn process_tripletswithsum_case(sum: u32, expected: &[[u32; 3]]) {
    let triplets = find(sum);

    if !expected.is_empty() {
        let expected = HashSet::from_iter(expected.iter().cloned());

        assert_eq!(expected, triplets);
    } else {
        assert!(triplets.is_empty());
    }
}

#[test]
fn test_triplets_whose_sum_is_12() {
    process_tripletswithsum_case(12, &[[3, 4, 5]]);
}

#[test]
#[ignore]
fn test_triplets_whose_sum_is_108() {
    process_tripletswithsum_case(108, &[[27, 36, 45]]);
}

#[test]
#[ignore]
fn test_triplets_whose_sum_is_1000() {
    process_tripletswithsum_case(1000, &[[200, 375, 425]]);
}

#[test]
#[ignore]
fn test_no_matching_triplets_for_1001() {
    process_tripletswithsum_case(1001, &[]);
}

#[test]
#[ignore]
fn test_returns_all_matching_triplets() {
    process_tripletswithsum_case(90, &[[9, 40, 41], [15, 36, 39]]);
}

#[test]
#[ignore]
fn test_several_matching_triplets() {
    process_tripletswithsum_case(
        840,
        &[
            [40, 399, 401],
            [56, 390, 394],
            [105, 360, 375],
            [120, 350, 370],
            [140, 336, 364],
            [168, 315, 357],
            [210, 280, 350],
            [240, 252, 348],
        ],
    );
}

#[test]
#[ignore]
fn test_triplets_for_large_number() {
    process_tripletswithsum_case(
        30_000,
        &[
            [1200, 14_375, 14_425],
            [1875, 14_000, 14_125],
            [5000, 12_000, 13_000],
            [6000, 11_250, 12_750],
            [7500, 10_000, 12_500],
        ],
    );
}

src/lib.rs

use crate::{matrix::*, ternary_tree::TernaryNode};
use std::collections::HashSet;

mod matrix;
mod ternary_tree;

pub fn find(sum: u32) -> HashSet<[u32; 3]> {
    let should_grow = |triplets: [u32; 3]| -> (Option<[u32; 3]>, bool) {
        let actual_sum: u32 = triplets.iter().sum();
        match actual_sum {
            actual if sum % actual == 0 => {
                let factor = sum / actual;
                // If the factor is greater than 1, then there are more possible solution
                // branches
                let keep_growing = if factor == 1 { false } else { true };
                // barning matrix multiplication has no expectation of being a sorted result
                let mut sorted = triplets.clone();
                sorted.sort();
                (
                    // multiply by found factor
                    Some([sorted[0] * factor, sorted[1] * factor, sorted[2] * factor]),
                    keep_growing,
                )
            },
            actual if actual > sum => (None, false),
            _ => (None, true),
        }
    };
    let mut root_node = TernaryNode::new(Matrix::new(3, 1, vec![3, 4, 5]).unwrap());

    // Barning matrices
    let a = Matrix::new(3, 3, BARNING_A.to_vec()).unwrap();
    let b = Matrix::new(3, 3, BARNING_B.to_vec()).unwrap();
    let c = Matrix::new(3, 3, BARNING_C.to_vec()).unwrap();
    let abc: [&Matrix; 3] = [&a, &b, &c];

    root_node.cond_grow(abc, &should_grow)
}

src/matrix.rs

use std::ops::Mul;

// https://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples
//     | 1-2 2 |
// A = | 2-1 2 |
//     | 2-2 3 |
pub static BARNING_A: &[i32] = &[1, -2, 2, 2, -1, 2, 2, -2, 3];

//     | 1 2 2 |
// B = | 2 1 2 |
//     | 2 2 3 |
pub static BARNING_B: &[i32] = &[1, 2, 2, 2, 1, 2, 2, 2, 3];

//     |-1 2 2 |
// C = |-2 1 2 |
//     |-2 2 3 |
pub static BARNING_C: &[i32] = &[-1, 2, 2, -2, 1, 2, -2, 2, 3];

#[derive(Debug, Clone, PartialEq)]
pub struct Matrix {
    pub rows: usize,
    pub cols: usize,
    pub data: Vec<i32>,
}
impl Matrix {
    pub fn new(rows: usize, cols: usize, data: Vec<i32>) -> Result<Self, &'static str> {
        let data_len = data.len();
        let matrix = Self { rows, cols, data };
        if (matrix.rows * matrix.cols) != data_len {
            return Err("No good long stuff")
        }
        Ok(matrix)
    }
}

impl Mul for Matrix {
    type Output = Self;

    #[allow(clippy::suspicious_arithmetic_impl)]
    fn mul(self, b_matrix: Self) -> Matrix {
        let a_matrix = self;
        if a_matrix.cols != b_matrix.rows {
            dbg!(a_matrix);
            dbg!(b_matrix);
            panic!(
                "Number of columns in the first matrix should equal to the number of rows in the \
                 second matrix!"
            )
        }
        let new_row = a_matrix.rows;
        let new_col = b_matrix.cols;
        let cell_iter = a_matrix.rows * b_matrix.cols;
        let mut new_data = Vec::with_capacity(cell_iter);
        for i in 0..cell_iter {
            let mut cell_val = 0;
            let a_start = a_matrix.cols * (i / b_matrix.cols);
            let a_stop = a_start + a_matrix.cols;
            let b_start = i % b_matrix.cols;
            for a in a_start..a_stop {
                let step_by = b_matrix.cols * (a % b_matrix.rows);
                let b = b_start + step_by;
                cell_val += (a_matrix.data[a] * b_matrix.data[b]) as i32;
            }
            new_data.push(cell_val);
        }

        Matrix {
            rows: new_row,
            cols: new_col,
            data: new_data,
        }
    }
}

// Multiplying two referenced Matrices should return an unreferenced matrix
impl<'a, 'b> Mul<&'b Matrix> for &'a Matrix {
    type Output = Matrix;

    fn mul(self, other: &'b Matrix) -> Matrix { self.clone() * other.clone() }
}

#[cfg(test)]
mod tests {

    use super::*;

    #[test]
    fn new_matrix() {
        assert_eq!(
            Matrix::new(6, 2, (0..12).collect()).unwrap(),
            Matrix {
                rows: 6,
                cols: 2,
                data: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].to_vec(),
            }
        );
    }
    #[test]
    fn ii_x_ii_matrix() {
        let a = Matrix::new(2, 3, (0..6).collect()).unwrap();
        let b = Matrix::new(3, 2, (0..6).collect()).unwrap();
        assert_eq!(
            a * b,
            Matrix {
                rows: 2,
                cols: 2,
                data: [10, 13, 28, 40].to_vec(),
            }
        );
    }
    #[test]
    fn ii_x_iii_matrix() {
        let a = Matrix::new(3, 2, vec![2, 4, 6, 4, 7, 3]).unwrap();
        let b = Matrix::new(2, 2, vec![2, 1, 8, 5]).unwrap();
        assert_eq!(
            &a * &b,
            Matrix {
                rows: 3,
                cols: 2,
                data: [36, 22, 44, 26, 38, 22].to_vec(),
            }
        );
        assert_eq!(
            a * b,
            Matrix {
                rows: 3,
                cols: 2,
                data: [36, 22, 44, 26, 38, 22].to_vec(),
            }
        );
    }
    #[test]
    fn iii_x_iv_matrix() {
        let a = Matrix::new(3, 2, vec![1, 3, 2, 4, 2, 5]).unwrap();
        let b = Matrix::new(2, 4, vec![1, 3, 2, 2, 2, 4, 5, 1]).unwrap();
        assert_eq!(
            a * b,
            Matrix {
                rows: 3,
                cols: 4,
                data: [7, 15, 17, 5, 10, 22, 24, 8, 12, 26, 29, 9].to_vec(),
            }
        );
    }
    #[test]
    fn iv_xx_iv_matrix() {
        let a = Matrix::new(4, 4, vec![5, 7, 9, 10, 2, 3, 3, 8, 8, 10, 2, 3, 3, 3, 4, 8]).unwrap();
        let b = Matrix::new(
            4,
            4,
            vec![3, 10, 12, 18, 12, 1, 4, 9, 9, 10, 12, 2, 3, 12, 4, 10],
        )
        .unwrap();
        assert_eq!(
            a * b,
            Matrix {
                rows: 4,
                cols: 4,
                data: vec![
                    210, 267, 236, 271, 93, 149, 104, 149, 171, 146, 172, 268, 105, 169, 128, 169
                ],
            }
        );
    }
}

src/ternary_tree.rs

use crate::matrix::Matrix;
use std::collections::HashSet;

type Leaf = Option<Box<TernaryNode>>;

#[derive(Debug, Clone, PartialEq)]
pub struct TernaryNode {
    val:    Matrix,
    left:   Leaf,
    middle: Leaf,
    right:  Leaf,
}

impl TernaryNode {
    pub fn new(matrix: Matrix) -> TernaryNode {
        Self {
            val:    matrix,
            left:   None,
            middle: None,
            right:  None,
        }
    }

    fn as_arr(&self) -> [u32; 3] {
        let data = self.val.data.clone();

        let c = data[2];
        let b = data[1];
        let a = data[0];

        [a as u32, b as u32, c as u32]
    }

    fn branch_out(self) -> Leaf { Some(Box::new(self)) }

    pub fn grow(&mut self, a_val: &Matrix, b_val: &Matrix, c_val: &Matrix) {
        self.left = Self::new(a_val * &self.val).branch_out();
        self.middle = Self::new(b_val * &self.val).branch_out();
        self.right = Self::new(c_val * &self.val).branch_out();
    }

    pub fn cond_grow<F>(&mut self, matrices: [&Matrix; 3], matcher: &F) -> HashSet<[u32; 3]>
    where F: Fn([u32; 3]) -> (Option<[u32; 3]>, bool) {
        let mut set: HashSet<[u32; 3]> = HashSet::new();
        let triplets: [u32; 3] = self.as_arr();
        let (matched_triplets, keep_growing) = matcher(triplets);
        matched_triplets.map(|val| set.insert(val));

        if !keep_growing {
            return set
        }

        // Grow all leaves using matrix multiplication
        self.grow(matrices[0], matrices[1], matrices[2]);

        let mut leaves: [&mut Leaf; 3] = [&mut self.left, &mut self.middle, &mut self.right];

        // traverse every leaf synchronously
        for leaf in leaves.iter_mut() {
            let leaf_matches = leaf.as_mut().unwrap().cond_grow(matrices, matcher);
            set.extend(leaf_matches);
        }
        set
    }
}

#[cfg(test)]
mod tests {

    use super::*;
    use crate::matrix::{BARNING_A, BARNING_B, BARNING_C};

    #[test]
    fn new_insert() {
        let matrix = Matrix::new(2, 2, vec![1, 2, 3, 4]).unwrap();
        let root_node = TernaryNode::new(matrix.clone());
        assert_eq!(
            root_node,
            TernaryNode {
                val:    matrix,
                left:   None,
                middle: None,
                right:  None,
            }
        );
    }
    #[test]
    fn grow_leaf() {
        let barning_matrix_a = Matrix::new(3, 3, BARNING_A.to_vec()).unwrap();
        let barning_matrix_b = Matrix::new(3, 3, BARNING_B.to_vec()).unwrap();
        let barning_matrix_c = Matrix::new(3, 3, BARNING_C.to_vec()).unwrap();
        let root_matrix = Matrix::new(3, 1, vec![3, 4, 5]).unwrap();
        let mut root_node = TernaryNode::new(root_matrix.clone());
        root_node.grow(&barning_matrix_a, &barning_matrix_b, &barning_matrix_c);
        assert_eq!(
            root_node,
            TernaryNode {
                val:    root_matrix.clone(),
                left:   TernaryNode::new(Matrix {
                    rows: 3,
                    cols: 1,
                    data: vec![5, 12, 13],
                },)
                .branch_out(),
                middle: TernaryNode::new(Matrix {
                    rows: 3,
                    cols: 1,
                    data: vec![21, 20, 29],
                },)
                .branch_out(),
                right:  TernaryNode::new(Matrix {
                    rows: 3,
                    cols: 1,
                    data: vec![15, 8, 17],
                },)
                .branch_out(),
            }
        );
    }
}

Community comments

Find this solution interesting? Ask the author a question to learn more.

mkatychev's Reflection

This was more of a learning exercise in implementing matrices and ternary nodes from scratch than a succinct solution.