I was asked this questions in one of my interviews. The questions goes like this
You have a string of '+' and '-' ( eg. ++----++++++-+--+ ). There are two players Player 1 and Player 2. At each turn one of the player can choose any two consecutive '+' i.e. ++ and flip them into --. So if the initial string is ++----++++++-+--+ and then the player has the following 6 choices (2 - 7) .(first one is for reference).
- ++----++++++-+--+
- ------++++++-+--+
- ++------++++-+--+
- ++----+--+++-+--+
- ++----++--++-+--+
- ++----+++--+-+--+
- ++----++++---+--+
The player takes turn one by one. The player which plays the last move will win ( or lose - doesn't make a difference).
Given a initial string and if player 1 takes the first turn, we have to tell who wins?
Now this seems like a classical game theory problem where each player tries to play optimally and at each step plays a move that moves him to a winning position.
Any ideas on how can I approach this to solve ?
PS - Interested more in approach than in solving. I have read http://www.codechef.com/wiki/tutorial-game-theory but couldn't apply the same logic here.
We can use Grundy function here, because after converting ++ to -- the game is divided into a sum of 2 separate games: to the left from -- and to the right. Let's assume that g(l, r) is the value of Grundy function for the [l, r] interval of the given string. To compute it, we can try to change ++ to -- in all possible positions, store all g(l, k - 1) xor g(k + 2, r)(where k is a position where ++ starts) values and choose the smallest non-negative integer that is not among them. The value for the base case(when there are no possible moves) is either 0 or 1(depending on whether the last player loses or wins). The first player wins if and only if g(0, n - 1)(n is the lenght of the input string) is non-zero. This solution has O(n^3) time complexity(there are O(n^2) possible (l, r) pairs and we can compute thr answer in linear time for each of them).