Initial rotate matrix attempt

tim-harding · Sep 1, 2023 · a948529 · a948529
1 parent b19b135
commit a948529
Show file tree

Hide file tree

Showing 4 changed files with 100 additions and 0 deletions.
diff --git a/src/problems/_01_arrays_and_strings/_07_rotate_matrix.rs b/src/problems/_01_arrays_and_strings/_07_rotate_matrix.rs
@@ -0,0 +1,66 @@
+pub trait RotateMatrix {
+    /// Given an image represented by an NxN matrix, where each pixel in the
+    /// image is 4 bytes, write a method to rotate the image by 90 degrees. Can
+    /// you do this in place?
+    fn rotate_matrix(image: &mut Vec<Pixel>, n: usize);
+}
+
+#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord)]
+pub struct Pixel([u8; 4]);
+
+struct Solution;
+
+impl RotateMatrix for Solution {
+    fn rotate_matrix(image: &mut Vec<Pixel>, n: usize) {
+        // Replace with your solution
+        use crate::solutions::_01_arrays_and_strings::_07_rotate_matrix as solutions;
+        solutions::Solution::rotate_matrix(image, n)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn rotates_3x3_image() {
+        #[rustfmt::skip]
+        let mut input = monochrome_image(&[
+            1, 2, 3, 
+            4, 5, 6,
+            7, 8, 9,
+        ]);
+        #[rustfmt::skip]
+        let expected = monochrome_image(&[
+            7, 4, 1,
+            8, 5, 2,
+            9, 6, 3,
+        ]);
+        Solution::rotate_matrix(&mut input, 3);
+        assert_eq!(input, expected);
+    }
+
+    #[test]
+    fn rotates_4x4_image() {
+        #[rustfmt::skip]
+        let mut input = monochrome_image(&[
+             1,  2,  3,  4,
+             5,  6,  7,  8,
+             9, 10, 11, 12,
+            13, 14, 15, 16,
+        ]);
+        #[rustfmt::skip]
+        let expected = monochrome_image(&[
+            13,  9, 5, 1,
+            14, 10, 6, 2,
+            15, 11, 7, 3,
+            16, 12, 8, 4,
+        ]);
+        Solution::rotate_matrix(&mut input, 4);
+        assert_eq!(input, expected);
+    }
+
+    fn monochrome_image(values: &[u8]) -> Vec<Pixel> {
+        values.into_iter().map(|&v| Pixel([v, v, v, v])).collect()
+    }
+}
diff --git a/src/problems/_01_arrays_and_strings/mod.rs b/src/problems/_01_arrays_and_strings/mod.rs
@@ -4,3 +4,4 @@ pub mod _03_urlify;
 pub mod _04_palindrome_permutation;
 pub mod _05_one_away;
 pub mod _06_string_compression;
+pub mod _07_rotate_matrix;
diff --git a/src/solutions/_01_arrays_and_strings/_07_rotate_matrix.rs b/src/solutions/_01_arrays_and_strings/_07_rotate_matrix.rs
@@ -0,0 +1,32 @@
+use crate::problems::_01_arrays_and_strings::_07_rotate_matrix::{Pixel, RotateMatrix};
+
+pub struct Solution;
+
+impl RotateMatrix for Solution {
+    fn rotate_matrix(image: &mut Vec<Pixel>, n: usize) {
+        // Iterate over a triangle forming a 1/8th slice of the image
+        for y in 0..n / 2 {
+            for x in y..n / 2 {
+                let mut x = x;
+                let mut y = y;
+                let mut tmp = image[y * n + x];
+                for _ in 0..4 {
+                    (x, y) = rotate_90(x, y, n);
+                    std::mem::swap(&mut image[y * n + x], &mut tmp);
+                }
+            }
+        }
+    }
+}
+
+fn rotate_90(x: usize, y: usize, n: usize) -> (usize, usize) {
+    // let h = n / 2
+    // Translate by (-h, -h) such that the center as at the origin
+    // Apply the 90° rotation matrix
+    // Reverse the translation
+    // ┏      ┓┏   ┓   ┏ ┓   ┏   ┓
+    // ┃  0 1 ┃┃x-h┃ + ┃h┃ = ┃  y┃
+    // ┃ -1 0 ┃┃y-h┃   ┃h┃   ┃n-x┃
+    // ┗      ┛┗   ┛   ┗ ┛   ┗   ┛
+    (y, n - x - 1)
+}
diff --git a/src/solutions/_01_arrays_and_strings/mod.rs b/src/solutions/_01_arrays_and_strings/mod.rs
@@ -4,3 +4,4 @@ pub mod _03_urlify;
 pub mod _04_palindrome_permutation;
 pub mod _05_one_away;
 pub mod _06_string_compression;
+pub mod _07_rotate_matrix;