Unlock Briefcase
There is a briefcase protected by a lock with 4 circular wheels. The password is a sequence of 4 digits.

1. Each wheel has 10 slots: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ’9’. 2. The wheels can rotate freely and wrap around, ‘9’ can be left rotated to ‘8’ and right rotated to ‘0’, similarly ‘0’ can be right rotated to ‘1’ and left rotated to ‘9’. Rotation of one wheel counts to one rotation. 3. Initially, the lock starts at “0000”, a string representing the state of four wheels.

You are given a list of dead ends (codes of 4 digits), meaning if at any point the lock displays any of these codes, the wheels of the lock will stop turning, and you will be unable to open it.

Given a target representing the code that will unlock the briefcase, return the minimum total number of turns required to open the lock, or -1 if it is not possible.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The first line of each test case contains an integer ‘N’ denoting the number of dead-end codes. The second line of each test case contains the ‘N’ single-space separated dead-end codes. The third line of each test case contains a string ‘target’ representing the unlocking code.

Output Format:

For each test case, print a single line containing a single integer denoting the minimum number of rotations will be printed. The output of each test case is printed in a separate line.

Note:

You don’t have to print anything, it has already been taken care of. Just implement the function.

Constraints:

1

Question

Unlock Briefcase

There is a briefcase protected by a lock with 4 circular wheels. The password is a sequence of 4 digits.

1. Each wheel has 10 slots: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ’9’.

2. The wheels can rotate freely and wrap around, ‘9’ can be left rotated to ‘8’ and right rotated to ‘0’, similarly ‘0’ can be right rotated to ‘1’ and left rotated to ‘9’. Rotation of one wheel counts to one rotation.

3. Initially, the lock starts at “0000”, a string representing the state of four wheels.

You are given a list of dead ends (codes of 4 digits), meaning if at any point the lock displays any of these codes, the wheels of the lock will stop turning, and you will be unable to open it.

Given a target representing the code that will unlock the briefcase, return the minimum total number of turns required to open the lock, or -1 if it is not possible.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the number of dead-end codes.

The second line of each test case contains the ‘N’ single-space separated dead-end codes.  

The third line of each test case contains a string ‘target’ representing the unlocking code.

Output Format:

For each test case, print a single line containing a single integer denoting the minimum number of rotations will be printed.

The output of each test case is printed in a separate line.

Note:

You don’t have to print anything, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10 
1 <=  N <= 5 * 10 ^ 4
|TARGET| = 4

Where ‘T’ is the total number of test cases, ‘N’ represents the number of dead-end codes, and ‘|TARGET|’  represents the length of the target.

Time limit: 1 sec.

Accepted Answer

can be easily solved using level order traversal

Accepted Answer

Breadth First Search

The idea is to use breadth first search. Find all possible codes that can be formed after one rotation in current code and for all those codes, find the next codes that can be formed after one rotation. These steps will lead to all possible codes that can be formed from the initial string. After, say ‘r’ number of rotations, the codes formed contain a code that is equal to the given target, you have reached to the target in minimum number of rotations that is ‘r’.

Algorithm :

Take an unordered set, avoid, to store all the dead end codes.
Take a queue and push the initial string “0000” to it. The queue will store the next valid codes possible by increasing or decreasing a digit by one unit.
If the starting code “0000” or target is present in the dead end codes, return -1.
Let the current size of the queue be ‘num’. Iterate from 0 to num - 1 and do the following:
1. Pop a code from the queue. If the code is already present in avoid, there is no need to consider this code and continue with the next iteration.
2. If the current code is equal to the target, return the count.
3. Insert count in avoid.
4. Traverse all the digits in the code, once increase the digit by one unit and once decrease it keeping the remaining digits of the code constant. Push these new codes in the queue.
Keep repeating step 4 until there are no further combinations left and the queue has become empty.
If the queue is empty and the target is not found, return -1.

Space Complexity: OtherExplanation:

O(N), where N is the number of dead end codes.

Since we are storing all the visited codes in a map and a queue is used to store all the possible codes formed after every rotation consuming space almost equal to O(2 * (10 ^ 4)). All the dead-end codes in a map, which takes O(N). Thus, the final space complexity will be O(N + 2 * 10 ^ 4) = O(N).

Time Complexity: OtherExplanation:

O(10 ^ 4).

There can be 10 * 10 * 10 * 10 = 10 ^ 4 possible number of codes that can be formed from the initial string “0000”. In BFS, every code is visited at most once in the worst case. Thus, the final time complexity will be O(10 ^ 4).

Java (SE 1.8)

/*

	Time complexity: O(10 ^ 4) 

	Space complexity: O(N)

	

	where N is the number of dead end codes.

*/



import java.util.ArrayList;

