Hey Sandeep Panda, thanks for this awesome question!
Code at github.com/sidhantpanda/FoxGooseCorn.
We can assume a state of the the game represented as a string of 0s and 1s. 0 means the character is on the right side and 1 means the character/item is on left side.
For eg, the string "1011" represents:
Now each index has 2 possible values -> 0 or 1. Hence the total number of states the game can possible go into is 2^4 = 16.
We have a forest of all the states possible:
[0000] [0001] [0011] [0111] [1000] .... [1100] ... [11110] ....
Now as per the question, there are some illegal states which will lead to the game stopping. We'll mark these states as invalid.
Now we check each state and find the possible next state from it (provided its not invalid) and add a directed edge between them with a weight of 1.
Now we have a directed graph and we can easily use Dijkstra's algo to find the shortest path and steps required.
The time complexity for setting up the forest is O(n). Thus our whole solution is limited by the time complexity of Dijkstra where we are using a MinHeap as a priority queue.
Would recommend everyone to give this question a try! It touches a lot of concepts: