# Ninja’s Safe

Posted: 18 Mar, 2021

Difficulty: Moderate

#### 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.

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.

SIMILAR PROBLEMS

# Number Of Sequence

Posted: 18 Jun, 2021

Difficulty: Hard

# PostFix To Prefix

Posted: 24 Jun, 2021

Difficulty: Easy

# Numbers with product K

Posted: 29 Jun, 2021

Difficulty: Hard

# Find the N-th term

Posted: 29 Jun, 2021

Difficulty: Hard

# Implement a Queue

Posted: 27 Jul, 2021

Difficulty: Easy