-
Notifications
You must be signed in to change notification settings - Fork 0
Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
- Loading branch information
1 parent
b19b135
commit a948529
Showing
4 changed files
with
100 additions
and
0 deletions.
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -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() | ||
} | ||
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -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) | ||
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters