Google has an annual programming competition called “code jam”.  There are multiple rounds, each consisting of 3 problems to solve.   They leave the old code jam websites up and it is a great place to find interesting problems.  They also have an automated answer checker, so you can verify that your solution is correct.   This problem comes from the 2010 competition, round 1.  You can (and should) check out the problem here.    Another aspect of this competition is that there are two inputs you need to consider.  One input consists of smaller numbers, the other larger.  So a solution that works for the small input may or may not also work for the larger….

Problem:  You and a friend are playing a game with 2 numbers, A and B.  On each turn, a player subtracts a multiple of one from the other.  The first person to make one of the numbers equal or drop below 0 loses.

For example:                               A = 14,B = 5.
You:  Subtract 5 * 2 from 14        A = 4, B = 5
Friend: Subtract 4 from 5            A = 4, B = 1
You: Subtract 1*3 from 4             A = 1, B = 1
Friend: Subtract 1 from 1            A = 0, B = 1, You win.

Determine how many positions within a given range for A and B would be winning positions for the first player.

Musings:

Either player can force a win by making the numbers equal.  If they are not equal, the next player can always subtract the lesser from the greater and the game continues.  So, if A = B at any point, the player who’s turn it is will lose.

To make the numbers equal, check if there is a number k such that B – (A*k) = A or A – (B*k) = B, that is, if one number is a factor of the other.  If the numbers are 15 and 5, you can subtract 5*2 from 15.  If the numbers are 54 and 9, you can subtract 9*5 from 54.

We therefore can assert that a position is winning if one number is a factor of another, and it is losing if your only move is a move resulting in one number being a factor of the other.

The most obvious method of solving the problem would be to attempt all possible moves for a game and see if there are moves that always lead to a first player victory.  A simple example would be A = 21, B = 12.

You:  Subtract 12 from 21          A = 9, B = 12 – only move available.
Friend: Subtract 9 from 12         A = 9, B = 3 –  only move, and now B is a factor of A, so…
You:  Subtract 3*2 from 9:          A = 3, B = 3 -  You win.

In this situation, we were able to get to the factor situation on a single path, there was only one possible move to attempt.

But what if our starting numbers were 3 and 3005.  There are 1001 possible moves the first player could make, and then potentially thousands more after that, (if first player subtracts just 3 from B, we have A = 3, B = 3002; much the same situation).  This would skyrocket out into recursion-netherworld.   So, as is often the case, we need a better way.

Notice in the example game above, at what point were you able to force victory?  When A = 9 and B = 3, there are 3 moves available.  If you played 9 – (3*1), the board is left at A = 6, B = 3, a losing position.  So there were two moves you could make without immediately losing, one of which led to victory, the other led to defeat.

Consider any position in which A is significantly larger than B.    If you subtract the largest multiple of B from A the resulting position is either winning or losing.  If it is winning, you can make this move.  If it is losing, you could instead make the move that is one multiple of B less and force our opponent to make the only remaining move, which leads to the losing position just identified.  Consider A = 102, B = 4.  The largest multiple that will fit in A is 100.  This leaves the position A = 2, b = 4, a losing position (as your opponent can hand back 2,2).  So instead, subtract 4*24, leaving A=6, b=4.  Your opponent now must play 6-(4*1), and we win with the position noted earlier.  So A = 102, B=4 is a winning position.  This would be true of any position where A is at least 2 * B. This gives us at least 2 choices to be able to choose the winning move.

What if A is less than 2 times B?  Keeping in mind that A is the greater, we can’t subtract A from B or we would lose the game.  So our only move is to subtract B from A.  If the resulting position leaves one number that is at least twice the other, we’ve lost and we can’t do anything about it.  If not, the game continues until we get to a position where it is so.  For the purposes of this discussion A is always the greater, not necessarily the first number on the board.

So a simple java method to solve this is:

 boolean isWinningPosition(int a, int b){ 
     if (a < b) return isWinningPosition(b, a); 
     if (a == b) return false; 
     if (a >= 2*b) return true; 
     return (!isWinningPosition (b, a-b)); 
} 

