I solved the today's (November 25th 2024) leetcode question and it was a BFS solution, but then I wanted to try recursion on the code and due to O(V!) time complexity, there is no way this code will return anything untill the heat dead of the universe (Something like 720! lol)
Here is the question: https://leetcode.com/problems/sliding-puzzle/description/
Is there a website or way to see or watch like a debugger so I can understand if the code is working as intended (even though it will never compile) ?
Here is my recursion code:
from typing import List, Tuple
class Solution:
def slidingPuzzle(self, board: List[List[int]]) -> int:
def to_string(board: List[List[int]]) -> str:
"""Convert the 2x3 board into a string representation."""
return "".join(str(num) for row in board for num in row)
def swap(state: str, i: int, j: int) -> str:
"""Swap characters at index i and j in the string."""
state = list(state)
state[i], state[j] = state[j], state[i]
return "".join(state)
def dfs(state: str, depth: int) -> int:
if state == target:
return depth
if state in memo:
return float('inf') # State already visited
memo.add(state)
zero_idx = state.index('0')
min_moves = float('inf')
for neighbor in directions[zero_idx]:
new_state = swap(state, zero_idx, neighbor)
moves = dfs(new_state, depth + 1)
min_moves = min(min_moves, moves)
memo.remove(state) # Backtrack
return min_moves
# Target state
target = "123450"
# Convert the board to a string
start = to_string(board)
# Directions based on 2x3 board
directions = [
[1, 3], # Index 0
[0, 2, 4], # Index 1
[1, 5], # Index 2
[0, 4], # Index 3
[1, 3, 5], # Index 4
[2, 4] # Index 5
]
# Memoization to track visited states
memo = set()
# Perform DFS
result = dfs(start, 0)
return result if result != float('inf') else -1
And here is the BFS solution in O(V+E)
from typing import List
from collections import defaultdict, deque
class Solution:
def slidingPuzzle(self, board: List[List[int]]) -> int:
def swap(s: str, zero_idx: int, new_idx: int) -> str:
char_arr = list(s)
char_arr[zero_idx], char_arr[new_idx] = char_arr[new_idx], char_arr[zero_idx]
return "".join(char_arr)
target = "123450"
start = "".join(str(board[r][c]) for r in range(len(board)) for c in range(len(board[0])))
visited = set()
directions = [
[1, 3], # Neighbors for index 0
[0, 2, 4], # Neighbors for index 1
[1, 5], # Neighbors for index 2
[0, 4], # Neighbors for index 3
[1, 3, 5], # Neighbors for index 4
[2, 4] # Neighbors for index 5
]
queue = deque([start])
visited.add(start)
res = 0
while queue:
size = len(queue)
for _ in range(size):
curr = queue.popleft()
if curr == target:
return res
zero_idx = curr.index('0') # Find the index of '0'
for dir_idx in directions[zero_idx]: # Valid moves for the zero's position
swapped = swap(curr, zero_idx, dir_idx)
if swapped in visited:
continue
visited.add(swapped)
queue.append(swapped)
res += 1
return -1
I would start with a global variable dfs_calls = 0 and every time dsf() was called I would increment it.
Well, I would not technically do that, but it is the easiest thing to do to augment your code without changing signatures and whatnot
Then I would use a print inside your for loop that gave this value and the current depth for context.
dfs_calls = 0
def dfs(state: str, depth: int) -> int:
global dfs_calls
dfs_calls += 1
if state == target:
return depth
if state in memo:
return float('inf') # State already visited
memo.add(state)
zero_idx = state.index('0')
min_moves = float('inf')
print(f"{dfs_calls} current_depth: { '.' * (depth // 10) }{ ' ' * 10 }", end="\r", flush=True)
for neighbor in directions[zero_idx]:
new_state = swap(state, zero_idx, neighbor)
moves = dfs(new_state, depth + 1)
min_moves = min(min_moves, moves)
memo.remove(state) # Backtrack
return min_moves
Note that print() is very slow and will dramtically impact the performance here.