This question was posted in the InterviewStreet for India Startups. InterviewStreet regularly runs contests were the topics are related to coding, algorithms and puzzles. The toppers of the contest get a chance to apply for a job with the startups. This question is taken from the Indian startups round.
Alice and Bob are playing a game. This game starts with two piles of n1 and n2 chips. They play alternatively and Alice starts first.
In his/her turn a person has to remove one of the piles and split the other pile into two piles, these two new piles need not be of same size. The person who cannot make a move in his turn loses.
Write a program which given n1 and n2 finds the winner. Assume both the players play optimally.
Approach
Visualizing this kind of a puzzle is easy with Mathematical Induction. So take a smaller value and gradually build up.
Example 1:-
Start with (2, 1).
Alice keeps 1, and splits the 2.
Bob gets (1,1). Since he can keep 1, but cannot keep the other 1, he looses.
Example 2:-
Start with (2, 2)
Alice keeps 2, and splits the other 2.
Bob gets (1,1). Since he can keep 1, but cannot keep the other 1, he looses.
Example 3:-
Start with (3, 2)
Bob gets (1,1). Since he can keep 1, but cannot keep the other 1, he looses.
Example 4:-
Start with (3, 3)
Alice keeps 3, and splits the other 3.
Bob gets (2,1). Bob keeps 1 and splits 2.
Alice gets (1,1) she looses.
Example 5:-
Start with (8, 1)
Alice keeps 1, and splits the 8
Bob gets (5, 3). He cannot keep 5 and split 3, since in that case he will have to provide (2, 1) in which case he will loose immediately. So he splits 5. To split 5, he cannot split it to (3, 2) as Alice will keep 3 and split the 2 as (1,1). In this case again Bob will loose. So to keep the game going he will split 5 as (4,1).
Alice gets (4,1). She keeps 1 and splits 4. There are 2 options (2, 2) and (3,1). But if she gives (2,2), in the next move Bob will provide her (1,1) and she will loose. So she splits (3,1).
Bob gets (3,1). He keeps 1 and has to split (2,1). So again he looses.
In example 5, instead of Alice splitting (5, 3), what if she split (4,4) or (6, 2). Well (6,2) is not possible, as she will loose immediately. Assume she splits (4, 4)
Bob gets (4, 4). He can split as (2, 2) which he won't do. So he will split (3, 1).
Alice gets (3,1). She keeps 1 and splits ( 2, 1). She will loose.
So splitting 8 as (5, 3) was a better move.
Example 6:-
Start with (10, 1).
Bob (5, 5)
Alice ( 4, 1)
Bob (3, 1)
Alice ( 2, 1) and wins
Start with (10, 1)
Bob (6, 4)
Alice (3, 1)
Bob (2, 1) and wins
Start with (10, 1)
Bob (6, 4)
Alice (3, 3)
Bob (2, 1) and wins
Solution:-
I have provided a solution which ensures the highest chances for Alice to win. Alice winning chances are when she gets atleast one input as even. For instance (10, 1) here 10 was even. She will split it into 2 odds - 5 and 5. This way she can ensure her winning. If she got (8, 1) then she can split (5, 3). If she got (8, 12) still she can split (5, 3). This way she can ensure the game is finished early.
If she gets (13, 1) that is the only option available is an odd, then Bob stands a winning chance. Still she can keep the game on by splitting into (12, 1).
The program prints the most optimized path favoring Alice.
Bob gets (2,1). Bob keeps 1 and splits 2.
Alice gets (1,1) she looses.
Example 5:-
Start with (8, 1)
Alice keeps 1, and splits the 8
Bob gets (5, 3). He cannot keep 5 and split 3, since in that case he will have to provide (2, 1) in which case he will loose immediately. So he splits 5. To split 5, he cannot split it to (3, 2) as Alice will keep 3 and split the 2 as (1,1). In this case again Bob will loose. So to keep the game going he will split 5 as (4,1).
Alice gets (4,1). She keeps 1 and splits 4. There are 2 options (2, 2) and (3,1). But if she gives (2,2), in the next move Bob will provide her (1,1) and she will loose. So she splits (3,1).
Bob gets (3,1). He keeps 1 and has to split (2,1). So again he looses.
In example 5, instead of Alice splitting (5, 3), what if she split (4,4) or (6, 2). Well (6,2) is not possible, as she will loose immediately. Assume she splits (4, 4)
Bob gets (4, 4). He can split as (2, 2) which he won't do. So he will split (3, 1).
Alice gets (3,1). She keeps 1 and splits ( 2, 1). She will loose.
So splitting 8 as (5, 3) was a better move.
Example 6:-
Start with (10, 1).
Bob (5, 5)
Alice ( 4, 1)
Bob (3, 1)
Alice ( 2, 1) and wins
Start with (10, 1)
Bob (6, 4)
Alice (3, 1)
Bob (2, 1) and wins
Start with (10, 1)
Bob (6, 4)
Alice (3, 3)
Bob (2, 1) and wins
Solution:-
I have provided a solution which ensures the highest chances for Alice to win. Alice winning chances are when she gets atleast one input as even. For instance (10, 1) here 10 was even. She will split it into 2 odds - 5 and 5. This way she can ensure her winning. If she got (8, 1) then she can split (5, 3). If she got (8, 12) still she can split (5, 3). This way she can ensure the game is finished early.
If she gets (13, 1) that is the only option available is an odd, then Bob stands a winning chance. Still she can keep the game on by splitting into (12, 1).
The program prints the most optimized path favoring Alice.