This algorithm solves the problem recursively.  It is simple, neat, and elegant.  You can use it to solve the small data set on the code jam practice page.  But it will not work for the large data set, the numbers in use are too large.  When you get to a range for A and B that is in the millions long, there are too many choices, games take too many moves, the recursion is a liability.

So we need a faster way to determine for starting positions 0 < A < 10000000 and 0 < B < 10000000 (or whatever), how many positions are winning?  Let’s go back and look at what happens to the equations for a few rounds.  In each round we check if the higher number is more than twice the lower.  If not, we subtract the lower from the higher.  Remember that “winning” is the case when the first player, the one that makes a move in round 1, wins.

Round	Higher Number	Lower Number	Condition	Solve for A / B
Round 1	A	B	Winning if A > 2B	A/B > 2
Round 2	B	A – B	Losing if B > 2(A – B)	A/B < 3/2
Round 3	A-B	B- (A – B)	Winning if a-b > 2(2B – A)	A/B > 5/3
Round 4	2B – A	2A – 3B	Losing if 2B – A > 2 (2A – 3B)	A/B < 8/5
Round 5	2A – 3B	5B – 3A	Winning if 2A – 3B > 2(5B – 3A)	A/B > 13 / 8

In the final column, I am rewriting the condition in terms of the ratio of the original starting numbers A and B.  In the first round, if this ratio is greater than 2 we can be sure it is a winning position, not very helpful, as we already know that.  But then it gets more interesting.  After round  2, we can say that if A / B < 3/2, we can be certain that the original position was  a losing one.   This is because the only move available to us in Round 1 must result in a position where the greater number will be more than twice the lesser.   Then with round 3 we can say that any position where A / B > 5/3 is winning position.  Then with round 4 we refine the observation from round 2, in fact any position where A/B < 8/5 is losing.

It may not be apparent from the fractions, but look at the numbers in decimal.

Round1 :  > 2 = Winning
Round2 : <1.5 = Losing
Round3 > 1.67 = Winning
Round4 <1.6 = Losing
Round 5 > 1.63 = Winning
Round 6 < 1.62 = Losing

Notice anything now?  If A / B is above the red line, it is a winning position.  If it is below the blue line, it is a losing position.    And the red and blue lines are converging to a single value which is approximately 1.618.  Another name for this number is the golden ratio, or phi.  So, if A  / B > phi, the position is winning.

This may seem strange, paradoxical. I think of it as three zones, winning, losing, and no-man’s land.  At the beginning of the game, there is a substantial no-man’s land, but as the game goes a few rounds, no man’s land gets smaller until a position favors one player.  Smaller numbers usually lead to quicker games, but as the numbers get bigger, they could take more rounds to determine.  3251, 5201 would take three moves to get one number more than double the other.   Pairs such as 6212427,10051706 would take still longer.

So our new algorithm is simply, for each value of A, [ A,B] is a winning position if A > B * 1.618, or if A < B / 1.618 (because B is at least phi * A).  So if A = 3, it is a winning position when B > 4.854, or when B < 1.854.   Rather than actually testing each value, we can just do some simple arithmetic to calculate the overlapping of the available B range and winning numbers.

Solution:

    for (int a = lowA; a <=highA; a++){

    int winningGreater = (int)Math.ceil(a * phi);

    int winningLess = (int)Math.floor(a / phi);

    if (lowB >= winningGreater || highB <= winningLess) {

        numberOfWinningPositions = highB - lowB + 1; //all B are winners

    } else {

        numberOfWinningPositions += Math.max(highB - winningGreater + 1, 0);

        numberOfWinningPositions += Math.max(winningLess - lowB + 1, 0);

    }

}

 

Recursion is beautiful like a home run.  Solving the same problem without recursion is beautiful like a perfect game.

Final Notes:

This problem is similar to Euclid’s algorithm for finding the greatest common divisor of two integers, where you subtract the lesser number from the greater until you get A = B.  http://en.wikipedia.org/wiki/Euclidean_algorithm