import java.util.HashSet;

import java.util.Queue;

import java.util.LinkedList;



public class Solution {

    public static int unlock(ArrayList deadends, int n, String target) {

        // To store dead end codes and visited codes.

        HashSet avoid = new  HashSet();



        // Insert all dead end codes in avoid.

        for (int i = 0; i < n; i++){

            avoid.add(deadends.get(i));

        }



        // If the initial code is a dead end code or the target is a dead end code, return -1.

        if (avoid.contains(target) || avoid.contains("0000")){

            return -1;

        }



        Queue q = new LinkedList();

        // Push the initial string to the queue.

        q.add("0000");



        int count = 0;

		

        while (!q.isEmpty()){

            int num = q.size();



            for (int k = 0; k < num; k++){



                String current = q.poll();



                // If the current code is in avoid, no need to consider it.

                if (avoid.contains(current)){

                    continue;

                }



                // If the new code formed is the target code, return the count.

                if (current.equals(target)){

                    return count;

                }



                // Add the current code to avoid.

                avoid.add(current);



                // Traverse the code.

                for (int i = 0; i < 4; i++){



                    // Right rotating the current wheel.

                    int digitUp = (current.charAt(i) - '0' + 1) % 10;



                    // Left rotating the current wheel.

                    int digitDown = (current.charAt(i) - '0' + 9) % 10;

                     

                    String newStr = current;

                    newStr = newStr.substring(0, i) + Integer.toString(digitUp) + newStr.substring(i + 1);

                    q.add(newStr);

                    newStr = newStr.substring(0, i) + Integer.toString(digitDown) + newStr.substring(i + 1);

                    q.add(newStr);

                }

            }

            count++;

        }



        // If target code can't be reached.

        return -1;

    }

}

Python (3.5)

'''

	Time complexity: O(10 ^ 4)

	Space complexity: O(N)



	where N is the number of dead end codes.

'''



from collections import deque



def unlock(deadends, n, target):



    # To store dead end codes and visited codes.

    avoid = set(deadends)



    # If the initial code is a dead end code or the target is a dead end code, return -1.

    if(target in avoid or "0000" in avoid):

        return -1



    q = deque()



    # Push the initial string to the queue.

    q.append("0000")



    count = 0



    while len(q):



        num = len(q)



        for j in range(num):



            current = q.popleft()



            # If the current code is in avoid, no need to consider it.

            if current in avoid:

                continue



            # If the new code formed is the target code, return the count.

            if current == target:

                return count



            # Add the current code to avoid.

            avoid.add(current)



            # Traverse the code.

            for i in range(4):



                # Right rotating the current wheel.

                digitUp = (ord(current[i]) - ord('0') + 1) % 10



                # Left rotating the current wheel.

                digitDown = (ord(current[i]) - ord('0') + 9) % 10



                for newDigit in (digitUp, digitDown):



                    newString = ''.join(str(newDigit) if j == i else str(

                        current[j]) for j in range(4))

                    q.append(newString)



        count += 1



    # If target code can't be reached.

    return -1

C++ (g++ 5.4)

/*

	Time complexity: O(10 ^ 4) 

	Space complexity: O(N)

	

	where N is the number of dead end codes.

*/



#include 

#include 



int unlock(vector &deadends, int n, string target)

{



    // To store dead end codes and visited codes.

    unordered_set avoid;



    // Insert all dead end codes in avoid.

    for (int i = 0; i < n; i++)

    {

        avoid.insert(deadends[i]);

    }



    // If the initial code is a dead end code or the target is a dead end code, return -1.

    if (avoid.find(target) != avoid.end() || avoid.find("0000") != avoid.end())

    {

        return -1;

    }



    queue q;

    // Push the initial string to the queue.

    q.push("0000");



    int count = 0;



    while (!q.empty())

    {



        int num = q.size();



        for (int k = 0; k < num; k++)

        {



            string current = q.front();

            q.pop();



            // If the current code is in avoid, no need to consider it.

            if (avoid.find(current) != avoid.end())

            {

                continue;

            }



            // If the new code formed is the target code, return the count.

            if (current == target)

            {

                return count;

            }



            // Add the current code to avoid.

            avoid.insert(current);



            // Traverse the code.

            for (int i = 0; i < 4; i++)

            {



                // Right rotating the current wheel.

                int digitUp = (current[i] - '0' + 1) % 10;



                // Left rotating the current wheel.

                int digitDown = (current[i] - '0' + 9) % 10;



                string newStr = current;

                newStr[i] = digitUp + '0';

                q.push(newStr);



                newStr[i] = digitDown + '0';

                q.push(newStr);

            }

        }

        count++;

    }



    // If target code can't be reached.

    return -1;

}