Sliding Puzzle - Graph / Implicit Graph

Problems
21

Isn’t the serialization and deserialization O(1) time complexity? We have a fixed size of 2x3, not a variable size of n.

Edit: since we have a fixed size, wouldn’t we also have a fixed number of combinations? So O(1) space and time complexity? I agree that if the number of tiles was variable, time complexity would be O(n * n!). If that were the case, wouldn’t space complexity also be O(n * n!)?

22 
def is_valid_hash(hashed_mat):
    return hashed_mat.startswith("123450")

def hash_mat(mat):
    def gen_mat():
        for y in range(2):
            for x in range(3):
                yield str(mat[y][x])
    return ''.join(gen_mat())

def get_neighbors(mat):
    empty_y, empty_x = next((y, x) for y in range(2) for x in range(3) if mat[y][x] == 0)
    for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        new_y, new_x = empty_y + dy, empty_x + dx
        if 0 <= new_y < 2 and 0 <= new_x < 3:
            rst_mat = deepcopy(mat)
            rst_mat[empty_y][empty_x], rst_mat[new_y][new_x] = rst_mat[new_y][new_x], rst_mat[empty_y][empty_x]
            yield rst_mat

def num_steps(init_pos: List[List[int]]) -> int:
    _mat = hash_mat(init_pos)
    if is_valid_hash(_mat): 
        return 0
    visited = set([_mat])
    queue = deque([deepcopy(init_pos)])
    steps = 0
    while queue:
        n = len(queue)
        for _ in range(n):
            mat = queue.popleft()
            for neighbor_mat in get_neighbors(mat):
                _mat = hash_mat(neighbor_mat)
                if _mat in visited:
                    continue
                if is_valid_hash(_mat):
                    return steps + 1
                visited.add(_mat)
                queue.append(neighbor_mat)
        steps += 1
    return -1
23

My clean solution.

from typing import List
from collections import deque 

class State:
    def __init__(self, pos, row=None, col=None):
        self.pos = pos
        self.row = row
        self.col = col
        
        if not row and not col:
            self.row, self.col = self.get_row_col(pos)
            
    def get_row_col(self, pos):
        for i in range(len(pos)):
            for j in range(len(pos[i])):
                if pos[i][j] == 0:
                    return (i, j)
    
    def __eq__(self, other):
        return self.pos == other.pos
    
    def __hash__(self):
        return hash(str(self.pos))
    
    def get_next_states(self):
        row_delta = [-1, 0, 1, 0]
        col_delta = [0, 1, 0, -1]

        result = []
        
        for i in range(len(row_delta)):

            row = self.row + row_delta[i]
            col = self.col + col_delta[i]

            if 0 <= row < len(self.pos) and 0 <= col < len(self.pos[0]):
                temp = [row_list[:] for row_list in self.pos] # deep copy 
                
                val = temp[row][col]
                temp[self.row][self.col] = val
                temp[row][col] = 0 
                
                state = State(temp, row, col)

                result.append(state)

        return result
    
    
def num_steps(init_pos: List[List[int]]) -> int:
    def bfs(): 
        init = State(init_pos)
        end_state = State([[1,2,3],[4,5,0]])
        q = deque([init])
        seen = set([init])
        steps = 0 
        while q:
            n = len(q)
            for _ in range(n):
                state = q.popleft()
                if state == end_state:
                    return steps
                next_states = state.get_next_states()
                for next_state in next_states:
                    if next_state in seen:
                        continue
                    seen.add(next_state)
                    q.append(next_state)
            steps += 1    
        return -1
    return bfs()