Pascal's Triangle - Good / Needs Work? Exercism

josephleblanc · October 28, 2019, 6:39pm

Hello rusty rusters, I've got a small exercise that could use some more experienced eyes. Any and all suggestions welcome. Below I briefly describe the exercise, my solution, and specific questions.

My code is posted at the end (lib.rs) as well as the tests included from Exercism, which can be placed in the tests cargo project folder for usage with cargo test. Note that if you do this, be sure to run all tests with cargo test -- --ignored.

The Exercise
Create a function which takes a u32 parameter and returns a struct called PascalsTriangle. The struct must have two functions built in, each with predetermined parameters and return types:

pub struct PascalsTriangle {}

impl PascalsTraingle {
    pub fn new(row_count: u32) -> Self {
    }

    pub fn rows(&self) -> Vec<Vec<u32>> {
    }
}

My Solution
This code basically works by creating a new vector for each row, and populating that row by adding the two values in the previous row.

Questions

Is this the right way to go about using rust for this problem?
Are there useful things from the standard library I'm missing?
Any other rust-style things I should be replacing for loops with? I'm still having trouble knowing when to apply while let, if let, match, and using iterators rather than for loops.

Anything else you think might improve this code is totally welcome. Thanks for looking!

src/lib.rs

pub struct PascalsTriangle {
    row_count: u32,
    triangle: Vec<Vec<u32>>,
}

impl PascalsTriangle {
    pub fn new(row_count: u32) -> Self {
        let mut triangle: Vec<Vec<u32>> = vec![];
        let mut new_triangle = PascalsTriangle { 
            row_count, 
            triangle, 
        };
        
        triangle = new_triangle.rows();
        new_triangle.triangle = triangle;
        new_triangle
    }

    // Create Pascals Triangle vector of vectors
    // First make containing vector, then populate first two rows as edge cases.
    // For remaining rows, create a new vector for each row, use members of previous
    // row to make members of new row.
    pub fn rows(&self) -> Vec<Vec<u32>> {
        let mut triangle: Vec<Vec<u32>> = 
            Vec::with_capacity(self.row_count as usize);

        if self.row_count == 0 { 
            return triangle
        } else if self.row_count >= 1 {
            let apex: Vec<u32> = vec![1];
            triangle.push(apex);
        }
        if self.row_count >= 2 {
            let second_row: Vec<u32> = vec![1, 1];
            triangle.push(second_row);
        }
        if self.row_count > 2 {
            for index in 2..(self.row_count as usize) {
                let mut row: Vec<u32> = Vec::with_capacity(index + 1);
                row.push(1);
                for last_index in 0..=((triangle[index - 1].len() - 2) as usize) {
                    row.push(triangle[index - 1][last_index] 
                             + triangle[index - 1][last_index+1]);
                }
                row.push(1);
                triangle.push(row);
            }
        }
        triangle
    }
}

tests/pascals-triangle.rs

use pascals_triangle::*;

#[test]
fn no_rows() {
    let pt = PascalsTriangle::new(0);
    let expected: Vec<Vec<u32>> = Vec::new();
    assert_eq!(expected, pt.rows());
}

#[test]
#[ignore]
fn one_row() {
    let pt = PascalsTriangle::new(1);
    let expected: Vec<Vec<u32>> = vec![vec![1]];
    assert_eq!(expected, pt.rows());
}

#[test]
#[ignore]
fn two_rows() {
    let pt = PascalsTriangle::new(2);
    let expected: Vec<Vec<u32>> = vec![vec![1], vec![1, 1]];
    assert_eq!(expected, pt.rows());
}

#[test]
#[ignore]
fn three_rows() {
    let pt = PascalsTriangle::new(3);
    let expected: Vec<Vec<u32>> = vec![vec![1], vec![1, 1], vec![1, 2, 1]];
    assert_eq!(expected, pt.rows());
}

#[test]
#[ignore]
fn last_of_four_rows() {
    let pt = PascalsTriangle::new(4);
    let expected: Vec<u32> = vec![1, 3, 3, 1];
    assert_eq!(Some(expected), pt.rows().pop());
}

#[test]
#[ignore]
fn five_rows() {
    let pt = PascalsTriangle::new(5);
    let expected: Vec<Vec<u32>> = vec![
        vec![1],
        vec![1, 1],
        vec![1, 2, 1],
        vec![1, 3, 3, 1],
        vec![1, 4, 6, 4, 1],
    ];
    assert_eq!(expected, pt.rows());
}

#[test]
#[ignore]
fn six_rows() {
    let pt = PascalsTriangle::new(6);
    let expected: Vec<Vec<u32>> = vec![
        vec![1],
        vec![1, 1],
        vec![1, 2, 1],
        vec![1, 3, 3, 1],
        vec![1, 4, 6, 4, 1],
        vec![1, 5, 10, 10, 5, 1],
    ];
    assert_eq!(expected, pt.rows());
}

#[test]
#[ignore]
fn seven_rows() {
    let pt = PascalsTriangle::new(7);
    let expected: Vec<Vec<u32>> = vec![
        vec![1],
        vec![1, 1],
        vec![1, 2, 1],
        vec![1, 3, 3, 1],
        vec![1, 4, 6, 4, 1],
        vec![1, 5, 10, 10, 5, 1],
        vec![1, 6, 15, 20, 15, 6, 1],
    ];
    assert_eq!(expected, pt.rows());
}

