[rust] Saddle Points

6 files changed, 261 insertions, 0 deletions

diff --git a/saddle-points/.exercism/metadata.json b/saddle-points/.exercism/metadata.json
new file mode 100644
index 0000000..cb44aa3
--- /dev/null
+++ b/saddle-points/.exercism/metadata.json
@@ -0,0 +1 @@
+{"track":"rust","exercise":"saddle-points","id":"18964e9c5971482790e97a569346a40d","url":"https://exercism.io/my/solutions/18964e9c5971482790e97a569346a40d","handle":"dyamon","is_requester":true,"auto_approve":false}
\ No newline at end of file
diff --git a/saddle-points/.gitignore b/saddle-points/.gitignore
new file mode 100644
index 0000000..db7f315
--- /dev/null
+++ b/saddle-points/.gitignore
@@ -0,0 +1,8 @@
+# Generated by Cargo
+# will have compiled files and executables
+/target/
+**/*.rs.bk
+
+# Remove Cargo.lock from gitignore if creating an executable, leave it for libraries
+# More information here http://doc.crates.io/guide.html#cargotoml-vs-cargolock
+Cargo.lock
diff --git a/saddle-points/Cargo.toml b/saddle-points/Cargo.toml
new file mode 100644
index 0000000..5f262e2
--- /dev/null
+++ b/saddle-points/Cargo.toml
@@ -0,0 +1,6 @@
+[package]
+edition = "2018"
+name = "saddle-points"
+version = "1.3.0"
+
+[dependencies]
diff --git a/saddle-points/README.md b/saddle-points/README.md
new file mode 100644
index 0000000..84647d0
--- /dev/null
+++ b/saddle-points/README.md
@@ -0,0 +1,132 @@
+# Saddle Points
+
+Detect saddle points in a matrix.
+
+So say you have a matrix like so:
+
+```text
+    1  2  3
+  |---------
+1 | 9  8  7
+2 | 5  3  2     <--- saddle point at column 1, row 2, with value 5
+3 | 6  6  7
+```
+
+It has a saddle point at column 1, row 2.
+
+It's called a "saddle point" because it is greater than or equal to
+every element in its row and less than or equal to every element in
+its column.
+
+A matrix may have zero or more saddle points.
+
+Your code should be able to provide the (possibly empty) list of all the
+saddle points for any given matrix.
+
+The matrix can have a different number of rows and columns (Non square).
+
+Note that you may find other definitions of matrix saddle points online,
+but the tests for this exercise follow the above unambiguous definition.
+
+## Rust Indices Start At 0
+
+By convention, ordered sequences of values in Rust have their contents numbered
+("indexed") starting from 0. This applies regardless of what the rest of the
+exercise description in this README says, such as references to indices that
+start at 1, so you will have to subtract 1 to translate those index numbers
+to Rust index numbers.
+
+## Efficiency Notice
+
+This exercise uses a _vector of vectors_ to store the content of matrices. While
+this exercise is designed to help students understand basic concepts about
+vectors, such as indexing, and that nested data types are legal, _vector of
+vectors_ is a suboptimal choice for high-performance matrix algebra and any
+similar efficient processing of larger amounts of data.
+
+The detailed explanation of this inefficiency is beyond the scope of this
+exercise and this learning track in general. This aspect is known as
+[cache locality](https://stackoverflow.com/questions/12065774/why-does-cache-locality-matter-for-array-performance)
+and you can find a good introduction to it by clicking that link if you'd like
+to learn more about details of a modern computer architecture.
+
+
+## Rust Installation
+
+Refer to the [exercism help page][help-page] for Rust installation and learning
+resources.
+
+## Writing the Code
+
+Execute the tests with:
+
+```bash
+$ cargo test
+```
+
+All but the first test have been ignored. After you get the first test to
+pass, open the tests source file which is located in the `tests` directory
+and remove the `#[ignore]` flag from the next test and get the tests to pass
+again. Each separate test is a function with `#[test]` flag above it.
+Continue, until you pass every test.
+
+If you wish to run all ignored tests without editing the tests source file, use:
+
+```bash
+$ cargo test -- --ignored
+```
+
+To run a specific test, for example `some_test`, you can use:
+
+```bash
+$ cargo test some_test
+```
+
+If the specific test is ignored use:
+
+```bash
+$ cargo test some_test -- --ignored
+```
+
+To learn more about Rust tests refer to the [online test documentation][rust-tests]
+
+Make sure to read the [Modules][modules] chapter if you
+haven't already, it will help you with organizing your files.
+
+## Further improvements
+
+After you have solved the exercise, please consider using the additional utilities, described in the [installation guide](https://exercism.io/tracks/rust/installation), to further refine your final solution.
+
+To format your solution, inside the solution directory use
+
+```bash
+cargo fmt
+```
+
+To see, if your solution contains some common ineffective use cases, inside the solution directory use
+
+```bash
+cargo clippy --all-targets
+```
+
+## Submitting the solution
+
+Generally you should submit all files in which you implemented your solution (`src/lib.rs` in most cases). If you are using any external crates, please consider submitting the `Cargo.toml` file. This will make the review process faster and clearer.
+
+## Feedback, Issues, Pull Requests
+
+The [exercism/rust](https://github.com/exercism/rust) repository on GitHub is the home for all of the Rust exercises. If you have feedback about an exercise, or want to help implement new exercises, head over there and create an issue. Members of the rust track team are happy to help!
+
+If you want to know more about Exercism, take a look at the [contribution guide](https://github.com/exercism/docs/blob/master/contributing-to-language-tracks/README.md).
+
+[help-page]: https://exercism.io/tracks/rust/learning
+[modules]: https://doc.rust-lang.org/book/ch07-02-defining-modules-to-control-scope-and-privacy.html
+[cargo]: https://doc.rust-lang.org/book/ch14-00-more-about-cargo.html
+[rust-tests]: https://doc.rust-lang.org/book/ch11-02-running-tests.html
+
+## Source
+
+J Dalbey's Programming Practice problems [http://users.csc.calpoly.edu/~jdalbey/103/Projects/ProgrammingPractice.html](http://users.csc.calpoly.edu/~jdalbey/103/Projects/ProgrammingPractice.html)
+
+## Submitting Incomplete Solutions
+It's possible to submit an incomplete solution so you can see how others have completed the exercise.
diff --git a/saddle-points/src/lib.rs b/saddle-points/src/lib.rs
new file mode 100644
index 0000000..7123243
--- /dev/null
+++ b/saddle-points/src/lib.rs
@@ -0,0 +1,16 @@
+fn is_min(mat: &[Vec<u64>], col: usize, row: usize) -> bool {
+    (0..mat.len()).all(|r| mat[r][col] >= mat[row][col])
+}
+
+pub fn find_saddle_points(input: &[Vec<u64>]) -> Vec<(usize, usize)> {
+    let mut res = vec![];
+    for (row,relem) in input.iter().enumerate() {
+        let m = relem.iter().max();
+        for (col,celem) in relem.iter().enumerate() {
+            if (m == Some(celem)) && is_min(input,col,row) {
+                res.push((row,col));
+            }
+        }
+    }
+    res
+}
diff --git a/saddle-points/tests/saddle-points.rs b/saddle-points/tests/saddle-points.rs
new file mode 100644
index 0000000..1fbc2de
--- /dev/null
+++ b/saddle-points/tests/saddle-points.rs
@@ -0,0 +1,98 @@
+use saddle_points;
+
+use saddle_points::find_saddle_points;
+
+// We don't care about order
+fn find_sorted_saddle_points(input: &[Vec<u64>]) -> Vec<(usize, usize)> {
+    let mut result = saddle_points::find_saddle_points(input);
+    result.sort();
+    result
+}
+
+#[test]
+fn identify_single_saddle_point() {
+    let input = vec![vec![9, 8, 7], vec![5, 3, 2], vec![6, 6, 7]];
+    assert_eq!(vec![(1, 0)], find_saddle_points(&input));
+}
+
+#[test]
+fn identify_empty_matrix() {
+    let input = vec![vec![], vec![], vec![]];
+    let expected: Vec<(usize, usize)> = Vec::new();
+    assert_eq!(expected, find_saddle_points(&input));
+}
+
+#[test]
+fn identify_lack_of_saddle_point() {
+    let input = vec![vec![1, 2, 3], vec![3, 1, 2], vec![2, 3, 1]];
+    let expected: Vec<(usize, usize)> = Vec::new();
+    assert_eq!(expected, find_saddle_points(&input));
+}
+
+#[test]
+fn multiple_saddle_points_in_col() {
+    let input = vec![vec![4, 5, 4], vec![3, 5, 5], vec![1, 5, 4]];
+    assert_eq!(
+        vec![(0, 1), (1, 1), (2, 1)],
+        find_sorted_saddle_points(&input)
+    );
+}
+
+#[test]
+fn multiple_saddle_points_in_row() {
+    let input = vec![vec![6, 7, 8], vec![5, 5, 5], vec![7, 5, 6]];
+    assert_eq!(
+        vec![(1, 0), (1, 1), (1, 2)],
+        find_sorted_saddle_points(&input)
+    );
+}
+
+#[test]
+fn identify_bottom_right_saddle_point() {
+    let input = vec![vec![8, 7, 9], vec![6, 7, 6], vec![3, 2, 5]];
+    assert_eq!(vec![(2, 2)], find_saddle_points(&input));
+}
+
+// track specific as of v1.3
+#[test]
+fn non_square_matrix_high() {
+    let input = vec![vec![1, 5], vec![3, 6], vec![2, 7], vec![3, 8]];
+    assert_eq!(vec![(0, 1)], find_saddle_points(&input));
+}
+
+#[test]
+fn non_square_matrix_wide() {
+    let input = vec![vec![3, 1, 3], vec![3, 2, 4]];
+    assert_eq!(vec![(0, 0), (0, 2)], find_sorted_saddle_points(&input));
+}
+
+#[test]
+fn single_column_matrix() {
+    let input = vec![vec![2], vec![1], vec![4], vec![1]];
+    assert_eq!(vec![(1, 0), (3, 0)], find_sorted_saddle_points(&input));
+}
+
+#[test]
+fn single_row_matrix() {
+    let input = vec![vec![2, 5, 3, 5]];
+    assert_eq!(vec![(0, 1), (0, 3)], find_sorted_saddle_points(&input));
+}
+
+#[test]
+fn identify_all_saddle_points() {
+    let input = vec![vec![5, 5, 5], vec![5, 5, 5], vec![5, 5, 5]];
+    assert_eq!(
+        vec![
+            (0, 0),
+            (0, 1),
+            (0, 2),
+            (1, 0),
+            (1, 1),
+            (1, 2),
+            (2, 0),
+            (2, 1),
+            (2, 2)
+        ],
+        find_sorted_saddle_points(&input)
+    );
+}