commit da97a56d57cdfe9a19649f7bab08aaa99b9adfb5
parent 4caa3fd7f94d692b27db51e91283620eab31e31b
Author: Louis Burda <quent.burda@gmail.com>
Date: Mon, 25 Nov 2024 05:31:31 +0100
Add problem 773
Diffstat:
2 files changed, 180 insertions(+), 0 deletions(-)
diff --git a/Cargo.toml b/Cargo.toml
@@ -36,6 +36,10 @@ name = "2601"
path = "src/bin/2601-prime-subtraction-operation.rs"
[[bin]]
+name = "773"
+path = "src/bin/0773-sliding-puzzle.rs"
+
+[[bin]]
name = "2257"
path = "src/bin/2257-count-unguarded-cells-in-the-grid.rs"
diff --git a/src/bin/0773-sliding-puzzle.rs b/src/bin/0773-sliding-puzzle.rs
@@ -0,0 +1,176 @@
+/// 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);
+ }
+}
