Open the Lock - Graph / Implicit Graph

Problems
25

Simple C++ implementation:

using namespace std;

vector<string> getNeighbours(string combo) {
    vector<string> neighbours;
    
    for(int i = 0; i < combo.size(); i++) {
        int ival = (combo[i] - '0');
        string next = combo.substr(0, i) + to_string((ival + 1 + 10) % 10) + combo.substr(i+1);
        string prev = combo.substr(0, i) + to_string((ival - 1 + 10) % 10) + combo.substr(i+1);
        neighbours.push_back(next);
        neighbours.push_back(prev);
    }
    return neighbours;
}

int num_steps(std::string target_combo, std::vector<std::string> trapped_combos) {
    // WRITE YOUR BRILLIANT CODE HERE
    unordered_map<string, bool> visited;
    unordered_map<string, bool> trapMap;
    
    for(auto trap: trapped_combos) {
        trapMap[trap] = true;
    }
    
    queue<string> q;
    q.push("0000");
    visited["0000"] = true;
    int count = 0;
    
    while(!q.empty()) {
        int n = q.size();
        for(int i = 0; i < n; i++) {
            string newCombo = q.front();
            q.pop();
            if(newCombo == target_combo) return count;
            vector<string> neighbours = getNeighbours(newCombo);
            for(auto next: neighbours) {
                if(!visited[next] && !trapMap[next]) {
                    q.push(next);
                    visited[next] = true;
                }
            }
        }
        count++;
    }
    
    return -1;
}
26

Yours is the same as mine

27 
if target_combo == "0000":
     return 0

steps = 0
queue = ["0000"]
visited = set()
visited.add("0000")

while queue:
    n = len(queue)
    steps += 1
    for _ in range(n):
        node = queue.pop(0)
        neighbors = get_neighbors(node)
        for neighbor in neighbors:
            if neighbor == target_combo:
                return steps

            if neighbor not in trapped_combos and neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

return -1

def get_neighbors(num):
# numbers at distance 1
neighbors = []
for pos in range(4):
digit = int(num[pos])

    changed_num = digit + 1 if digit < 9 else 0
    new_num = num[:pos] + str(changed_num) + num[pos+1:]
    neighbors.append(new_num)
    
    changed_num = digit - 1 if digit > 0 else 9
    new_num = num[:pos] + str(changed_num) + num[pos+1:]
    neighbors.append(new_num)
 
return neighbors
28 
public static Map<Character, Character> nextDigit = Map.of(
        '0', '1',
        '1', '2',
        '2', '3',
        '3', '4',
        '4', '5',
        '5', '6',
        '6', '7',
        '7', '8',
        '8', '9',
        '9', '0'
    );
    public static Map<Character, Character> prevDigit = Map.of(
        '0', '9',
        '1', '0',
        '2', '1',
        '3', '2',
        '4', '3',
        '5', '4',
        '6', '5',
        '7', '6',
        '8', '7',
        '9', '8'
    );
    public static int numSteps(String targetCombo, List<String> trappedCombos) {
        String start = "0000";
        return bfs(start, targetCombo, trappedCombos);
    }
    
    private static int bfs(String start, String targetCombo, List<String> trappedCombos) {
        ArrayDeque<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        
        queue.add(start);
        visited.addAll(trappedCombos);
        visited.add(start);
        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(targetCombo))
                    return steps;
                for (String neighbor : getNeighbors(current)) {
                    if (visited.contains(neighbor)) continue;
                    queue.add(neighbor);
                    visited.add(neighbor);
                }
            }
            steps++;
        }
        return -1;
    }
    
    private static List<String> getNeighbors(String current) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < current.length(); i++) {
            String next = current.substring(0, i) + nextDigit.get(current.charAt(i)) + current.substring(i + 1);
            String prev = current.substring(0, i) + prevDigit.get(current.charAt(i)) + current.substring(i + 1);
            result.add(next);
            result.add(prev);
        }
        return result;
    }
29

Structured Programming JS Solution:

const nextDigit = new Map();
const prevDigit = new Map();

for (let a = 0; a < 10; a++) {
    const b = ((a + 1) % 10)

    const prev = a.toString();
    const next = b.toString()
    
    nextDigit.set(prev, next);
    prevDigit.set(next, prev);
}

