iâm interested if we need a bfs_map at all. i feel that we can just use regular visited set() and then to keep track of how many steps use a steps/level variable that is either kept in the queue as a tuple (step, combo_number) or just is a variable incremented after exploring the entire queueâs current nodes. i feel that might be more in line with previous solutions, but an explanation of why you do this would be interesting! i was just most confused why you would do bfs_map[top] + 1 because using a hashmap implies that we might need to quickly look up the steps for this specific combo once again? but we only ever each combo once right :o
We can start regular BFS with visited initialized to trapped_combos and â0000â. For this problem, we need to avoid trapped_combos, since we already avoid visited, we can combine into one.
We can simplify the logic for ârotatingâ to single function, with +1 and -1 offsets. Neighbors will be forward_combos + backward_combos.
The solution is definitely not neatâŚ
Made your proposed alternate solution below. Itâs a modified version of this submission on LC, edited for readability: https://leetcode.com/problems/open-the-lock/discuss/110232/Accepted-PythonJava-BFS-%2B-how-to-avoid-TLE
from typing import List
from collections import deque
def num_steps(combo: str, trapped_combos: List[str]) â int:
# we can solve the problem of integer rollover
# by using the % operator with 10.
def get_next_combos(src):
res = []
for i, digit in enumerate(src):
num = int(digit)
res.append(src[:i] + str((num - 1) % 10) + src[i+1:])
res.append(src[:i] + str((num + 1) % 10) + src[i+1:])
return res
visited, queue = set(trapped_combos), deque(['0000'])
depth = -1
while queue:
size = len(queue)
depth += 1
for _ in range(size):
cur_combo = queue.popleft()
if cur_combo == combo:
return depth
if cur_combo in visited:
continue
visited.add(cur_combo)
queue.extend(get_next_combos(cur_combo))
return -1
Where did you get 10^4 as the time complexity?
// Implementation in Javascript
function numSteps(combo, trappedCombos) {
function getNeighbors(combo) {
let a = combo.split(ââ).map(x => parseInt(x, 10));
let res = [];
let delta = [1,-1];
for (let i=0; i<4; i++) {
for (let j=0; j<delta.length; j++) {
let temp = a[i];
a[i] = (a[i] + delta[j] + 10)%10;
if (!trappedCombos.includes(a.join(ââ))) res.push(a.join(ââ));
a[i]=temp; // Resetting the value;
}
}
return res;
}
let visited = new Set(['0000']);
let queue = ['0000'];
let steps = -1;
while (queue.length) {
steps++;
let n = queue.length;
for (let i=0; i<n; i++) {
let node = queue.shift();
if (node === combo) return steps;
for (let x of getNeighbors(node)) {
if (visited.has(x)) continue;
visited.add(x);
queue.push(x);
}
}
}
return -1;
}
Yo, I am amazed by the bfs_map part in the solution.
I initially come up with a solution that use BFS with kind of a level order search (8 states per level) and keep a variable steps = 0 and increase by 1 for every level. I got all answers correct except test case 3 which was time limit exceeded. After I change my visited set to a visited dictionary (bfs_map in the solution) I passed test case 3.
Can someone explain to me why doing addition of steps for every state and save the results in a hashmap is faster than I just keep a variable and do the addition of steps per level? I know taking a value from hashmap cost O(1) time but it seems to me that there are much more work to be done compare to just keeping a step variable.
FYI - I followed the âgetting neighborsâ pattern to keep the coding style consistent with previous questions
# WRITE YOUR BRILLIANT CODE HERE
def get_nbs(comb: str):
res = []
for i in range(4):
k = int(comb[i])
k += 1
if k > 9:
k = 0
s = comb[0:i] + str(k) + comb[i+1:]
res.append(s)
k = int(comb[i])
k -= 1
if k < 0:
k = 9
s = comb[0:i] + str(k) + comb[i+1:]
res.append(s)
#print(f"nbs of {comb}: {res}")
return res
q = deque(["0000"])
steps_map = {"0000": 0}
trapped_combos_set = set(trapped_combos)
while len(q) > 0:
qlen = len(q)
for _ in range(qlen):
prev = q.popleft()
for nb in get_nbs(prev):
if nb not in trapped_combos_set and nb not in steps_map:
q.append(nb)
steps_map[nb] = steps_map[prev] + 1
if nb == combo:
return steps_map[nb]
return -1
How come algomonster throws an error when trying to pass a string to the funtion below? Running this in an ipython console works as intended with no errors whatsoever.
def get_neighbors(combo):
res = []
for i in range(4):
k = int(combo[i])
if k + 1 > 9:
s1 = combo[0:i] + '0' + combo[i + 1:]
else:
s1 = combo[0:i] + str(k + 1) + combo[i + 1:]
res.append(s1)
if k - 1 < 0:
s2 = combo[0:i] + '9' + combo[i + 1:]
else:
s2 = combo[0:i] + str(k - 1) + combo[i + 1:]
res.append(s2)
return res
The error is below:
Traceback (most recent call last):
File "solution.py", line 44, in <module>
res = num_steps(combo, trapped_combos)
File "solution.py", line 31, in num_steps
for neighbor in get_neighbors(node):
File "solution.py", line 13, in get_neighbors
s1 = combo[0:i] + '0' + combo[i + 1:]
TypeError: can only concatenate list (not "str") to list
Iâd also like to know this. It doesnât seem to make sense.
My solution without a dictionary
WRITE YOUR BRILLIANT CODE HERE
def get_neighbors(num):
res = []
for i in range(4):
next_digit = int(num[i]) + 1
if next_digit > 9:
next_digit = 0
prev_digit = int(num[i]) - 1
if prev_digit < 0:
prev_digit = 9
next_num = num[:i] + str(next_digit) + num[i+1:]
prev_num = num[:i] + str(prev_digit) + num[i+1:]
res.append(str(prev_num))
res.append(str(next_num))
return res
if combo == "0000":
return 0
q = deque(["0000"])
trap_set = set(trapped_combos)
visited = set(["0000"])
tests = 0
while q:
for _ in range(len(q)):
test_combo = q.popleft()
if combo == test_combo:
return tests
for nbr in get_neighbors(test_combo):
if nbr in visited or nbr in trap_set:
continue
visited.add(nbr)
q.append(nbr)
tests += 1
return -1
Solution that I found to be more readable:
def rotate(combo, index, amount):
copy = [int(x) for x in combo]
digit = copy[index] + amount
if digit > 9:
copy[index] = 0
elif digit < 0:
copy[index] = 9
else:
copy[index] = digit
return ââ.join([str(x) for x in copy])
def num_steps(target: str, traps: List[str]) â int:
q = deque([â0000â])
visited = {}
steps = 0
while len(q) > 0:
n = len(q)
for _ in range(n):
current = q.popleft()
if current in visited:
continue
visited[current] = True
if current in traps:
continue
if current == target:
return steps
for rotate_index in range(4):
q.append(rotate(current, rotate_index, 1))
q.append(rotate(current, rotate_index, -1))
steps += 1
return -1
why do we keep track of steps for each combo in a dictionary? wouldnât increasing âstepâ variable after each âlevelâ be simpler and more memory efficient? In the end we are interested only in the minimum number of steps for a single combination? \
moreover, we could initialise âvisitedâ set with prohibited combinations and have a single check: new_combo in visited instead of splitting it for already vistited and prohibited combos \
My solution: \
def num_steps(target_combo: str, trapped_combos: List[str]) â int:
def get_neighbours(combo):
for i in range(4):
yield combo[0:i] + str((int(combo[i]) + 1) % 10) + combo[i+1:]
yield combo[0:i] + str((int(combo[i]) - 1) % 10) + combo[i+1:]
seed = "0000"
visited = set(trapped_combos)
visited.add(seed)
q = deque([seed])
steps = 0
while len(q) > 0:
for _ in range(len(q)):
combo = q.popleft()
if combo == target_combo:
return steps
for n in get_neighbours(combo):
if n in visited:
continue
visited.add(n)
q.append(n)
steps += 1
return -1
mine implementation (comment above) using a visited set and steps update after each level passes all tests
Why do we need to turn the trapped_combos into a set? canât we just leave it as a list, since weâre only checking if a combo is in it?
OH its because, to check the existence of an item in a SET can be done in O(1) time whereas in a LIST its O(n)
from typing import List
from collections import deque
def num_steps(target_combo: str, trapped_combos: List[str]) â int:
# WRITE YOUR BRILLIANT CODE HERE
# 1- each code have 8 neighber (4 forward and 4 backworld)
# 2- get_neighbor from each case above
# 3- bfs to determine the min number of digit change to unlock
# need to parse all element in the bfsâqueue to process
# entire level inoredr to increment the steps by 1
def get_neighbor(combo):
for i in range(4):
yield combo[0:i] + str((int(combo[i]) + 1) % 10) + combo[i+1:]
yield combo[0:i] + str((int(combo[i]) - 1) % 10) + combo[i+1:]
def bfs(target_combo, trapped_combos):
visited = set(trapped_combos)
start = "0000"
visited.add(start)
Try_nums = 0
q = deque([start])
while len(q):
for _ in range(len(q)):
combo = q.popleft()
if combo == target_combo:
return Try_nums
for nieghbor in get_neighbor(combo):
if nieghbor in visited:
continue
q.append(nieghbor)
visited.add(nieghbor)
Try_nums += 1
# Can't open it without triggering the trap
return -1
return bfs(target_combo, trapped_combos)
Can someone help please:
I just realized that when I finish a problem and click on the âMark as Completedâ button. My code/my Solution it disrepair from âTry it yourselfâ Does any one facing this? and I can we recover our solution that we did for previous exercises ?
Thank you