Open the lock problem with JavaScript
You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
. The wheels can rotate freely and wrap around: for example we can turn '9'
to be '0'
, or '0'
to be '9'
. Each move consists of turning one wheel one slot.
The lock initially starts at '0000'
, a string representing the state of the 4 wheels.
You are given a list of deadends
dead ends, meaning if 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 value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.
This problem can be solved by shortest path problem on a graph. We start at 0000
for each step there is 8 possible directions we can take. for example for
0000
next connections are 1000, 9000, 0100, 0900, 0010, 0090, 0001, 0009
Similarly if we take next step as 1000
the combinations are 1001, 9001, 0101, 0901, 0011, 0091, 0002, 0000
here if we notice 0001
will lead to 0000
again. So we have to keep track of these combinations in a separate data structure to avoid taking this as next step.
So we will be having two functions one to loop through each step in a bread first search fashion and the other to generate the next possible combinations
Here is the javascript implementations