Numbers Game Challenge

An interesting programming challenge of Numbers Game proposed by the DevDraft aroused my attention. Though this semester is rough, I still spent some time taking the challenge and achieved 100% code correctness by passing all the big integer test cases up to 10^10. According to their editorial, my approach falls into the bottom up category which is more efficient at runtime than recursive solutions.

Problem Statement

A turn-based two-player game is played as follows. There are three positive integers, which are given initial values at the beginning of the game. The two players alternate turns. Each player must, on their turn, choose exactly one of the integers and replace it with the average of the other two, rounded down to the nearest integer if the average is not an integer. For example, if the integers currently in play are 4, 9, and 12, the player whose turn it is may choose one of the following three actions:

1. Replace 4 with (9 + 12) / 2 = 10 (rounded down), changing to {9, 10, 12}. 
2. Replace 9 with (4 + 12) / 2 = 8, changing the set of integers to {4, 8, 12}.
3. Replace 12 with (4 + 9) / 2 = 6 (rounded down), changing to {4, 6, 9}. 

No player, however, is allowed to make a move that would not change which integers are present. In our example, suppose the first player chooses to replace 9 with 8 according to the second option above. It would now be the second player's turn to act on the integers {4, 8, 12}. The second player would not be allowed to choose to replace 8, because the replacement for 8 would be (4 + 12) / 2 = 8, which would lead to no change in the integers present. The second player therefore has only two options:

1. Replace 4 by (8 + 12) / 2 = 10, passing {8, 10, 12} back to the first player.
2. Replace 12 by (4 + 8) / 2 = 6, passing {4, 6, 8} back to the first player.

A player loses if there are no valid moves available on their turn. For example, if the set of integers on a player's turn is {3, 3, 3}, there is no available move that does not violate the constraint that a player must make a change to the integers present, since no matter which of the 3s is chosen, the replacement would be (3 + 3) / 2 = 3. Having no valid moves is the only way in which a player can lose; the opposing player then wins.

You are playing the above game against an AI. Unfortunately for you, it is a supercomputer that has already predicted all possible games on all possible inputs and knows all the optimal strategies to use against you. Your only hope is that you're allowed to choose whether you'd like to take the first turn, or let the computer play first. Can you find a way to always win the game?

Example

Input:

4             // four games
3 3 3         // 1st game initial state
3 3 4         // 2nd game initial state
10 11 13      // 3rd game initial state
1 17 43       // 4th game initial state 

Correct output:

Second        // win by taking the 2nd round
First         // win by taking the 1st round
First         // ...
First         // ...

Implementation

Analysis

Since the input involves big integers. The solution must be derived at least as efficiently as logarithmically. It's quite reasonable because each time the difference between numbers is halved regardless of the number chosen. When a number is selected for the turn, the problem is reduced to choose a number given the new differences in the next turn. The process forms a search sequence and continues until reaching a base case where a decision can be made. The search sequence may be cached to accelerate the following test cases so that the time and space complexity are both logarithmic in terms of the maximum differences between numbers. 

Algorithm

Next, start with simple test cases to figure out the decision to make according to the differences between numbers. The main algorithm follows.

1. sort the input numbers in an ascending order, say n1 <= n2 <=n3
2. take the differences diff1 = n2 - n1 and diff2 = n3 - n2
3. check if diff1 and diff2 form a boundary case and solve directly as follows.
   (0, 0) => return "Second"
   (0, 1) => return "First"
   (1, 0) => return "First"
   (1, 1) => return "Second" 
4. If not, make the decision based on diff1 and diff2 collectively and diff3 when necessary as follows. The procedure isFirst() returns the decision and is explained later. If there is any decision saying "First," then the final decision goes for First. Otherwise, "Second" is returned.

if(diff1 == diif2 || diff1 = diff2 + 1) {
    // differences are balanced, only consider n1 and n3 which are selectable
    return isFirst(diff1) || isFirst(diff2) ? "First" : "Second"
} else {
    // all the three numbers are selectable and should be considered
    let diff3 = n3 - n1;
    return isFirst(diff1) || isFirst(diff2) || isFirst(diff3) ? "First" : "Second"
}

The isFirst(diff) makes a decision, true for First and false for Second, based on the difference between numbers. The base cases are 1 for Second and 2 for First since 1 and 2 will be respectively reduced to boundary cases (0, 1) and (1,1). The decision is derived recursively according to the following rules.

1. If there exists a First decision from the reduced differences, go for "Second."
2. If all the decisions for the reduced differences are Second, go for "First."

In this way, with (0, 1) => First and (1, 1) => Second, base cases 1 and 2 return "Second" and "First" respectively.

Now, following the boundary cases, we found the decisions for ranges of differences shown below.

First      Second
             1
2           3-5            
6-10      11-21
22-42    43-85
....

The start of the Second range would be the start of the First range multiplied by 2 minus 1, say 3 = 2*2-1 and 11 = 6*2-1. The start of a particular First range can be derived by multiplying the previous start of the Second range by 2, say 2 = 1*2 and 6 = 3 * 2.

Subsequently, we are able to make the decision given a difference by searching for the corresponding range in the sequence. The sequence is cached in a list and only the start of the First difference ranges are stored since the Second difference ranges can be computed in constant time. The complete isFirst(diff) is described as follows.

1. If diff == 1, return false since it is reduced to (0, 1) case.
2. Extend the list until diff is covered
   while(true) {
       if(diff > list.last())
           list.add(2 * (list.last() * 2 - 1));        
   }
3. Binary search the list for the difference range start given diff >= 2
4. Return true if diff is in the First range, or false if in the Second range.

Large Test Cases

492872161511047876121090525535 255150212172885813131239322959 548864392447656644051047609900 

814512952321192527796758893639 538493780251421394966500687072 241642113654220082814598772808

366499418210442055430526207221 435870750795181732477547091132 282660720914873075681153812110

449409426900695373634382676136 174595727592704842993002752823 634010482364894269553198787339 

 and so on.

Compilation and Execution

Assume TextX.txt contains the test cases and TestX.sol is the correct output as shown in the example. Compile and execute the code by typing the following commands.

$> javac NumbersGame.java
$> java NumbersGame TestX.sol < TestX.txt