Ninja’s Safe

PROBLEM STATEMENT

Try Problem

After an accident, Ninja is suffering from transient amnesia. He wants to open his safe but has forgotten his password.

The safe’s lock has 4 circular wheels. Each wheel has 10 slots: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. The wheels can rotate clockwise as well as anti-clockwise: for example, we can turn 9 to be 0, or 0 to be 9. Each move consists of turning one wheel in one slot.

The lock initially starts at 0000, a string representing the state of the 4 wheels.

Ninja is given a list of ‘blockages’ dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning, and Ninja would be unable to open it.

There would be a ‘result’ given representing the wheels' value that will unlock the lock, return the minimum total number of turns Ninja is required to open the lock, or -1 if it is impossible for him to open it.

Help Ninja to open his safe.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a single integer ‘N’ denoting the size of the ‘blockages’ array.

The next line contains ‘N’ space-separated strings denoting the values of the ‘blockages’ array.

The third line contains a single string denoting the ‘result’ value.

Output Format :

For each test case, print a single line containing numbers of turns or -1 as per the condition.

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

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5 
1 <= N <= 500
blockages[i].length ==  4
result.length ==  4
result will not be in the list blockages
result and blockages[i] consists of only digits from ‘0’ to ‘9’.

Time Limit: 1sec

Approach 1

Declare a queue and a hashmap ‘visited’ and the count as ‘0’.
Make all the strings of ‘visited’ as true.
Now check whether the initial state “0000” is visited or not, if not push it into the queue.
Run a loop until the queue is not empty.
- Increase the count by 1.
- Decrease the queue size by one each time.
- Check whether the front of the queue is the result or not; if yes, then return count-1.
- Otherwise, check whether the top[i] is 9 or 0, if it is 9 then decrement ‘top[i]’ by 1 i.e. do top[i]--, if it is 0, then change it to 9 and sidewise check for the visited strings if they are not visited push them into the queue (here ‘top[i]’ are the digits of the string present in the front of the queue).
- ‘count-1’ would be our final answer if opening the safe is possible.
Otherwise, return -1.

Try Problem

Approach 2

The idea here is to use the unordered set of the same size as the ‘blockages’ and use a queue to insert the strings which are not visited as well as are not present in the ‘blockages’. Also,instead of dealing with the string , change them into integers and then move forward towards the result.

Algorithm:

Declare an empty queue and an unordered set of size ‘blockages’ and the count as ‘0’.
Insert initial state into the queue if it is not present in the ‘blockages’; otherwise, return -1.
Run a loop until the queue is not empty. The front of the queue is the result or not; if yes, then return count-1.
- Note its size.
- Decrease the size of the queue by one at every iteration.
- Check if our current state is the required result if it returns the ‘count’.
- Otherwise, check if it is visited or not. If not, insert it; otherwise, continue.
- Now change the string into the integers and change the integers by one-one places to check the possibility of new unvisited codes and then push them into the queue and increase the count by one
Finally, return the answer either it is the number of steps to reach the result or -1 if it is impossible to open the safe.

Try Problem