Job hunting and programming tests

[pendell]

Well, here's one I personally found mortifying.

Game of Stones, part 1

Problem description in spoiler

Spoiler: Problem

Show

Two players (numbered 1 and 2) are playing a game with stones. Player always plays first, and the two players move in alternating turns. The game's rules are as follows:

In a single move, a player can remove either 2, 3, or 5stones from the game board.
If a player is unable to make a move, that player loses the game.

Given the number of stones, find and print the name of the winner (i.e., First or Second) on a new line. Each player plays optimally, meaning they will not make a move that causes them to lose the game if some better, winning move exists.

Input Format

The first line contains an integer, n, denoting the number of test cases.
Each of the subsequent lines contains a single integer, s, denoting the number of stones in a test case.

Constraints
1<=n<=100
1<=S<=100

Output Format

On a new line for each test case, print "First" if the first player is the winner; otherwise, print "Second".

Sample Input

8
1
2
3
4
5
6
7
10

Sample Output

Second
First
First
First
First
First
Second
First

Now, when I saw this game theory problem, I was thinking about a tree to model the different moves, dynamic programming to save answers of previously calculated moves, alpha-beta pruning of the game search tree -- but it turns out you can solve this in one line of code.

Spoiler: Solution

Show

if (numStones % 7 < 2 ) { Console.WriteLine("Second"); } else { Console.WriteLine("First"); }

Okay, obviously you need a little more furniture to pull in the input from stdin, but that's essentially all you need to answer the question. Anyone want to take a crack at why it works? Hint: It's a proof by induction.

There are times when I think I'm never going to have a mathematical head for this -- and I've been doing it for twenty years!

Respectfully,

Brian P.