Thursday, June 16, 2011

A combinatorial game problem

So, I was lurking on the AlgoGeeks group when I came across this interesting question posted by Piyush from IIIT-Allahabad. Apparently, it came in a DE Shaw interview.

The original question is:
Given N heaps numbered sequentially from 1 to N that contain atleast 1 counter each, players move in turns to pick counters from the heaps. The rules of the game are such that counters can only be picked from the lowest numbered heap that is not empty. The question is: design an algorithm for optimal play that will determine which player will win given a configuration of heaps.

Here's my answer:
There are only 2 types of heaps in this problem:
1. Optional heaps -> have > 1 coins
2. Non-optional heaps -> have = 1 coins

For optional heaps, optimal play dictates that you either pick all the elements from the heap or leave just one element in the heap when you play your turn. This is an obvious constraint because otherwise, you're putting your opponent in the driving seat with a heap configuration that is similar to yours and if he can force a win, he will! :)

So, to repeat: there are only 2 things you can do with an optional heap - pick all or leave 1. Now, to get the solution for the game, read on:

Start from the rightmost heap. 
This is base case - whoever gets this heap surely wins.
Look at the heaps before it.

If it is a non-optional heap (1 element only), then the assured outcome is the 
inverse of the assured outcome of the next heap.

If it is an optional heap, then the assured outcome for whoever is first is a win - irrespective of the
assured outcome of the next heap. This is because the player whose turn 
it is to move can either pick up all the elements of the heap thus converting it 
into the assured outcome of the next heap (if that is a loss for the other player) 
or can leave 1 element in the heap, thus getting a win by optimal play.

When there are multiple optional heaps in sequence, the optimal play is
to always force your opponent to keep picking the last element from each heap
so that you retain control over the fate of the game. Hence, a sequence of 
optional heaps is the same as a single optional heap.

Unroll the loop till the first heap and output the assured outcome as the answer.

For example 1 2 2 2 1:
1 - Win
2 1 - Win for Player 1 at this stage
2 2 1 - Win for Player 1 at this stage
2 2 2 1 - Win for Player 1 at this stage
1 2 2 2 1 - Loss for Player 1 at this stage...
Outcome: Loss
This is equivalent to 1 2 1

For eg.
For the heap: 1 2 3 1 2
2 - win for player 1
1 2 - Loss for player 1
3 1 2 - Win for player 1
2 3 1 2 - Win for player 1
1 2 3 1 2 - Loss for player 1
This is equivalent to 1 2 1 2

For all the games discussed above:
Game 1: 2 3 -> is the same as game 2 2 which is equivalent to 2 -> Player 1 wins
Game 2: 1 2 -> is a loss for player 1 for obvious reasons
Game 3: 2 1 -> is a win because of the optional heap
Game 4: 1,2,3,1,4 -> Loss for player 1. Equal to 1 2 2 1 2 -> 1 2 1 2 -> Loss
Game 5: 1,1,2,3 -> Win for player 1. Equal to 1 1 2 2 -> 1 1 2 -> Win
Game 6: 2,1,3,4,5 -> Equal to 2 1 2 2 2 -> 2 1 2 -> Win for player 1

Nice question. Hope you enjoyed the solution too! :)
Feel free to leave a comment if you liked it and 
don't forget to follow me on Twitter at:  http://twitter.com/divyekapoor