Instantly share code, notes, and snippets.

@codesections /robot_paths.rs
Last active Jan 10, 2019

Embed
What would you like to do?
Download ZIP
Unified Split

Revisions

  1. codesections revised this gist Jan 9, 2019. 1 changed file with 1 addition and 1 deletion.
    View file
    2 robot_paths.rs
    @@ -45,7 +45,7 @@ fn robot_paths(n: usize) -> usize {
    board.toggle_piece(i, j);
    result
    }
    robot_paths(n, &mut Board::new(7), 0, 0)
    robot_paths(n, &mut Board::new(n), 0, 0)
    }

    #[cfg(test)]
  2. codesections revised this gist Jan 9, 2019. 1 changed file with 36 additions and 32 deletions.
    View file
    68 robot_paths.rs
    @@ -1,5 +1,5 @@
    fn main() {
    println!("{:?}", robot_paths(6, &mut Board::new(6), None, None));
    println!("{:?}", robot_paths(6));
    }

    #[derive(Clone)]
    @@ -8,47 +8,51 @@ struct Board {
    }

    impl Board {
    fn new(n: i32) -> Board {
    let mut squares = Vec::new();

    for i in 0..n {
    squares.push(Vec::new());
    for _ in 0..n {
    squares[i as usize].push(false);
    }
    fn new(n: usize) -> Board {
    Board {
    squares: vec![vec![false; n]; n],
    }

    Board { squares }
    }

    fn toggle_piece(&mut self, i: i32, j: i32) {
    let i = i as usize;
    let j = j as usize;
    fn toggle_piece(&mut self, i: usize, j: usize) {
    self.squares[i][j] = !self.squares[i][j];
    }

    fn has_been_visited(&mut self, i: i32, j: i32) -> bool {
    let i = i as usize;
    let j = j as usize;
    fn has_been_visited(&mut self, i: usize, j: usize) -> bool {
    self.squares[i][j]
    }
    }

    fn robot_paths(n: i32, board: &mut Board, i: Option<i32>, j: Option<i32>) -> i32 {
    let i = i.unwrap_or(0);
    let j = j.unwrap_or(0);
    if !(i >= 0 && i < n && j >= 0 && j < n) || board.has_been_visited(i, j) {
    return 0;
    fn robot_paths(n: usize) -> usize {
    fn robot_paths(n: usize, board: &mut Board, i: usize, j: usize) -> usize {
    if i == n - 1 && j == n - 1 {
    return 1;
    }
    board.toggle_piece(i, j);
    let mut result = 0;
    for x in [(0, 1), (1, 0), (-1, 0), (0, -1)].iter() {
    let i = i as isize + x.0;
    let j = j as isize + x.1;
    if i >= 0
    && j >= 0
    && i < n as isize
    && j < n as isize
    && !board.has_been_visited(i as usize, j as usize)
    {
    result += robot_paths(n, board, i as usize, j as usize);
    }
    }
    board.toggle_piece(i, j);
    result
    }
    if i == n - 1 && j == n - 1 {
    return 1;
    robot_paths(n, &mut Board::new(7), 0, 0)
    }

    #[cfg(test)]
    mod test {
    use super::*;
    #[test]
    fn it_works() {
    assert_eq!(8512, robot_paths(5))
    }
    board.toggle_piece(i, j);
    let result = robot_paths(n, board, Some(i), Some(j + 1))
    + robot_paths(n, board, Some(i), Some(j - 1))
    + robot_paths(n, board, Some(i + 1), Some(j))
    + robot_paths(n, board, Some(i - 1), Some(j));
    // Return the board to its original state
    board.toggle_piece(i, j);
    result
    }
  3. codesections revised this gist Jan 8, 2019. 1 changed file with 6 additions and 7 deletions.
    View file
    13 robot_paths.rs
    @@ -1,5 +1,5 @@
    fn main() {
    println!("{:?}", robot_paths(6, None, None, None));
    println!("{:?}", robot_paths(6, &mut Board::new(6), None, None));
    }

    #[derive(Clone)]
    @@ -34,8 +34,7 @@ impl Board {
    }
    }

    fn robot_paths(n: i32, board: Option<Board>, i: Option<i32>, j: Option<i32>) -> i32 {
    let mut board = board.unwrap_or(Board::new(n));
    fn robot_paths(n: i32, board: &mut Board, i: Option<i32>, j: Option<i32>) -> i32 {
    let i = i.unwrap_or(0);
    let j = j.unwrap_or(0);
    if !(i >= 0 && i < n && j >= 0 && j < n) || board.has_been_visited(i, j) {
    @@ -45,10 +44,10 @@ fn robot_paths(n: i32, board: Option<Board>, i: Option<i32>, j: Option<i32>) ->
    return 1;
    }
    board.toggle_piece(i, j);
    let result = robot_paths(n, Some(board.clone()), Some(i), Some(j + 1))
    + robot_paths(n, Some(board.clone()), Some(i), Some(j - 1))
    + robot_paths(n, Some(board.clone()), Some(i + 1), Some(j))
    + robot_paths(n, Some(board.clone()), Some(i - 1), Some(j));
    let result = robot_paths(n, board, Some(i), Some(j + 1))
    + robot_paths(n, board, Some(i), Some(j - 1))
    + robot_paths(n, board, Some(i + 1), Some(j))
    + robot_paths(n, board, Some(i - 1), Some(j));
    // Return the board to its original state
    board.toggle_piece(i, j);
    result
  4. codesections created this gist Jan 8, 2019.
    View file
    55 robot_paths.rs
    @@ -0,0 +1,55 @@
    fn main() {
    println!("{:?}", robot_paths(6, None, None, None));
    }

    #[derive(Clone)]
    struct Board {
    squares: Vec<Vec<bool>>,
    }

    impl Board {
    fn new(n: i32) -> Board {
    let mut squares = Vec::new();

    for i in 0..n {
    squares.push(Vec::new());
    for _ in 0..n {
    squares[i as usize].push(false);
    }
    }

    Board { squares }
    }

    fn toggle_piece(&mut self, i: i32, j: i32) {
    let i = i as usize;
    let j = j as usize;
    self.squares[i][j] = !self.squares[i][j];
    }

    fn has_been_visited(&mut self, i: i32, j: i32) -> bool {
    let i = i as usize;
    let j = j as usize;
    self.squares[i][j]
    }
    }

    fn robot_paths(n: i32, board: Option<Board>, i: Option<i32>, j: Option<i32>) -> i32 {
    let mut board = board.unwrap_or(Board::new(n));
    let i = i.unwrap_or(0);
    let j = j.unwrap_or(0);
    if !(i >= 0 && i < n && j >= 0 && j < n) || board.has_been_visited(i, j) {
    return 0;
    }
    if i == n - 1 && j == n - 1 {
    return 1;
    }
    board.toggle_piece(i, j);
    let result = robot_paths(n, Some(board.clone()), Some(i), Some(j + 1))
    + robot_paths(n, Some(board.clone()), Some(i), Some(j - 1))
    + robot_paths(n, Some(board.clone()), Some(i + 1), Some(j))
    + robot_paths(n, Some(board.clone()), Some(i - 1), Some(j));
    // Return the board to its original state
    board.toggle_piece(i, j);
    result
    }