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!)?
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
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()
Structured for clarity and two optimizations - caching the position of the zero cell so we don’t need to traverse to find it (except the initial state), and no need for a map, just a set using a simple string serialization of the state.
Complexity is O(n + n!) whereas the provided solution is actually O(3n * n!) due to zero-finding traversal and deserialization, which my solution doesn’t require.
from typing import List
from collections import deque
import copy
def num_steps(init_pos: List[List[int]]) -> int:
dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
target = [[1,2,3],[4,5,0]]
if init_pos == target:
return 0
def get_neighbors(r, c):
for dr, dc in dirs:
r1, c1 = r+dr, c+dc
if 0 <= r1 < len(init_pos) and 0 <= c1 < len(init_pos[0]):
yield r1, c1
def forward(state_, o_r, o_c, t_r, t_c):
next_state = copy.deepcopy(state_)
next_state[o_r][o_c] = state[t_r][t_c]
next_state[t_r][t_c] = 0
return next_state
# find the starting open slot
start_open = (0, 0)
for i in range(len(init_pos)):
for j in range(len(init_pos[0])):
if init_pos[i][j] == 0:
start_open = (i, j)
queue = deque([(init_pos, start_open, 0)])
states : set[str] = set()
while queue:
state, zero_pos, distance = queue.popleft()
z_r, z_c = zero_pos
for r1, c1 in get_neighbors(z_r, z_c):
next_state = forward(state,
z_r, z_c,
r1, c1)
if next_state == target:
return distance + 1
state_repr = str(next_state)
if state_repr in states:
continue
states.add(state_repr)
# we already know what the position of the new zero is,
# since it was the tile we moved to get to the new state.
# putting in the queue alongside the state to avoid recalculating it
queue.append((next_state, (r1, c1), distance + 1))
return -1