Problem Statement
Five Pile Special is a NIM variant: a two-player combinatorial game. It is played with five piles of tokens, arranged in a row.
There are three types of valid moves:
- The player selects one of the piles, selects a positive number x, and removes x tokens from the selected pile.
- The player selects three consecutive piles, selects a positive number x, and removes x tokens from each of the selected piles.
- The player selects all five piles, selects a positive number x, and removes x tokens from each of the selected piles.
The players take alternating turns. The player unable to make a valid move loses the game.
You are given a position in this game: the long[] piles containing the token counts on the individual piles.
Each move in this game can be represented as a sequence of five values: for each pile, the number of tokens removed from it. Find all winning moves for the given position and return their concatenation (in any order).
Definition
- Class:
- FivePileSpecial
- Method:
- findWinningMoves
- Parameters:
- long[]
- Returns:
- long[]
- Method signature:
- long[] findWinningMoves(long[] piles)
- (be sure your method is public)
Notes
- An empty pile still counts as a pile. For example, if the token counts are {1, 0, 2, 3, 0}, the three non-empty piles are not consecutive.
- You may assume that for each position that matches the constraints given below there are at most 1,000 distinct winning moves.
Constraints
- piles will contain exactly 5 elements.
- Each element of piles will be between 0 and 10^18, inclusive.
Examples
{0, 0, 0, 7, 7}Returns: { }As most of the piles are empty, valid moves in this situation must only involve a single pile. Then, this is clearly a losing position: the second player can win by "mirroring" the first player's moves on the other pile.{7, 7, 7, 7, 7}Returns: {7, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 7, 7, 7, 7, 0, 0, 0, 7, 7, 7, 0, 0, 0, 7, 7, 7, 7, 7, 7, 7, 7 }Taking 7 from all piles is a winning move: the opponent has no tokens left and loses immediately. Taking 7 from the first three piles is also a winning move: it produces the situation from Example 0. Further analysis can show that taking 7 from any other valid set of piles is also a winning move.{47, 42, 0, 42, 47}Returns: { }A less trivial symmetric position that is losing for the same reason as in Example 0.{10, 0, 11, 0, 12}Returns: {3, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 11 }We can emulate a traditional game of three-pile NIM.{0, 11, 14, 19, 0}Returns: {0, 0, 0, 14, 0, 0, 6, 6, 6, 0 }{1, 2, 3, 4, 5}Returns: {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 3, 3, 3 }{0, 1234567890123, 0, 0, 2}Returns: {0, 1234567890121, 0, 0, 0 }