datas.rs

use std::collections::VecDeque;
use std::collections::HashSet;
use std::hash::{Hash, Hasher};
use std::time::Instant;

fn main() {
    let start = Instant::now();
    let result = bfs(Board3::new(vec![0, 2, 5, 6, 8, 3, 4, 7, 1]));
    let elapsed = start.elapsed();
    println!("{:?}", elapsed);
    println!("{:?}", result);
}

#[derive(Debug, Eq, PartialEq, PartialOrd, Ord, Copy, Clone)]
enum Move {
    Left = 0,
    Right = 1,
    Up = 2,
    Down = 3,
}

fn bfs<T: Board>(board: T) -> Option<T> {
    let mut frontier: VecDeque<T> = VecDeque::new();
    let mut explored: HashSet<T> = HashSet::new();
    let solved = T::solved();
    frontier.push_front(board);

    while !frontier.is_empty() {
        let state: T = frontier.pop_front().unwrap();
        explored.insert(state.clone());

        if state.eq(&solved) {
            return Some(state.clone());
        }
        if state.can_move(Move::Up) {
            let new_board = state.move_direction(Move::Up);
            if explored.get(&new_board).is_none() {
                frontier.push_back(new_board);
            }
        }
        if state.can_move(Move::Down) {
            let new_board = state.move_direction(Move::Down);
            if explored.get(&new_board).is_none() {
                frontier.push_back(new_board);
            }
        }
        if state.can_move(Move::Left) {
            let new_board = state.move_direction(Move::Left);
            if explored.get(&new_board).is_none() {
                frontier.push_back(new_board);
            }

        }
        if state.can_move(Move::Right) {
            let new_board = state.move_direction(Move::Right);
            if explored.get(&new_board).is_none() {
                frontier.push_back(new_board);
            }
        }
    }
    None
}

trait Board: Hash + Eq + Clone {
    /// Creates a new board from a raw vector of values.
    /// Does verification that the board is correct and should not be used in
    /// a tight loop.
    fn new(values: Vec<u8>) -> Self;

    /// Returns the cannonical solved board for the given size.
    fn solved() -> Self;

    /// Will moving in the provided direction yield a valid board.
    fn can_move(&self, direction: Move) -> bool;

    /// Moves the empty piece in the given direction.
    /// Does not check if it is valid, guard with can_move.
    fn move_direction(&self, direction: Move) -> Self;
}

#[derive(Debug)]
struct Board2 {
    values: [u8; 4],
    empty_slot: usize,
    moves: Vec<Move>,
}

impl Board for Board2 {
    fn new(values: Vec<u8>) -> Board2 {
        assert!(values.len() == 4);
        let mut zero_loc = 0;
        for i in 0..values.len() {
            if values[i] == 0 {
                zero_loc = i;
                break;
            }
        }
        Board2 {
            values: [values[0], values[1], values[2], values[3]],
            empty_slot: zero_loc,
            moves: Vec::new(),
        }
    }

    fn solved() -> Board2 {
        Board2 {
            values: [0, 1, 2, 3],
            empty_slot: 0,
            moves: Vec::new(),
        }
    }

    #[inline]
    fn can_move(&self, direction: Move) -> bool {
        match direction {
            Move::Left => self.empty_slot == 1 || self.empty_slot == 3,
            Move::Right => self.empty_slot == 0 || self.empty_slot == 2,
            Move::Up => self.empty_slot >= 2,
            Move::Down => self.empty_slot < 2,
        }
    }

    fn move_direction(&self, direction: Move) -> Board2 {
        let mut new_board = self.values.clone();
        let mut new_moves = self.moves.clone();
        let new_empty = match direction {
            Move::Left => self.empty_slot - 1,
            Move::Right => self.empty_slot + 1,
            Move::Up => self.empty_slot - 2,
            Move::Down => self.empty_slot + 2,
        };
        new_moves.push(direction);
        new_board.swap(new_empty, self.empty_slot);

        Board2 {
            values: new_board,
            moves: new_moves,
            empty_slot: new_empty,
        }
    }
}

impl PartialEq for Board2 {
    fn eq(&self, other: &Board2) -> bool {
        self.values[0] == other.values[0] && self.values[1] == other.values[1] &&
        self.values[2] == other.values[2] && self.values[3] == other.values[3]
    }
}

impl Eq for Board2 {}

impl Hash for Board2 {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.values[0].hash(state);
        self.values[1].hash(state);
        self.values[2].hash(state);
        self.values[3].hash(state);
    }
}

impl Clone for Board2 {
    fn clone(&self) -> Board2 {
        Board2 {
            values: self.values.clone(),
            moves: self.moves.clone(),
            empty_slot: self.empty_slot,
        }
    }
}



#[derive(Debug)]
struct Board3 {
    values: [u8; 9],
    empty_slot: usize,
    moves: Vec<Move>,
}

impl Board for Board3 {
    fn new(values: Vec<u8>) -> Board3 {
        assert!(values.len() == 9);
        let mut zero_loc = 0;
        for i in 0..values.len() {
            if values[i] == 0 {
                zero_loc = i;
                break;
            }
        }
        Board3 {
            values: [values[0], values[1], values[2], values[3], values[4], values[5], values[6],
                     values[7], values[8]],
            empty_slot: zero_loc,
            moves: Vec::new(),
        }
    }

    fn solved() -> Board3 {
        Board3 {
            values: [0, 1, 2, 3, 4, 5, 6, 7, 8],
            empty_slot: 0,
            moves: Vec::new(),
        }
    }

    #[inline]
    fn can_move(&self, direction: Move) -> bool {
        match direction {
            Move::Left => self.empty_slot != 0 && self.empty_slot != 3 && self.empty_slot != 6,
            Move::Right => self.empty_slot != 2 && self.empty_slot != 5 && self.empty_slot != 8,
            Move::Up => self.empty_slot > 2,
            Move::Down => self.empty_slot <= 5,
        }
    }

    fn move_direction(&self, direction: Move) -> Board3 {
        let mut new_board = self.values.clone();
        let mut new_moves = self.moves.clone();
        let new_empty = match direction {
            Move::Left => self.empty_slot - 1,
            Move::Right => self.empty_slot + 1,
            Move::Up => self.empty_slot - 3,
            Move::Down => self.empty_slot + 3,
        };
        new_moves.push(direction);
        new_board.swap(new_empty, self.empty_slot);

        Board3 {
            values: new_board,
            moves: new_moves,
            empty_slot: new_empty,
        }
    }
}

impl PartialEq for Board3 {
    fn eq(&self, other: &Board3) -> bool {
        self.values[0] == other.values[0] && self.values[1] == other.values[1] &&
        self.values[2] == other.values[2] && self.values[3] == other.values[3] &&
        self.values[4] == other.values[4] && self.values[5] == other.values[5] &&
        self.values[6] == other.values[6] &&
        self.values[7] == other.values[7] && self.values[8] == other.values[8]
    }
}

impl Eq for Board3 {}

impl Hash for Board3 {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.values[0].hash(state);
        self.values[1].hash(state);
        self.values[2].hash(state);
        self.values[3].hash(state);
        self.values[4].hash(state);
        self.values[5].hash(state);
        self.values[6].hash(state);
        self.values[7].hash(state);
        self.values[8].hash(state);
    }
}

impl Clone for Board3 {
    fn clone(&self) -> Board3 {
        Board3 {
            values: self.values.clone(),
            moves: self.moves.clone(),
            empty_slot: self.empty_slot,
        }
    }
}