function numSteps(target, trappedCombos) {
    const queue = ["0000"];
    const visited = new Set(queue);
    const traps = new Set([...trappedCombos]);
    let result = -1;
    let count = -1;
    
    while (queue.length > 0 && result < 0 && !traps.has("0000")) {
        count += 1;
        const n = queue.length;
        
        for (
            let i = 0;
            i < n && result < 0;
            i++
        ) {
            const initialCombo = queue.shift();
        
            if (initialCombo === target) {
                result = count;
            } else {
                for (let j = 0; j < initialCombo.length; j++) {
                    const digit = initialCombo.charAt(j);

                    for (const map of [prevDigit, nextDigit]) {
                        const newCombo = initialCombo.slice(0, j) + map.get(digit) + initialCombo.slice(j + 1);

                        if (!traps.has(newCombo) && !visited.has(newCombo)) {
                            queue.push(newCombo);
                            visited.add(newCombo);
                        }
                    }
                }
            }
        }
    }

    return result;
}
31

One of the key things about this specific problem is that you must add each neighbor’s combo to the “visited” hash/set (in the above solution its called steps) at the same time you are iterating through each neighbor. If you add the combo to the visited set only after its been popped from the queue, then you will end up adding neighbors to the queue that have already been visited and will only skip them once they’ve been popped. Specifically, the following Test #3 will time out
1111
0111 2111 1011 1211 1101 1121 1110 1112

if you add the combo to the visited set only after it’s been popped, like so:
trht = set(trapped_combos)

d = deque(["0000"])
v = set()
steps = 0
while d:
    for _ in range(len(d)):
        combo = d.pop()
        if combo == target_combo:
            return steps
        v.add(combo)
        for nb in get_neighbors(combo):
            if nb not in v and nb not in trht:
                d.appendleft(nb)
    steps += 1
return -1

If you instead add the combo to the visited set at the same time you are iterating through each neighbor, Test #3 will not time out, like so:
trht = set(trapped_combos)

d = deque(["0000"])
v = set(["0000"])
steps = 0
while d:
    for _ in range(len(d)):
        combo = d.pop()
        if combo == target_combo:
            return steps
        for nb in get_neighbors(combo):
            if nb not in v and nb not in trht:
                d.appendleft(nb)
                v.add(nb)
    steps += 1
return -1
32

Here’s get_neighbors if you are curious

def get_neighbors(combo):
    neighbors = []
    for i in range(len(combo)):
        v = int(combo[i])
        for j in [-1, 1]:
            newv = v + j
            if newv == 10:
                newv = 0
            elif newv == -1:
                newv = 9
            neighbors.append(f"{combo[:i]}{newv}{combo[i+1:]}")
    return neighbors
33

I refuse to believe people code like this: String newCombo = top.substring(0, i).concat(String.valueOf(nextDigit.get(top.charAt(i)))).concat(top.substring(i + 1));

34

Thanks a ton for posting a bfs version that follows the template. It is so much more easier to understand!

35

A fundamental question - the beauty of BFS in giving shortest paths is true for unweighted graphs with no cycles. But here the last digit loops back to 0, doesn’t that mean, we have a cycle in the graph? How does BFS give us the minimum number of steps in that case?

36

Agreed

37 
def num_steps(target_combo: str, trapped_combos: List[str]) -> int:
    trapped_combos_set = trapped_combos
    start_combo = "0000"
    
    if start_combo not in trapped_combos_set:
        step = 0
        q = deque([(start_combo, step)])
        visited = set(start_combo)

        while q:
            combo, step = q.popleft()

            if combo == target_combo:
                return step

            next_combos = get_neighbors(combo)
            for next_combo in next_combos:
                if next_combo not in trapped_combos_set:
                    if next_combo not in visited:
                        visited.add(next_combo)
                        q.append((next_combo, step + 1))
    return -1

def get_neighbors(combo):
    for i in range(len(combo)):
        num = int(combo[i])
        
        plus_one = (num + 1) % 10
        yield (combo[:i] + str(plus_one) + combo[i + 1:])
        
        minus_one = (num - 1) % 10
        yield (combo[:i] + str(minus_one) + combo[i + 1:])
38

My solution in Java . Using arithmetic instead of Hashmap

