c# solution - broken down into sections
public static int NumSteps(List<List> initPos)
{
int level = 0;
string target = “123450”;
String first = null;
Queue q = new Queue();
HashSet visited = new HashSet();
//convert the initial board into a string
for(int i = 0; i<initPos.Count; i++){
for(int j=0; j<initPos[0].Count; j++){
first += initPos[i][j].ToString();
}
}
q.Enqueue(first);
visited.Add(first);
while (q.Count>0) {
int n = q.Count;
for(int i=0; i < n; i++) {
string current = q.Dequeue();
if (current == target) {
return level;
}
//find the next nodes
List<string> nextBoards = GetNextBoards(current);
foreach (string board in nextBoards){
if (!visited.Contains(board)){
q.Enqueue(board);
visited.Add(board);
}
}
}
level++;
}
return -1;
}
public static List<string> GetNextBoards(string s) {
List<string> nextBoards = new List<string>();
// find pos of zero
int posOfZero = FindPosOfZero(s);
int[][] PossibleZeroPositions = new int[][] {new int[]{1, 3}, new int[]{0, 2, 4},
new int[]{1, 5}, new int[]{0, 4},
new int[]{3, 1, 5}, new int[]{2, 4}} ;
int[] nextPositions = PossibleZeroPositions[posOfZero];
foreach (int index in nextPositions) {
//swap chars at posOfZero and next position
string nextBoard = swap(s, posOfZero, index);
nextBoards.Add(nextBoard);
}
return nextBoards;
}
public static string swap(string s, int pos1, int pos2){
char[] charArray = s.ToCharArray();
charArray[pos1] = s[pos2];
charArray[pos2] = s[pos1];
return new String(charArray);
}
public static int FindPosOfZero(string s){
for (int i=0; i<s.Length; i++){
if (s[i] == '0')
return i;
}
return -1;
}
FYI - A solution that follows the template:
from typing import List
from collections import deque
import copy
def num_steps(init_pos: List[List[int]]) -> int:
# WRITE YOUR BRILLIANT CODE HERE
delta_r = [-1, 0, 1, 0]
delta_c = [0, 1, 0, -1]
target = [
[1, 2, 3],
[4, 5, 0]
]
if init_pos == target:
return 0
def get_nbs(current):
res = []
rs, cs = 2, 3
pr, pc = 0, 0
for i in range(rs):
for j in range(cs):
if current[i][j] == 0:
pr, pc = i, j
break
for i in range(4):
src_r, src_c = pr + delta_r[i], pc + delta_c[i]
if 0 <= src_r < rs and 0 <= src_c < cs:
candidate = copy.deepcopy(current)
v = candidate[src_r][src_c]
candidate[src_r][src_c] = 0
candidate[pr][pc] = v
res.append(candidate)
return res
def get_key(pos):
rs1 = [str(i) for i in pos[0]]
rs2 = [str(i) for i in pos[1]]
rs1.extend(rs2)
return "".join(rs1)
q = deque([init_pos])
step_tracker = {get_key(init_pos): 0}
while q:
for _ in range(len(q)):
pre = q.popleft()
pre_key = get_key(pre)
for nb in get_nbs(pre):
nb_key = get_key(nb)
if nb_key not in step_tracker:
step_tracker[nb_key] = step_tracker[pre_key] + 1
if nb == target:
return step_tracker[nb_key]
q.append(nb)
return -1
A simpler alternative for serialize/deserialize functions:
const serialize = position => position.toString();
const deserialize = (string) => {
const [a, b, c, d, e, f] = string.split(“,”).map(Number);
return [
[a, b, c],
[d, e, f]
];
};
A simpler alternative for serialize/deserialize functions:
const serialize = position => position.toString();
const deserialize = (string) => { const [a, b, c, d, e, f] = string.split(“,”).map(Number); return [ [a, b, c], [d, e, f] ]; };
Getting two testcases as time limit exceeded. What can be improved in the below code:
from typing import List
import copy
from collections import deque
def num_steps(init_pos: List[List[int]]) → int:
# WRITE YOUR BRILLIANT CODE HERE
target = [[1,2,3],[4,5,0]]
neighbours = {}
def get_neighbors(node):
node_tuple = tuple(tuple(line) for line in node)
if node_tuple in neighbours:
return neighbours[node_tuple]
res = []
row,col = 0,0
for i,list in enumerate(node):
for j,neighbour in enumerate(list):
if node[i][j] == 0:
row,col = i,j
delta_row = [-1,0,1,0]
delta_col = [0,1,0,-1]
for i in range(len(delta_row)):
row_new = row + delta_row[i]
col_new = col + delta_col[i]
if 0<=row_new<len(node) and 0<=col_new<len(node[0]):
node[row_new][col_new],node[row][col] = node[row][col],node[row_new][col_new]
res.append(copy.deepcopy(node))
node[row_new][col_new],node[row][col] = node[row][col],node[row_new][col_new]
node_tuple = tuple(tuple(line) for line in node)
neighbours[node_tuple] = res
return res
def bfs():
queue = deque([init_pos])
level = 0
if init_pos == target:
return level
while len(queue)>0:
n = len(queue)
level+=1
for _ in range(n):
node = queue.popleft()
for neighbor in get_neighbors(node):
if neighbor == target:
return level
queue.append(neighbor)
return 0
return bfs()
Found out my mistake:
Didnt maintain visited set tracker :
from typing import List
import copy
from collections import deque
def num_steps(init_pos: List[List[int]]) → int:
# WRITE YOUR BRILLIANT CODE HERE
target = [[1,2,3],[4,5,0]]
neighbours = {}
def get_neighbors(node):
node_tuple = tuple(tuple(line) for line in node)
if node_tuple in neighbours:
return neighbours[node_tuple]
res = []
row,col = 0,0
for i,list in enumerate(node):
for j,neighbour in enumerate(list):
if node[i][j] == 0:
row,col = i,j
delta_row = [-1,0,1,0]
delta_col = [0,1,0,-1]
for i in range(len(delta_row)):
row_new = row + delta_row[i]
col_new = col + delta_col[i]
if 0<=row_new<len(node) and 0<=col_new<len(node[0]):
node[row_new][col_new],node[row][col] = node[row][col],node[row_new][col_new]
res.append(copy.deepcopy(node))
node[row_new][col_new],node[row][col] = node[row][col],node[row_new][col_new]
node_tuple = tuple(tuple(line) for line in node)
neighbours[node_tuple] = res
return res
def bfs():
queue = deque([init_pos])
node_tuple = tuple(tuple(line) for line in init_pos)
visited = set([node_tuple])
level = 0
if init_pos == target:
return level
while len(queue)>0:
n = len(queue)
level+=1
for _ in range(n):
node = queue.popleft()
for neighbor in get_neighbors(node):
node_tuple = tuple(tuple(line) for line in neighbor)
if node_tuple in visited:
continue
if neighbor == target:
return level
queue.append(neighbor)
visited.add(node_tuple)
return -1
return bfs()
Here is my python solution. I decided to use the List of lists instead of converting it to a tuple. For the set, I had a stringify_matrix function.
from typing import List
from collections import deque
def get_next_possible_swaps(curr_pos: List[List[int]], r: int, c: int):
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
possible_swaps = []
for direction in directions:
new_r = r + direction[0]
new_c = c + direction[1]
# if you try to simply set a temporary variable like below:
# new_pos = curr_pos
# then, BFS will not work you must get a new copy of curr_pos and
# assign it to new_pos like so
# new_pos = list(list(line) for line in curr_pos)
new_pos = list(list(line) for line in curr_pos)
if 0 <= new_r < len(curr_pos) and 0 <= new_c < len(curr_pos[0]):
new_pos[r][c], new_pos[new_r][new_c] = new_pos[new_r][new_c], new_pos[r][c]
possible_swaps.append(new_pos)
return possible_swaps
Time complexity O(m + n)
def stringify_matrix(matrix: List[List[int]]) → str:
ordered_nums = []
for r in range(len(matrix)):
for c in range(len(matrix[0])):
ordered_nums.append(str(matrix[r][c]))
return “”.join(ordered_nums)
Time complexity O(n!)
def num_steps(init_pos: List[List[int]]) → int:
target = [[1,2,3],[4,5,0]]
queue = deque([init_pos])
visited = set([stringify_matrix(init_pos)])
moves_required = 0
while len(queue) > 0:
n = len(queue)
for _ in range(n):
curr_pos = queue.popleft()
if curr_pos == target:
return moves_required
for r in range(len(curr_pos)):
for c in range(len(curr_pos[0])):
if curr_pos[r][c] == 0:
for swap in get_next_possible_swaps(curr_pos, r, c):
stringified_swap = stringify_matrix(swap)
if stringified_swap not in visited:
queue.append(swap)
visited.add(stringified_swap)
moves_required += 1
return -1
#
# Approach:
#
# 1- idetify the the posible moves of black cell (0)
# 2- Use (puzzle) matrix compression to represent
# the matrix as a string of numbers
# 3- to get neighbor, need to identify the location
# of 0 (which represent the black cell) in the
# string of numbers.Then calculate the row and col of that cell(0)
# 4- run bfs on the list of neighbor to get the smallest number
# to try/steps to get to the "123450"
from typing import List
from collections import deque
def num_steps(init_pos: List[List[int]]) → int:
# WRITE YOUR BRILLIANT CODE HERE
#
# Approach:
#
# 1- idetify the the posible moves of black cell (0)
# 2- Use (puzzle) matrix compression to represent
# the matrix as a string of numbers
# 3- to get neighbor, need to identify the location
# of 0 (which represent the black cell) in the
# string of numbers.Then calculate the row and col of that cell(0)
# 4- run bfs on the list of neighbor to get the smallest number
# to try/steps to get to the “123450”
row_nums = len(init_pos)
col_nums = len(init_pos[0])
start = "".join([str(i) for row in init_pos for i in row])
target = "".join([str(i) for i in range(1, row_nums*col_nums)] + ["0"])
def swap(cur, i, j):
buf = list(cur)
buf[i], buf[j] = buf[j], buf[i]
return "".join(buf)
def get_neighbor(cur):
delta_moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
i = cur.find("0")
row,col = int(i/col_nums), i%col_nums
for i, j in delta_moves:
yield row + i, col + j
def bfs(start):
num_steps = 0
q = deque()
q.append(start)
visited = set()
visited.add(start)
while(len(q) > 0):
q_size = len(q)
for _ in range(q_size):
cur = q.popleft()
if cur == target:
return num_steps
for neighbor in get_neighbor(cur):
r, c = neighbor
if r < 0 or r >= row_nums or c < 0 or c >= col_nums:
continue
i = cur.find("0")
nxt_pos = swap(cur, i, r*col_nums + c)
if nxt_pos in visited:
continue
q.append(nxt_pos)
visited.add(nxt_pos)
num_steps += 1
return -1
return(bfs(start))
public static int numSteps(List<List<Integer>> initPos) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < initPos.size(); i++) {
for (int j = 0; j < initPos.get(0).size(); j++) {
sb.append(initPos.get(i).get(j));
}
}
String initial = sb.toString();
return bfs(initial, initPos);
}
private static int bfs(String initial, List<List<Integer>> initPos) {
ArrayDeque<String> queue = new ArrayDeque<>();
Set<String> visited = new HashSet<>();
String target = "123450";
queue.add(initial);
visited.add(initial);
int steps = 0;
while (queue.size() > 0) {
int n = queue.size();
for (int i = 0; i < n; i++) {
String current = queue.poll();
if (current.equals(target))
return steps;
for (String neighbor : getNeighbors(current)) {
if (visited.contains(neighbor))
continue;
visited.add(neighbor);
queue.add(neighbor);
}
}
steps++;
}
return -1;
}
private static List<String> getNeighbors(String current) {
List<String> result = new ArrayList<>();
int[][] swapIdx = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
int zeroIdx = -1;
for (int i = 0; i < current.length(); i++) {
if (current.charAt(i) == '0') {
zeroIdx = i;
break;
}
}
int[] swapArr = swapIdx[zeroIdx];
for (int i = 0; i < swapArr.length; i++) {
int swapIndex = swapArr[i];
String zeroSwapped = current.substring(0, zeroIdx) + current.charAt(swapIndex) + current.substring(zeroIdx + 1);
String res = zeroSwapped.substring(0, swapIndex) + '0' + zeroSwapped.substring(swapIndex + 1);
result.add(res);
}
return result;
}Here is my solution, I only serialize the positions in order to store them in the unordered_set of the visited positions:
std::string serialize(std::vector<std::vector<int>> pos, int rows, int cols) {
std::string res;
for (int c = 0; c < cols; ++c) {
for (int r = 0; r < rows; ++r) {
res += std::to_string(pos[r][c]);
}
}
return res;
}
int num_steps(std::vector<std::vector<int>> init_pos) {
int delta_rows[] = { -1, 0, 1, 0 };
int delta_cols[] = { 0, 1, 0, -1 };
std::vector<std::vector<int>> win_pos { { 1, 2, 3 }, { 4, 5, 0 } };
if (init_pos == win_pos) return 0;
int rows = (int)init_pos.size();
int cols = (int)init_pos[0].size();
int steps = 1;
std::unordered_set<std::string> visited;
visited.emplace(serialize(init_pos, rows, cols));
std::queue<std::vector<std::vector<int>>> q;
q.push(init_pos);
while (q.size() > 0) {
int n = (int)q.size();
for (int i = 0; i < n; ++i) {
std::vector<std::vector<int>> pos = q.front();
int row;
int col;
for (int c = 0; c < cols; ++c) {
for (int r = 0; r < rows; ++r) {
if (pos[r][c] == 0) {
row = r;
col = c;
break;
}
}
}
for (int i = 0; i < 4; ++i) {
int n_row = row + delta_rows[i];
if (0 > n_row || n_row >= rows) continue;
int n_col = col + delta_cols[i];
if (0 > n_col || n_col >= cols) continue;
std::vector<std::vector<int>> n_pos = pos;
std::swap(n_pos[row][col], n_pos[n_row][n_col]);
std::string str_pos = serialize(n_pos, rows, cols);
if (visited.count(str_pos)) continue;
if (n_pos == win_pos) return steps;
visited.emplace(str_pos);
q.push(n_pos);
}
q.pop();
}
++steps;
}
return -1;
}
Why is complexity n!? For me it looks that at each step we can generate 3 potential moves, and we have as many such steps as there nodes in graph, so 3 * V, where V is number of nodes in graph. BTW I usually find complexity explanation lacking.
O(N!) because we ask the question, how many “boards” are we processing in the worst case? Say we have a 1x3 board e.g. ‘abc’, how many possible candidates can we process?
abc, acb, cba, cab, bac, bca or (3x1)! = 3•2•1 = 6
In theory you are processing in the worst case n! possible candidates of a board before coming to an answer. Note that there are no repetition so we process one configuration only once.
Why does the complexity not include the processing time for each node? Let’s say the total matrix size is n. Everytime we poll a node, we deserialize it [O(n)], we find the blank position [O(n)] and then get neighbours [O(1)]. Each node is visited, serialized and deserialized atmost one time. And in the worst case we can process O(n!) nodes - so shouldn’t the TC be O(n*n!) ?
you are right, we are updating it to include the serialization code
Can somebody please elaborate on the time and space complexity a bit? I am having a hard time computing them for the graph problems. I am having a hard time figuring out that the space complexity is O(n!). At a time, the queue only holds the adjacent states which differ by only 1 tile change position, which in our case can only be 3 at max since 0 can have 3 neighbors (or 2 which is again less than 3) only at a time. So the children for any particular state at max can be 3. If the puzzle is larger, then the 0 at max can have 4 neighbors (either top, bottom, left or right). So there will be 4 children for each state now. So if there are n tiles in the puzzle, at a time the queue will only hold a multiple of 4 number of states where each state is n in quantity because of the number of tiles. So space complexity should be O(4cn) where c is some constant which boils down to O(n). Please correct me if I am wrong.
Regarding the time complexity, why will there be n! nodes in the worst case?
Java Solution following the template:
public static int numSteps(List<List> initPos) {
String target = “123450”;
String start = “”;
for(int row=0;row<initPos.size();row++){
for(int col=0;col<initPos.get(row).size();col++){
start += initPos.get(row).get(col);
}
}
Set<String> visited = new HashSet<>();
ArrayDeque<String> queue = new ArrayDeque<>();
queue.add(start);
visited.add(start);
int steps = 0;
int[][] zeroDirections = {{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}};
while(!queue.isEmpty()){
int size = queue.size();
for(int i=0;i<size;i++){
String node = queue.poll();
if(node.equals(target)){
return steps;
}
int zeroIndex = node.indexOf('0');
for(int index: zeroDirections[zeroIndex]){
String current = swap(node, zeroIndex, index);
if(visited.contains(current)){
continue;
}
queue.add(current);
visited.add(current);
}
}
steps++;
}
return -1;
}
public static String swap(String word, int currIndex, int futureIndex){
StringBuilder sb = new StringBuilder(word);
char temp = word.charAt(futureIndex);
sb.setCharAt(futureIndex, '0');
sb.setCharAt(currIndex, temp);
return sb.toString();
}
I think the space complexity in this case revers to the moves map rather than the queue. Worst case we will have to store every combination in moves map (e.g. when there’s no solution). This scenario, where we have to store every combination, makes the worst-case space complexity O(N!).
To clarify further on why it’s N!, in our case there are 6 tiles (N = 6). (I’m including the empty space here because technically it moves and takes up space on the graph as well.) We’re told that some initial positions may have no solution. For these cases, we will have to look at every possible move to determine that there is no solution. Since every combination is possible in this game, and there are 6 tiles for 6 spaces, that means that there are 6 * 5 * 4 * 3 * 2 * 1 => N! combinations, and therefore N! moves to arrive at those combinations. We have to create tuples for each of those combinations, which takes O(N) time. Therefore we arrive at O(N! * N) time complexity.
Hope this helps!
Can anyone please explain to me, How BFS is finding shortest path(or tries).
As from solution it seems like we are trying to go to all directions.
An explanation would be very appreciable.
Thanks
My JavaScript solution
function numSteps(initPos) {
const targetState = "1,2,3,4,5,0";
const queue = [initPos];
const seen = new Set();
let numSteps = 0;
while (queue.length > 0) {
const n = queue.length;
for (let i = 0; i < n; i++) {
const state = queue.shift();
if (state.toString() === targetState) {
return numSteps;
}
const neighbors = getAdjacentStates(state);
for (const neighbor of neighbors) {
if (!seen.has(neighbor.toString())) {
queue.push(neighbor);
seen.add(neighbor.toString());
}
}
}
numSteps++;
}
return -1;
}
function getAdjacentStates(state) {
const M = state.length;
const N = state[0].length;
const EMPTY_SLOT_VALUE = 0;
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
const states = [];
for (let row = 0; row < M; row++) {
for (let col = 0; col < N; col++) {
for (const [dr, dc] of directions) {
if (row + dr >= 0
&& row + dr < M
&& col + dc >= 0
&& col + dc < N
&& state[row + dr][col + dc] === EMPTY_SLOT_VALUE) {
const newState = [...state.map(row => [...row])];
newState[row][col] = EMPTY_SLOT_VALUE;
newState[row + dr][col + dc] = state[row][col];
states.push(newState);
}
}
}
}
return states;
}