Leetcode: Cracking the Safe
This question is exclusively asked at Google. The question is as follows:
There is a box protected by a password. The password is a sequence of n digits where each digit can be one of the first k digits 0, 1, .... k - 1.
While entering a password, the last n digits entered will automatically be matched against the correct password.
If the correct password is "345" if you type "012345" the box will open because the correct password is matched.
Return the password of minimum length that is guaranteed to open the box. The samples are as follows:
Example 1:
Input: n = 1, k = 2
Output: "01"
Note: "10" will be accepted too.
Example 2:
Input: n = 2, k = 2
Output: "00110"
Note: "01100", "10011", "11001" will be accepted too.
GraceMeng from leetcode does an excellent job at explaining the solution, which turns out to be a De Bruijn sequence. The input password contain all length combinations of digits 0...k so there are k^n combinations in total.
We better make each combination of digits occur once as a substring. A de Bruijn sequence of order n on a size k alphabet A is a cyclic sequence in which every possible length n string occurs exactly once as a substrinc, and such a sequence has length k^n. We try to make these sequences optimal meaning that they are as short as possible.
]
n = 2 and k = 2 and we need all 2-length k-combinations.
This is how we do it.
00(`00`110)
01(0`01`10)
11(00`11`0)
10(001`10`)
We can utilize DFS to find the password. Our goal is to find the shortest input password such that each possible n-length combination of digits [0...k-1] occurs exactly once on the substring, where the node is the current input password. We define an edge if the last n - 1 digits of node1 can can be transformed into node 2 by appending a digit, and this will make an edge between node1 and node2.
The start node is all repeated zeros, and the end node is when all length combinations are visited.
We start with an algorithm where we initially check to see if the number of digits are visited, then we return the function.
If this return function doesn't work, we then attempt to iterate through every digit from 0 to k using the character '0'. Then, we see if the digits contain each other, and see if the same is cracked. Otherwise, delete the character and remove everything. We check the last n - 1 digits of each password, and append each combination accordingly. If a safe is cracked, then we're done otherwise we remove the characters. I probably will look at another explanation after this to clarify things.
public String crackSafe(int n, int k) {
// Initialize pwd to n repeated 0's as the start node of DFS.
String strPwd = String.join("", Collections.nCopies(n, "0"));
StringBuilder sbPwd = new StringBuilder(strPwd);
Set<String> visitedComb = new HashSet<>();
visitedComb.add(strPwd);
int targetNumVisited = (int) Math.pow(k, n);
crackSafeAfter(sbPwd, visitedComb, targetNumVisited, n, k);
return sbPwd.toString();
}
private boolean crackSafeAfter(StringBuilder pwd, Set<String> visitedComb, int targetNumVisited, int n, int k) {
// Base case: all n-length combinations among digits 0..k-1 are visited.
if (visitedComb.size() == targetNumVisited) {
return true;
}
String lastDigits = pwd.substring(pwd.length() - n + 1); // Last n-1 digits of pwd.
for (char ch = '0'; ch < '0' + k; ch++) {
String newComb = lastDigits + ch;
if (!visitedComb.contains(newComb)) {
visitedComb.add(newComb);
pwd.append(ch);
if (crackSafeAfter(pwd, visitedComb, targetNumVisited, n, k)) {
return true;
}
visitedComb.remove(newComb);
pwd.deleteCharAt(pwd.length() - 1);
}
}
return false;
}
This problem I want a shortest sequence with the shortest 4-digit combination, which they are called de Bruijn sequences. These are used in computing, robotics, and DNA sequences.
They have 11, 12, 22, and 21 and we join these combinations with an arrow, if I add a digit to the end of the combination(s) and it overlaps these combinations. We want to prevent a graph that does not overlap with itself. Each Hamilton graph writes every combination of length n and visits each node exactly once.
Hamilton path traverses every node exactly one. We can also write the combinations of length 1 and join them together to an arrow.
The euler cycle is the path that visits every edge exactly once. So we can either find the Hamilton Path or Euler Path, below:
Let's try to do a harder one, the Euler path that contains all the combinations 1, 2 and 3, and contains all the combinations, and we want to find a path that traverses through every edge exactly once. The number of De Bruijn sequences is equal to the number of Euler sequences.
k!^(k^(n - 1))/(k^n)
There is an efficient algorithm to make this graph instead, and we list all the combinations of a specific length and the number that divides a specific length. So n and divisors of n. If 4, we get the combinations of 1, 2, and 4 and order these combinations in lexicographic order, the same as ordering words in a dictionary (A, AA, AAA, AAAA, AAAB, AAAC, AABA, etc.). We cross off the periodic combinations that if you rotate them, they already appear earlier in the list. This means if we get 1112, we can get 2111 and we string all these combinations together and that's it and we get the solution sequence. So let's look at the leetcode de Bruijn algorithm again.
We initialize the password to zeros and initialize a stringBuilder. We also have a visited Combination HashSet and and the number visited target number (k^n) and we decide to crack the safe with a boolean return set, then finally converting the stringBuilder to a string.
If we have the hashSet at full value, we can return true. We take the last n - 1 digits of the password string to look at, and look at the last digits adding a character and adding this digits if the combination does not contain this. We then check, and remove the combination and try other combination while recursively calling the crackSafe function to see if the target number visited is valid.
And that's de Bruijn's in a nutshell.
Comments
Post a Comment