public static int numSteps(String targetCombo, List trappedCombos) {
String startingPoint = “0000”;
ArrayDeque lockCombinations = new ArrayDeque<>();
HashSet visited = new HashSet<>();
lockCombinations.add(startingPoint);
visited.add(startingPoint);
HashSet traps = new HashSet<>(trappedCombos);
HashMap<String, Integer> steps = new HashMap<>();
steps.put(“0000”, 0);
int numSteps = 0 ;

    while (!lockCombinations.isEmpty()){
        int size = lockCombinations.size();
        for (int i = 0; i < size; i++) {
            String topCombination = lockCombinations.pop();
            if(topCombination.equals(targetCombo)) return numSteps;
            for (String combination:getNeighbours(topCombination,traps,targetCombo)) {
                if (visited.contains(combination) || steps.containsKey(combination)){
                    continue;
                }
                lockCombinations.add(combination);
                steps.put(combination,steps.get(topCombination+1));
            }
        }
        numSteps++;
    }
    return -1;
}

private static List<String> getNeighbours(String topCombination, HashSet<String> traps, String targetCombo) {
    List<String> neighbours = new ArrayList<>();
    for (int i = 0; i < 4; i++) {
        char c = topCombination.charAt(i);
        char nextchar = nextChar(c);
        char prevChar = prevChar(c);
        String moveupString = topCombination.substring(0,i) + nextchar + topCombination.substring(i+1);
        String movedownString = topCombination.substring(0,i) + prevChar + topCombination.substring(i+1);
        if (!traps.contains(moveupString))neighbours.add(moveupString);
        if (!traps.contains(movedownString))neighbours.add(movedownString);
    }
    return neighbours;
}

private static char nextChar(char c) {
    if (c == '9') {
        return '0';
    }
    Integer nextNum = Integer.parseInt(String.valueOf(c)) + 1;
    return nextNum.toString().charAt(0);
}
private static char prevChar(char c) {
    if (c == '0') {
        return '9';
    }
    Integer nextNum = Integer.parseInt(String.valueOf(c)) - 1;
    return nextNum.toString().charAt(0);
}
39

ask ChatGPT

41

From the picture can someone explain how “0100” and “0200” are not adjacent? How are they not 1 apart?

42 
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        def get_neighbours(node): 
            # each neighbor differs from the node by a value of 1
            # at any of the 4 positions in the node
            res = [] 
            for i in range(4): 
                x = int(node[i])
                for d in (-1,1): 
                    # %10 helps to convert (9+1) to 0
                    y = (x+d)%10
                    neigh = node[:i] + str(y) + node[i+1:]
                    res.append(neigh)
            return res 
        
        queue = deque(['0000'])
        seen = set(['0000'])
        levels = 0
        while queue:
            n = len(queue)
            for _ in range(n): 
                node = queue.popleft()
                if node == target: return levels
                if node in deadends: continue
                for neigh in get_neighbours(node): 
                    if neigh not in seen: 
                        seen.add(neigh)
                        queue.append(neigh)
            levels += 1
        return -1
43

Here is a much more neater solution

from typing import List
from collections import deque

def num_steps(target_combo: str, trapped_combos: List[str]) -> int:
    
    def get_neighbors(node):
        
        num_lst = [int(num) for num in node]
        
        res = []
        
        for idx in range(len(num_lst)):
            
            num = num_lst[idx]
            num_lst[idx] = num + 1 if (num < 9) else 0
            res.append(''.join([str(x) for x in num_lst]))
            num_lst[idx] = num - 1 if (num > 0) else 9
            res.append(''.join([str(x) for x in num_lst]))
            num_lst[idx] = num
            
        return res
                                             
    queue = deque()
    start_node = '0000'
    queue.append(start_node)
    steps = 0
    visited = set([start_node])
    
    trapped_combos_set = set(trapped_combos)
    
    while queue:
        
        n = len(queue)
        
        for _ in range(n):
            
            node = queue.popleft()
            
            if target_combo == node:
                return steps
            
            for neighbor in get_neighbors(node):
                  
                if neighbor not in visited and neighbor not in trapped_combos:
                    queue.append(neighbor)
                    visited.add(neighbor)
                    
                        
           
        steps += 1    
            
    return -1

if __name__ == '__main__':
    target_combo = input()
    trapped_combos = input().split()
    res = num_steps(target_combo, trapped_combos)
    print(res)
44

My solution passed here but not on leetcode, the problem was that I was not checking the starting combination of “0000” to be a trapped combo. If that is the case, we should implicitly return -1.

Can this be added as a testcase.