Click to change color scheme

Notes on codes, projects and everything

Learning a new language for more than 2 months (feat. Exercism)

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.

leave your comment

name is required

email is required

have a blog?

This blog uses scripts to assist and automate comment moderation, and the author of this blog post does not hold responsibility in the content of posted comments. Please note that activities such as flaming, ungrounded accusations as well as spamming will not be entertained.