data.rs

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

const MAX_ITER: usize = 1000000000000;
const DIRECTIONS: [Move; 4] = [Move::Down, Move::Up, Move::Left, Move::Right];

fn main() {
    let args: Vec<_> = args().collect();
    if args.len() < 2 {
        return;
    }
    let mut vec: Vec<u8> = Vec::new();
    for ch in args[1].split(",") {
        vec.push(ch.parse::<u8>().unwrap());
    }
    let mut zero_loc: usize = 0;
    for i in 0..vec.len() {
        if vec[i] == 0 {
            zero_loc = i;
            break;
        }
    }
    println!("{:?}", vec);
    let start = Instant::now();
    let result = bfs(BoardState::new(vec, zero_loc));
    let elapsed = start.elapsed();
    println!("{:?}", elapsed);
    println!("{:?}", result);
}

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

#[derive(Debug)]
struct BoardState {
    board: Vec<u8>,
    moves: Vec<Move>,
    size: usize,
    empty_slot: usize,
}

// The board is represented as an array in memory, with 0 as the empty tile.
// [ 0 | 3 | 2 | 1]
//
// It represents a square matrix, which looks as follows.
// [0 | 3]
// [2 | 1]
//
// From this state the empty tile can be moved Right or Down.
// Moving Right
// [3 | 0]
// [2 | 1]
// Moving Down
// [2 | 3]
// [0 | 1]
//
//
impl BoardState {
    fn new(values: Vec<u8>, empty_slot: usize) -> BoardState {
        let size = (values.len() as f64).sqrt() as usize;
        BoardState {
            board: values,
            moves: Vec::new(),
            size: size,
            empty_slot: empty_slot,
        }
    }
    fn solved(size: usize) -> BoardState {
        let mut board: Vec<u8> = Vec::with_capacity(size);
        for i in 0..size {
            board.push(i as u8);
        }
        BoardState {
            board: board,
            moves: Vec::new(),
            size: 0,
            empty_slot: 0,
        }
    }

    #[inline]
    fn can_move(&self, direction: Move) -> bool {
        match direction {
            Move::Left => !(self.empty_slot % self.size == 0),
            Move::Right => !((self.empty_slot + 1) % self.size == 0),
            Move::Up => !(self.empty_slot < self.size),
            Move::Down => !(self.empty_slot >= self.size * self.size - self.size),
        }
    }

    fn move_direction(&self, direction: Move) -> BoardState {
        let mut new_board = self.board.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 - self.size,
            Move::Down => self.empty_slot + self.size,
        };
        new_moves.push(direction);
        new_board.swap(new_empty, self.empty_slot);

        BoardState {
            board: new_board,
            moves: new_moves,
            size: self.size,
            empty_slot: new_empty,
        }
    }
}

impl Clone for BoardState {
    fn clone(&self) -> BoardState {
        BoardState {
            board: self.board.clone(),
            moves: self.moves.clone(),
            size: self.size,
            empty_slot: self.empty_slot,
        }
    }
}

impl PartialEq for BoardState {
    fn eq(&self, other: &BoardState) -> bool {
        for (left, right) in self.board.iter().zip(other.board.iter()) {
            if left != right {
                return false;
            }
        }
        return true;
    }
}
impl Eq for BoardState {}

impl Hash for BoardState {
    fn hash<H: Hasher>(&self, state: &mut H) {
        for x in self.board.iter() {
            x.hash(state);
        }
    }
}


fn bfs(board: BoardState) -> Option<BoardState> {
    let mut frontier: VecDeque<BoardState> = VecDeque::new();
    let mut explored: HashSet<BoardState> = HashSet::new();
    let mut count: usize = 0;
    let solved = BoardState::solved(board.board.len());
    frontier.push_front(board);

    while frontier.len() > 0 && count < MAX_ITER {
        count += 1;
        let state: BoardState = frontier.pop_front().unwrap();
        explored.insert(state.clone());

        if state.eq(&solved) {
            return Some(state.clone());
        }
        for direction in DIRECTIONS.into_iter().filter(|&d| state.can_move(*d)) {
            let new_board = state.move_direction(*direction);
            if explored.get(&new_board).is_some() {
                continue;
            } else {
                frontier.push_back(new_board);
            }
        }
    }
    None
}