Problem
This is a Leetcode problem:
On a 2 x 3
board, there are 5 tiles represented by the integers1
through5and an empty square represented by0.A move consists of choosing
0and a 4-directionally adjacent number
and swapping it.The state of the board is solved
if and only if the
boardis
[[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 –
boardwill 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.
Solution
Many great ideas here:
- using a hashable data structure to be able to store it in a set
- using a dequeue to generate the various possible states
- storing the neighboors in a dictionnary
However, various points can be improved.
Initialisation of the board
Having 2 consecutive assignments to init_state makes things more complicated than needed.
Starting with “[] + ” is not required.
Using _ as a variable name is pretty common but it usually corresponds to a value that is not going to be used. In your case, I’d use a more normal name.
Thus, I’d recommend:
init_state = "".join(str(c) for c in board[0] + board[1])
Stopping as soon as possible
Because of the way the queue is built, elements with be in increasing order regarding the step element. One of the implication is that once we’ve found a solution, there is no need to continue, no solution will ever be better. You can return at that point. That also removes the need for a special value corresponding to “no solution found so far”.
def sliding_puzzle(board):
"""
:type board: List[List[int]]
:rtype: int
"""
# 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 = "".join(str(c) for c in board[0] + board[1])
visited = {init_state}
queue = deque([[init_state, 0]])
while queue:
top = queue.popleft()
current_state, step = top
# check results
if current_state == "123450":
return step
for index1 in graph:
for index2 in graph[index1]:
new_state = 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)
return -1
This makes the code way faster : twice faster on my machine on the test cases provided, more than twice on a more comprehensive test suite:
def find_new_tests():
import random
board = "123450"
values_found = {}
for i in range(1000):
board_lst = list(board)
random.shuffle(board_lst)
ret = sliding_puzzle([board_lst[0:3], board_lst[3:]])
if ret not in values_found:
values_found[ret] = ''.join(board_lst)
print(values_found)
start = time.time()
for i in range(10):
# Provided in the question
assert sliding_puzzle([[1,2,3],[4,0,5]]) == 1
assert sliding_puzzle([[1,2,3],[5,4,0]]) == -1
assert sliding_puzzle([[4,1,2],[5,0,3]]) == 5
assert sliding_puzzle([[3,2,4],[1,5,0]]) == 14
# Found randomly
assert sliding_puzzle([[1,2,0],[4,5,3]]) == 1
assert sliding_puzzle([[1,2,3],[0,4,5]]) == 2
assert sliding_puzzle([[1,3,0],[4,2,5]]) == 3
assert sliding_puzzle([[1,5,2],[0,4,3]]) == 4
assert sliding_puzzle([[4,1,3],[2,0,5]]) == 5
assert sliding_puzzle([[4,1,2],[5,3,0]]) == 6
assert sliding_puzzle([[2,3,5],[1,0,4]]) == 7
assert sliding_puzzle([[5,2,3],[1,4,0]]) == 8
assert sliding_puzzle([[4,2,3],[5,0,1]]) == 9
assert sliding_puzzle([[5,0,3],[1,2,4]]) == 10
assert sliding_puzzle([[1,2,5],[3,0,4]]) == 11
assert sliding_puzzle([[4,0,1],[3,2,5]]) == 12
assert sliding_puzzle([[3,1,0],[4,5,2]]) == 13
assert sliding_puzzle([[1,4,3],[5,2,0]]) == 14
assert sliding_puzzle([[0,1,3],[2,5,4]]) == 15
assert sliding_puzzle([[5,1,3],[0,4,2]]) == 16
assert sliding_puzzle([[1,3,0],[5,4,2]]) == 17
assert sliding_puzzle([[2,0,1],[3,5,4]]) == 18
assert sliding_puzzle([[0,2,1],[3,5,4]]) == 19
assert sliding_puzzle([[3,2,1],[0,5,4]]) == 20
assert sliding_puzzle([[4,2,3],[0,1,5]]) == -1
print(time.time() - start)
Finding the sliding pieces
At the moment, to generate new state, you try each cell and for each cell, each neighboor then eventually you check than one or the other is empty.
You just need to find the empty cell and consider its neighboor.
This makes the code almost 3 times faster (and 7 times faster than the original code) and more concise:
def get_new_state(index1, index2, current_state):
current_state = list(current_state)
current_state[index1], current_state[index2] = current_state[index2], current_state[index1]
return "".join(current_state)
def sliding_puzzle(board):
"""
:type board: List[List[int]]
:rtype: int
"""
# 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 = "".join(str(c) for c in board[0] + board[1])
visited = {init_state}
queue = deque([[init_state, 0]])
while queue:
current_state, step = queue.popleft()
# check results
if current_state == "123450":
return step
empty = current_state.find("0")
for candidate in graph[empty]:
new_state = get_new_state(empty, candidate, current_state)
if new_state not in visited:
queue.append([new_state, step + 1])
visited.add(new_state)
return -1
Other optimisation ideas
When pieces on the left border are in place, there is no need to move them anymore.
(On a 3×3 board, this would apply also to the top/bottom borders).
Thus, we can reduce the search space by not trying to move them in these cases. I did not find any noticeable improvement by doing so:
pieces_to_keep = set()
if current_state[0] == "1" and current_state[3] == "4":
pieces_to_keep.add(0)
pieces_to_keep.add(3)
empty = current_state.find("0")
for candidate in graph[empty]:
if candidate not in pieces_to_keep:
new_state = get_new_state(empty, candidate, current_state)
if new_state not in visited:
queue.append((new_state, step + 1))
visited.add(new_state)
Micro optimisation
We could try to save a bit of time by avoiding calling the get_new_state function and inlining the corresponding code.
for candidate in graph[empty]:
tmp_state = list(current_state)
tmp_state[empty], tmp_state[candidate] = tmp_state[candidate], "0"
new_state = ''.join(tmp_state)
if new_state not in visited:
queue.append((new_state, step + 1))
visited.add(new_state)
This leads to a significant improvement in performances.
More extreme caching
We can easily notice two interesting points:
-
there are not so many reachable positions (360)
-
when looking for a non reachable position, we have to generate all reachable position.
This leads to an idea: we may as well compute all the positions and the number of steps required once and for all. This is an expensive initialisation step but as soon as we look for a single non reachable position, it is worth it. The more requests we perform, the more amortised the upfront operations are as each request takes a constant time.
Corresponding code is:
from collections import deque
def generate_cache():
graph = {0:[1, 3], 1:[0, 2, 4], 2:[1, 5], 3:[0, 4], 4:[1, 3, 5], 5:[2, 4]}
init_state = '123450'
results = {init_state: 0}
queue = deque([[init_state, 0]])
while queue:
current_state, step = queue.popleft()
empty = current_state.find("0")
for candidate in graph[empty]:
tmp_state = list(current_state)
tmp_state[empty], tmp_state[candidate] = tmp_state[candidate], "0"
new_state = ''.join(tmp_state)
if new_state not in results:
queue.append((new_state, step + 1))
results[new_state] = step + 1
return results
cache = generate_cache()
def sliding_puzzle(board):
"""
:type board: List[List[int]]
:rtype: int
"""
init_state = "".join(str(c) for c in board[0] + board[1])
return cache.get(init_state, -1)
This got me:
Runtime: 32 ms, faster than 100.00% of Python3 online submissions for Sliding Puzzle.
Memory Usage: 13.3 MB, less than 15.86% of Python3 online submissions for Sliding Puzzle.
Hardcoded cache
This would probably be a right place to stop but for some reason, after a few days, I got a bit curious of the performance gain we’d have by having the cache hardcoded:
Runtime: 32 ms, faster than 100.00% of Python3 online submissions for Sliding Puzzle.
Memory Usage: 13.1 MB, less than 80.58% of Python3 online submissions for Sliding Puzzle.
I must confess that I am a bit disappointed.
Additional note: at this level of details, resubmitting the same solution can lead to different performances.