Project Euler Problem 11 in Rust: largest product of consecutive elements of 20x20 grid

Question

Here is my solution to problem 11 on Project Euler. The goal was to find the largest product of any four numbers in consecutive line of any direction (vertical, horizontal, or diagonal). While my code achieved the solution it feels wrong to me in a way I cannot quite articulate. I attempted to implement a pseudo-matrix struct as a vec of vec after finding the docs for existing crates dealing with matrices somewhat difficult to grasp. With the current code I feel like I am looping too many times. For a 20x20 grid this is not an issue, but for a large grid, this would be a real issue. Suggestions for improving the efficiency of my code?

Link to the rust playground

struct Matrix {
    size: (usize, usize),
    rows: Vec<Vec<u32>>,
    cols: Vec<Vec<u32>>
}


fn new_matrix(row_size: usize, col_size: usize) -> Matrix {
    Matrix { size: (row_size, col_size), rows: Vec::with_capacity(row_size), cols: Vec::with_capacity(col_size) }
}


impl Matrix {
    fn cols_from_rows(&self) -> Vec<Vec<u32>> {
         let mut cols = vec![];
         for i in 0..(self.rows.len()) {
            let mut col = vec![];
            for j in 0..(self.rows[i].len()) {
                let item = *self.rows[j].iter().nth(i).unwrap();
                col.push(item);
             }
            cols.push(col);
         }
         cols
    }

    fn rows_from_cols(&self) -> Vec<Vec<u32>> {
        let mut rows = vec![];
        for i in 0..(self.cols.len()) {
            let mut row = vec![];
            for j in 0..(self.cols[i].len()) {
                let item = *self.cols[i].iter().nth(j).unwrap();
                row.push(item);
            }
            rows.push(row);
        }
        rows
    }

    fn matrix_row(&self, ndx: usize) -> Vec<u32> {
        let ref row = self.rows[ndx];
        row.to_vec()
    }

    fn matrix_column(&self, ndx: usize) -> Vec<u32> {
        let ref col = self.cols[ndx];
        col.to_vec()
    }

    fn matrix_diag_pos(&self, start_row: usize, start_col: usize, row_stride: usize, col_stride: usize) -> Vec<u32> {
        let mut diag = vec![];
        let mut cur_row = start_row;
        let mut cur_col = start_col;
        while cur_row < self.rows.len() && cur_col < self.cols.len() {
            diag.push(self.rows[cur_row][cur_col]);
            cur_row += row_stride;
            cur_col += col_stride;
        }
        diag
    }

    fn matrix_diag_neg(&self, start_row: usize, start_col: usize, row_stride: usize, col_stride: usize) -> Vec<u32> {
        let mut diag = vec![];
        let mut cur_row = start_row;
        let mut cur_col = start_col;
        while cur_col < self.cols.len() {
            diag.push(self.rows[cur_row][cur_col]);
            if cur_row != 0 { cur_row -= row_stride; } else { break }
            cur_col += col_stride; 
        }
        diag
    }
}

fn main() {
  let mut matrix = new_matrix(20, 20);
  matrix.rows = mtrx_rows();
  matrix.cols = matrix.cols_from_rows();
  let mut max_row_prod = 0u32;
  for i in 0..(matrix.rows.len()) {
      let current_row_prod = mult_windows(matrix.rows.iter().nth(i).unwrap().to_vec(), 4);
      if current_row_prod > max_row_prod {
          max_row_prod = current_row_prod;
      } else { max_row_prod; };
  }
  let mut max_col_prod = 0u32;
  for i in 0..(matrix.cols.len()) {
      let current_col_prod = mult_windows(matrix.cols.iter().nth(i).unwrap().to_vec(), 4);
      if current_col_prod > max_col_prod {
          max_col_prod = current_col_prod;
      } else { max_col_prod; };
  }
  let mut max_diag_prod = 0u32;
  let mut diags =vec![];
  for i in 0..(matrix.rows.len() - 3) {
    diags.push(matrix.matrix_diag_pos(0, i, 1, 1));
  }
  for i in (1..(matrix.rows.len() - 3)).rev() {
    diags.push(matrix.matrix_diag_pos(i,0,1,1));
  }
  for i in (3..(matrix.rows.len())).rev() {
    diags.push(matrix.matrix_diag_neg(i,0,1, 1));
  }
  for i in (0..(matrix.rows.len()-3)).rev() {
      diags.push(matrix.matrix_diag_neg(matrix.rows.len()-1,i,1,1));
  }
  for k in 0..diags.len() {
    let current_diag_prod = mult_windows(diags.iter().nth(k).unwrap().to_vec(), 4);
    if current_diag_prod > max_diag_prod {
        max_diag_prod = current_diag_prod;
    } else { max_diag_prod; };
  }
  println!("Max prod of diag sliced by four: {}", max_diag_prod);
  println!("Max prod of row sliced by four: {}", max_row_prod);
  println!("Max prod of col sliced by four: {}", max_col_prod);
}


