(Leetcode) Sliding puzzle in Python

Question

This is a Leetcode problem:

On a 2 x 3 board, there are 5 tiles represented by the integers 1 through 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 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.

Answer 1

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 3x3 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.