Return to Question

This is a Leetcode problem -

Here is my solution to this challenge -

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 -

Here are the times taken for each output -

Here is my Leetcode result (32 test cases) -

So, I would like to know whether I could make my program shorter and more efficient.

Any help would be highly appreciated.

This is a Leetcode problem:

Here is my solution to this challenge:

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:

Here are the times taken for each output:

Here is my Leetcode result (32 test cases):

So, I would like to know whether I could make my program shorter and more efficient.

Explanation - Convert the board to a list so that we can have a visit set to track what 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 we have the graph and we just need to do a regular BFS.

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.

from collections import deque
       
class Solution:
        
    def get_new_state(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(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

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