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