fn mult_windows(num: Vec<u32>, window_size: usize) -> u32 {
    let mut prods = num.windows(window_size)
       .map(|i| i.iter().fold(1, |acc, &j| acc * j))
       .collect::<Vec<u32>>();
    prods.sort();
    *prods.last().unwrap()
}

fn mtrx_rows() -> Vec<Vec<u32>> {
    vec![vec![ 08,  02,  22,  97,  38,  15,  00,  40,  00,  75,  04,  05,  07,  78,  52,  12,  50,  77,  91,  08 ],
         vec![ 49,  49,  99,  40,  17,  81,  18,  57,  60,  87,  17,  40,  98,  43,  69,  48,  04,  56,  62,  00 ],
         vec![ 81,  49,  31,  73,  55,  79,  14,  29,  93,  71,  40,  67,  53,  88,  30,  03,  49,  13,  36,  65 ],
         vec![ 52,  70,  95,  23,  04,  60,  11,  42,  69,  24,  68,  56,  01,  32,  56,  71,  37,  02,  36,  91 ],
         vec![ 22,  31,  16,  71,  51,  67,  63,  89,  41,  92,  36,  54,  22,  40,  40,  28,  66,  33,  13,  80 ],
         vec![ 24,  47,  32,  60,  99,  03,  45,  02,  44,  75,  33,  53,  78,  36,  84,  20,  35,  17,  12,  50 ],
         vec![ 32,  98,  81,  28,  64,  23,  67,  10,  26,  38,  40,  67,  59,  54,  70,  66,  18,  38,  64,  70 ],
         vec![ 67,  26,  20,  68,  02,  62,  12,  20,  95,  63,  94,  39,  63,  08,  40,  91,  66,  49,  94,  21 ],
         vec![ 24,  55,  58,  05,  66,  73,  99,  26,  97,  17,  78,  78,  96,  83,  14,  88,  34,  89,  63,  72 ],
         vec![ 21,  36,  23,  09,  75,  00,  76,  44,  20,  45,  35,  14,  00,  61,  33,  97,  34,  31,  33,  95 ],
         vec![ 78,  17,  53,  28,  22,  75,  31,  67,  15,  94,  03,  80,  04,  62,  16,  14,  09,  53,  56,  92 ],
         vec![ 16,  39,  05,  42,  96,  35,  31,  47,  55,  58,  88,  24,  00,  17,  54,  24,  36,  29,  85,  57 ],
         vec![ 86,  56,  00,  48,  35,  71,  89,  07,  05,  44,  44,  37,  44,  60,  21,  58,  51,  54,  17,  58 ],
         vec![ 19,  80,  81,  68,  05,  94,  47,  69,  28,  73,  92,  13,  86,  52,  17,  77,  04,  89,  55,  40 ],
         vec![ 04,  52,  08,  83,  97,  35,  99,  16,  07,  97,  57,  32,  16,  26,  26,  79,  33,  27,  98,  66 ],
         vec![ 88,  36,  68,  87,  57,  62,  20,  72,  03,  46,  33,  67,  46,  55,  12,  32,  63,  93,  53,  69 ],
         vec![ 04,  42,  16,  73,  38,  25,  39,  11,  24,  94,  72,  18,  08,  46,  29,  32,  40,  62,  76,  36 ],
         vec![ 20,  69,  36,  41,  72,  30,  23,  88,  34,  62,  99,  69,  82,  67,  59,  85,  74,  04,  36,  16 ],
         vec![ 20,  73,  35,  29,  78,  31,  90,  01,  74,  31,  49,  71,  48,  86,  81,  16,  23,  57,  05,  54 ],
         vec![ 01,  70,  54,  71,  83,  51,  54,  69,  16,  92,  33,  48,  61,  43,  52,  01,  89,  19,  67,  48 ]
        ]

}

