leetcode

0773-sliding-puzzle.rs (4746B)

/// 773. Sliding Puzzle (Hard)
///
/// On an 2 x 3 board, there are five tiles labeled from 1 to 5, and an empty
/// square represented by 0. A *move* consists of choosing 0 and a
/// 4-directionally adjacent number and swapping it.
///
/// The state of the board is solved if and only if the board is
/// [[1,2,3],[4,5,0]].
///
/// Given the puzzle board board, return the least number of moves required so
/// that the state of the board is solved. If it is impossible for the state of
/// the board to be solved, return -1.
///
/// *Example 1:*
///
///   *Input:* board = [[1,2,3],[4,0,5]]
///   *Output:* 1
///   *Explanation:* Swap the 0 and the 5 in one move.
///
/// *Example 2:*
///
///   *Input:* board = [[1,2,3],[5,4,0]]
///   *Output:* -1
///   *Explanation:* No number of moves will make the board solved.
///
/// *Example 3:*
///
///   *Input:* board = [[4,1,2],[5,0,3]]
///   *Output:* 5
///   *Explanation:* 5 is the smallest number of moves that solves the board.
///   An example path:
///   After move 0: [[4,1,2],[5,0,3]]
///   After move 1: [[4,1,2],[0,5,3]]
///   After move 2: [[0,1,2],[4,5,3]]
///   After move 3: [[1,0,2],[4,5,3]]
///   After move 4: [[1,2,0],[4,5,3]]
///   After move 5: [[1,2,3],[4,5,0]]
///
/// *Constraints:*
///
///   * board.length == 2
///   * board[i].length == 3
///   * 0 <= board[i][j] <= 5
///   * Each value board[i][j] is *unique*.
///
use leetcode::*;
use std::cmp::Ordering;
use std::collections::hash_map;
use std::collections::{BinaryHeap, HashMap};

type Board = [u8; 6];

const FINAL: Board = [1, 2, 3, 4, 5, 0];

#[derive(Clone, Eq)]
struct State {
    board: Board,
    pos: u8,
    dist: u32,
    cost: u32,
}

impl State {
    fn new(board: Board, pos: u8) -> Self {
        Self {
            board,
            pos,
            dist: 0,
            cost: Self::board_cost(board),
        }
    }

    fn swap(&self, pos: u8) -> Self {
        let mut board = self.board;
        board.swap(self.pos as usize, pos as usize);
        Self {
            board,
            dist: self.dist + 1,
            cost: self.dist + 1 + Self::board_cost(board),
            pos,
        }
    }

    fn board_cost(board: Board) -> u32 {
        (0..6)
            .filter(|i| board[*i] > 0)
            .map(|i| (i as u32).abs_diff(board[i] as u32 - 1))
            .sum()
    }
}

impl PartialEq for State {
    fn eq(&self, other: &Self) -> bool {
        self.cost == other.cost
    }
}

impl Ord for State {
    fn cmp(&self, other: &Self) -> Ordering {
        other.cost.cmp(&self.cost)
    }
}

impl PartialOrd for State {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

struct Solution {}

impl Solution {
    fn push_swap(
        queue: &mut BinaryHeap<State>,
        distmap: &mut HashMap<Board, u32>,
        state: &State,
        pos: u8,
    ) {
        let nstate = state.swap(pos);
        match distmap.entry(nstate.board) {
            hash_map::Entry::Occupied(mut entry) => {
                let prev_dist = entry.get_mut();
                if nstate.dist < *prev_dist {
                    *prev_dist = nstate.dist;
                    queue.push(nstate);
                }
            }
            hash_map::Entry::Vacant(entry) => {
                entry.insert(nstate.dist);
                queue.push(nstate);
            }
        };
    }

    pub fn sliding_puzzle(board: Vec<Vec<i32>>) -> i32 {
        let board: Board = (0..6)
            .map(|i| board[i / 3][i % 3] as u8)
            .collect::<Vec<_>>()
            .try_into()
            .unwrap();
        let pos = board.iter().enumerate().find(|(_, v)| **v == 0).unwrap().0 as u8;
        let mut queue = BinaryHeap::new();
        let mut distmap = HashMap::new();
        queue.push(State::new(board, pos));
        while let Some(state) = queue.pop() {
            if state.board == FINAL {
                return state.dist as i32;
            }
            Self::push_swap(&mut queue, &mut distmap, &state, (state.pos + 3) % 6);
            if (state.pos % 3) > 0 {
                Self::push_swap(&mut queue, &mut distmap, &state, state.pos - 1);
            }
            if (state.pos % 3) < 2 {
                Self::push_swap(&mut queue, &mut distmap, &state, state.pos + 1);
            }
        }
        -1
    }
}

pub fn main() {
    println!("{}", Solution::sliding_puzzle(arg_into(1)));
}

#[cfg(test)]
mod tests {
    use crate::Solution;
    use leetcode::vvi;

    #[test]
    fn test() {
        assert_eq!(Solution::sliding_puzzle(vvi("[[1,2,3],[4,0,5]]")), 1);
        assert_eq!(Solution::sliding_puzzle(vvi("[[1,2,3],[5,4,0]]")), -1);
        assert_eq!(Solution::sliding_puzzle(vvi("[[4,1,2],[5,0,3]]")), 5);
    }
}