#[test]
#[ignore]
fn ten_rows() {
    let pt = PascalsTriangle::new(10);
    let expected: Vec<Vec<u32>> = vec![
        vec![1],
        vec![1, 1],
        vec![1, 2, 1],
        vec![1, 3, 3, 1],
        vec![1, 4, 6, 4, 1],
        vec![1, 5, 10, 10, 5, 1],
        vec![1, 6, 15, 20, 15, 6, 1],
        vec![1, 7, 21, 35, 35, 21, 7, 1],
        vec![1, 8, 28, 56, 70, 56, 28, 8, 1],
        vec![1, 9, 36, 84, 126, 126, 84, 36, 9, 1],
    ];
    assert_eq!(expected, pt.rows());
}

stevensonmt · October 28, 2019, 7:14pm

Nothing wrong with your solution, but you might consider a couple of things:

You don't need to store both the number of rows AND the collection of rows. Pick one or the other to store. The most intuitive choice (at least to me) is to store the collection of rows. If you ever need the number of rows, just call len() on the collection. That said, for this exercise you aren't manipulating the rows after you build them into the collection, so the most efficient thing is to just store the number of rows and only build the collection when you call rows().
HINT: struct PascalsTriangle(u32);
This is a good exercise for thinking about recursion.
HINT:

fn rows(&self) -> Vec<Vec<u32>> {
    match self.0 { //or self.row_count with your current struct def
        0 => vec![],
        _ => build_row(vec![], self.0 - 1) // or self.row_count - 1
    }
}

fn build_row(triangle: Vec<Vec<u32>>, row_count: u32) -> Vec<Vec<u32>> {
    // do stuff that pushes new row to triangle (either using 
    // mut triangle or building a new_triangle) 
    // and that decrements row_count by one (again by either using 
    // mut row_count or declaring a new_row_count)
    ...
    if new_row_count > 0 {
        build_row(new_triangle, new_row_count)
    } else { 
        return new_triangle 
    }
}

alice · October 28, 2019, 7:14pm

The loop can be written as:

let prev_row = &triangle[index-1];
for (left, right) in prev_row.iter().zip(prev_row.iter().skip(1)) {
    row.push(*left + *right);
}

josephleblanc · October 28, 2019, 9:46pm

OK made changes with setvensonmt and alice's advice, now it uses a recursive helper function, PascalsTriangle only has a u32, and loop written with zip. Code below.

Any other suggestions?

pub struct PascalsTriangle {
    row_count: u32,
}

impl PascalsTriangle {
    pub fn new(row_count: u32) -> Self {
        let new_triangle = PascalsTriangle {
            row_count,
        };

        new_triangle
    }

    // Deal with edge cases, call recursive function to contruct triangle
    pub fn rows(&self) -> Vec<Vec<u32>> {
        match self.row_count {
            0 => vec![],
            1 => vec![vec![1]],
            _ => build_row(vec![vec![1]], self.row_count - 1),
        }
    }

}

// Recursive function to contruct pascal triangle
fn build_row(mut triangle: Vec<Vec<u32>>, row_count: u32) -> Vec<Vec<u32>> {
    let mut new_row: Vec<u32> = vec![];

    // Do stuff to construct new row
    new_row.push(1);
    let prev_row = &triangle.last().unwrap(); // Cannot panic, b/c no 0 len vec
    for (left, right) in prev_row.iter().zip(prev_row.iter().skip(1)) {
        new_row.push(*left + *right);
    }
    new_row.push(1);

    // Add new row to triangle
    triangle.push(new_row);

    // Recurse if needed, otherwise return
    if row_count - 1 > 0 {
        build_row(triangle, row_count - 1)
    } else {
        return triangle
    }
}

alice · October 28, 2019, 9:51pm

I'm not sure I agree that it's a nice place to use recursion.

josephleblanc · October 28, 2019, 9:52pm

What are the pros and cons of recursion here?

stevensonmt · October 28, 2019, 10:13pm

I suspect you are a more experienced/educated coder than I am, so I would probably defer to your opinion, but I'm curious why you think it is not a good candidate for a recursive solution. The process of adding a row is doing the same calculation based on the previous row until you reach a maximum number of rows. That sounds like a recursive problem to me.

alice · October 28, 2019, 10:58pm

I think this specific form of recursion is less awkward to write as a loop. It's just a tail call and it reminds me of coding in Haskell. In particular I don't like the row_count parameter, because it is a symptom of doing recursion "upside down" to what I find natural.

If I were to factor out the code for computing the triangle in a separate function, I might do something like this.

That said you can apply an alternate strategy to the problem and get something that is much more naturally recursive, because it calls itself twice, namely recursion with memoization. See playground for example.

system · January 26, 2020, 10:58pm

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.

Topic		Replies	Views
Rust in Exercism community	9	2347	March 19, 2020
Implementing simple linked-list @ exercism help	5	729	January 12, 2023
Feedback wanted: Countdown solver code review	8	656	September 5, 2022
Rasteroid code review code review	13	597	January 23, 2023
First Exercises in Rust; feedback appreciated! code review	2	74	January 15, 2025

Pascal's Triangle - Good / Needs Work? Exercism

Related topics