Answer 1

Disclaimer: I'm not familiar with the maths for this problem - I've added asserts to the code to make sure it stays correct!

I think there's a few changes you could make to get the code looking more Rust-y, and you can optimize a few things in the process:

• If you want an annotation to apply to its surroundings, you need a #! prefix - as it stands, you've only disabled dead code warnings for the Matrix struct, not the rest of your code.
• If you're creating a function that constructs an struct, it's conventional to have that be attached to the struct itself and called new.
• You don't need to specify the u32 at the end of your numeric literals in this case - the compiler can infer their type from their usage.
• Generally you don't need to use explicit indexes/ranges to iterate over a collection in Rust - the for expression can operate on anything that implements IntoIterator! By using this, you could remove a ton of unwrap boilerplate from your main function.
• Your else branches in your for loops aren't actually doing anything - note the 'path statement with no effect' warning in your compiler output!
• It's rare that you'll ever want to take a Vec as a parameter to a function - slices are more general/flexible. Also, note that every time you call to_vec, you're not just casting, you're making a copy of the data. I don't know if that's a performance bottleneck here, but it's not necessary either way.
• In general, I think you're copying/allocating vectors more often than you need to :p
• Try using the Clippy tool (which is available in the playground, or as a command line program) - it will analyze your code for common mistakes/things that are unidiomatic. For example, it pointed out to me that your fold in mult_windows actually just reimplements the existing Iterator product method!

There's probably more that you could do than I've done here (in particular, I think the code that calculates diagonals could be done with iterators without too much trouble), but hopefully it sets you in the right direction!

https://play.rust-lang.org/?gist=122310b496907b7da301a1d2987be837&version=stable

#![allow(dead_code)]

struct Matrix {
    size: (usize, usize),
    rows: Vec<Vec<u32>>,
    cols: Vec<Vec<u32>>,
}

impl Matrix {
    fn new(row_size: usize, col_size: usize) -> Matrix {
        Matrix {
            size: (row_size, col_size),
            rows: Vec::with_capacity(row_size),
            cols: Vec::with_capacity(col_size),
        }
    }

    fn cols_from_rows(&self) -> Vec<Vec<u32>> {
        let mut cols = vec![];
        for row in &self.rows {
            let mut col = vec![];
            for item in row {
                col.push(*item);
            }
            cols.push(col);
        }
        cols
    }

    fn rows_from_cols(&self) -> Vec<Vec<u32>> {
        let mut rows = vec![];
        for col in &self.cols {
            let mut row = vec![];
            for item in col {
                row.push(*item);
            }
            rows.push(row);
        }
        rows
    }

    fn matrix_row(&self, ndx: usize) -> &[u32] {
        &self.rows[ndx]
    }

    fn matrix_column(&self, ndx: usize) -> &[u32] {
        &self.cols[ndx]
    }

    fn matrix_diag_pos(
        &self,
        start_row: usize,
        start_col: usize,
        row_stride: usize,
        col_stride: usize,
    ) -> Vec<u32> {
        let mut diag = vec![];
        let mut cur_row = start_row;
        let mut cur_col = start_col;
        while cur_row < self.rows.len() && cur_col < self.cols.len() {
            diag.push(self.rows[cur_row][cur_col]);
            cur_row += row_stride;
            cur_col += col_stride;
        }
        diag
    }

    fn matrix_diag_neg(
        &self,
        start_row: usize,
        start_col: usize,
        row_stride: usize,
        col_stride: usize,
    ) -> Vec<u32> {
        let mut diag = vec![];
        let mut cur_row = start_row;
        let mut cur_col = start_col;
        while cur_col < self.cols.len() {
            diag.push(self.rows[cur_row][cur_col]);
            if cur_row != 0 {
                cur_row -= row_stride;
            } else {
                break;
            }
            cur_col += col_stride;
        }
        diag
    }
}

