This is a Leetcode problem:
On a 2 x 3
board
, there are 5 tiles represented by the integers1
through5
and an empty square represented by0
.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 a puzzle 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
.Note -
board
will be a 2 x 3 array as described above.board[i][j]
will be a permutation of[0, 1, 2, 3, 4, 5]
.
Here is my solution to this challenge:
from collections import deque
class Solution:
def get_new_state(self, index1, index2, current_state):
if current_state[index1] == "0" or current_state[index2] == "0":
current_state = list(current_state)
current_state[index1], current_state[index2] = current_state[index2], current_state[index1]
return "".join(current_state)
return None
def sliding_puzzle(self, board):
"""
:type board: List[List[int]]
:rtype: int
"""
min_step = 1 << 31
# need to convert board to a string so that we can add it as a state in the set
# construct the graph based on the positions of the next place it can swap
graph = {0:[1, 3], 1:[0, 2, 4], 2:[1, 5], 3:[0, 4], 4:[1, 3, 5], 5:[2, 4]}
# convert init board to an initial state
init_state = [] + board[0] + board[1]
init_state = "".join(str(_) for _ in init_state)
visited = {init_state}
queue = deque([[init_state, 0]])
while queue:
top = queue.popleft()
current_state, step = top
# check results
if current_state == "123450":
min_step = min(min_step, step)
for index1 in graph:
for index2 in graph[index1]:
new_state = self.get_new_state(index1, index2, current_state)
if new_state is not None and new_state not in visited:
queue.append([new_state, step + 1])
visited.add(new_state)
if min_step == 1<< 31:
return -1
return min_step
Explanation
Convert the board
to a list so that we can have a visit
set to track which state is visited.
Construct an adjacency list to mark which position we can go to. For example, [[1, 2, 3], [4, 5, 0]]
, as it is a board
value, 1
can swap with 4
or 2
.
If we make it a string "123450"
, that means position 0
(so-called index) can swap with index value 0
and index value 3
=> 0:[1, 3]
, same for 1:[0, 2, 4]
for so on so forth.
Now that we have the graph, we just need to do a regular BFS.
Here are some example outputs:
#print(sliding_puzzle([[1,2,3],[4,0,5]]))
>>> 1
#Explanation: Swap the 0 and the 5 in one move.
#print(sliding_puzzle([[1,2,3],[5,4,0]]))
>>> -1
#Explanation: No number of moves will make the board solved.
#print(sliding_puzzle([[4,1,2],[5,0,3]]))
>>> 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]]
#print(sliding_puzzle([[3,2,4],[1,5,0]]))
>>> 14
Here are the times taken for each output:
%timeit output.sliding_puzzle([[1,2,3],[4,0,5]])
3.24 ms ± 629 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit output.sliding_puzzle([[1,2,3],[5,4,0]])
3.17 ms ± 633 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit output.sliding_puzzle([[4,1,2],[5,0,3]])
3.32 ms ± 719 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit output.sliding_puzzle([[3,2,4],[1,5,0]])
2.75 ms ± 131 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Here is my Leetcode result (32 test cases):
So, I would like to know whether I could make my program shorter and more efficient.