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?
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 ]
]
}