fn main() {
    let mut matrix = Matrix::new(20, 20);

    matrix.rows = mtrx_rows();
    matrix.cols = matrix.cols_from_rows();

    let mut max_row_prod = 0;

    for row in &matrix.rows {
        let current_row_prod = mult_windows(row, 4);
        if current_row_prod > max_row_prod {
            max_row_prod = current_row_prod;
        }
    }

    let mut max_col_prod = 0;

    for col in &matrix.cols {
        let current_col_prod = mult_windows(col, 4);
        if current_col_prod > max_col_prod {
            max_col_prod = current_col_prod;
        }
    }

    let mut max_diag_prod = 0;
    let mut diags = vec![];

    for i in 0..(matrix.rows.len() - 3) {
        diags.push(matrix.matrix_diag_pos(0, i, 1, 1));
    }

    for i in (1..(matrix.rows.len() - 3)).rev() {
        diags.push(matrix.matrix_diag_pos(i, 0, 1, 1));
    }

    for i in (3..(matrix.rows.len())).rev() {
        diags.push(matrix.matrix_diag_neg(i, 0, 1, 1));
    }

    for i in (0..(matrix.rows.len() - 3)).rev() {
        diags.push(matrix.matrix_diag_neg(matrix.rows.len() - 1, i, 1, 1));
    }

    for diag in &diags {
        let current_diag_prod = mult_windows(diag, 4);
        if current_diag_prod > max_diag_prod {
            max_diag_prod = current_diag_prod;
        }
    }

    println!("Max prod of diag sliced by four: {}", max_diag_prod);
    println!("Max prod of row sliced by four: {}", max_row_prod);
    println!("Max prod of col sliced by four: {}", max_col_prod);

    assert_eq!(70_600_674, max_diag_prod);
    assert_eq!(48_477_312, max_row_prod);
    assert_eq!(51_267_216, max_col_prod);
}

fn mult_windows(num: &[u32], window_size: usize) -> u32 {
    let mut prods = num.windows(window_size)
        .map(|i| i.iter().product())
        .collect::<Vec<u32>>();

    prods.sort();
    *prods.last().unwrap()
}

fn mtrx_rows() -> Vec<Vec<u32>> {
    vec![
        vec![
            08, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 08,
        ],
        vec![
            49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00,
        ],
        vec![
            81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65,
        ],
        vec![
            52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91,
        ],
        vec![
            22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80,
        ],
        vec![
            24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50,
        ],
        vec![
            32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70,
        ],
        vec![
            67, 26, 20, 68, 02, 62, 12, 20, 95, 63, 94, 39, 63, 08, 40, 91, 66, 49, 94, 21,
        ],
        vec![
            24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72,
        ],
        vec![
            21, 36, 23, 09, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95,
        ],
        vec![
            78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14, 09, 53, 56, 92,
        ],
        vec![
            16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57,
        ],
        vec![
            86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58,
        ],
        vec![
            19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40,
        ],
        vec![
            04, 52, 08, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66,
        ],
        vec![
            88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69,
        ],
        vec![
            04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 08, 46, 29, 32, 40, 62, 76, 36,
        ],
        vec![
            20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16,
        ],
        vec![
            20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54,
        ],
        vec![
            01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48,
        ],
    ]
}

EDIT:

You're right that Clippy itself still requires nightly, but that doesn't mean that your code has to target nightly - if you're using rustup to manage your toolchains (you should be!), you can do this:

cargo +nightly install clippy
cargo +nightly clippy

This compiles, installs and runs Clippy on the nightly toolchain without switching your default away from stable.

With regards to the references in the for loops - this goes back to what I was saying about for accepting anything that implements the IntoIterator trait. &'a Vec<T> implements IntoIterator in such a way that the for loop can automatically create an iterator of &'a T when you try to loop over it. You'd get the exact same result by doing for col in matrix.cols.iter().

This raises the question: why do you need the & if Vec<T> also implements IntoIterator? This is because the IntoIterator implementation for Vec<T> returns the actual values from the vector, not references to them - since data can only have one owner in Rust, this would result in you actually removing the data from the vector, which isn't what you want!