Saddle point
In short the objective is to find an entry which is greater than all its rowmates, but smallest among the cellmates (pun not intended). As usual, my first attempt is clumsy and somehow started a discussion with my mentor on code readability.
pub fn find_saddle_points(input: &[Vec<u64>]) -> Vec<(usize, usize)> {
input
.iter()
.enumerate()
.map(|(row_idx, row)| match find_max(row) {
Some(max) => row.iter()
.enumerate()
.filter(|(_idx, &value)| value == max)
.map(|(col_idx, &value)| {
let col = input.iter().map(|crow| crow[col_idx]).collect::<Vec<u64>>();
let min = find_min(&col);
if value == min {
Some((row_idx, col_idx))
} else {
None
}
})
.filter(|x| x.is_some())
.map(|x| x.unwrap())
.collect::<Vec<(usize, usize)>>(),
_ => vec![],
})
.fold(vec![], |mut result: Vec<(usize, usize)>, incoming| {
result.append(&mut incoming.clone());
result
})
}
fn find_min(input: &Vec<u64>) -> u64 {
input.iter().fold(
input[0],
|result, &incoming| {
if result <= incoming {
result
} else {
incoming
}
},
)
}
fn find_max(input: &Vec<u64>) -> Option<u64> {
match input.len() {
0 => None,
_ => input.iter().fold(Some(input[0]), |result, &incoming| {
if result.unwrap() >= incoming {
result
} else {
Some(incoming)
}
}),
}
}
Not the most efficient solution, cloning is probably unnecesary, still unfamiliar with the borrow checker, but code somehow works. Then I was told about flat_map that I totally overlooked in the documentation. After some iterations, the code became
use std::cmp::{max, min};
use std::u64::MAX;
pub fn find_saddle_points(input: &[Vec<u64>]) -> Vec<(usize, usize)> {
input
.iter()
.enumerate()
.flat_map(|(row_idx, row)| match find_max(&row) {
Some(max) => row.iter()
.enumerate()
.filter(|(_idx, &value)| value == max)
.flat_map(|(col_idx, &value)| {
match find_min(&input.iter().map(|crow| crow[col_idx]).collect::<Vec<u64>>()) {
min if value == min => vec![(row_idx, col_idx)],
_ => vec![],
}
})
.collect::<Vec<(usize, usize)>>(),
_ => vec![],
})
.collect::<Vec<(usize, usize)>>()
}
fn find_min(input: &Vec<u64>) -> u64 {
input.iter().cloned().fold(MAX, min)
}
fn find_max(input: &Vec<u64>) -> Option<u64> {
match input.len() {
0 => None,
_ => Some(input.iter().cloned().fold(0, max)),
}
}
Not sure if it would look different if I re-do today (like what I did to the previous exercise). However I learned a lot throughout the peer review process.
Then the exercises get harder.
