Week 12: Exercises

1. Button Game

Consider the following game. There is a row of N squares, each containing some positive integer. A button begins on the leftmost square. On each player's turn, they can move the button right either (a) one square or (b) by k squares, where k is the number currently under the button. The winner is the player who first moves the button past the rightmost square. Write a method that takes an array containing the numbers on the board, and returns a boolean which is true if the first player can always win.

2. Wythoff's Game

A certain game is played as follows. A chess queen is placed on a 8 x 8 chessboard, one square below the upper left corner. Two players alternate moves. On each player's turn, they must move the queen in one of three directions: either rightward, downward, or diagonally down and to the right. The first player to move the queen into the lower-right corner wins.

With perfect play, will the first player win or lose? Write a program to determine the answer.

3. Visual Wythoff

Write a Windows Forms program that displays an 8 x 8 chessboard. Each square should be colored red if the player whose turn it is to move can always win from that square, blue otherwise.

4. Ghost

Consider the following game. Let W be a set of words, each containing only lowercase letters from 'a' to 'z'. Two players take turns adding a letter to a string S, which is initially empty. A player loses if after their turn either

1. they have made a word (i.e. S is a word in W), or

2. no more words are possible (i.e. S is not a prefix of any word in W).

For example, suppose that W = { "chirp", "cat", "dark", "dog", "donate", "donut" }. The game might proceed as follows:

1. A chooses d

2. B chooses o

3. A chooses n

4. B chooses u

Now A has lost: if he chooses 't' he has made the word 'donut', and he cannot choose any other letter since then no other word will be possible.

Write a method that takes an array of strings (the set W) and returns a boolean which is true if the first player can always win the game.

5. Parsing Arithmetic Expressions

Write a program that reads an arithmetic expression from standard input and constructs an expression tree. Expressions are defined by this grammar, and may also include embedded whitespace.

digit = '0' | '1' | … | '9'

op = '+' | '-' | '*'

const = digit
expr = const | '(' expr op expr ')'

6. Expressions with Numbers

Extend the previous program so that numbers may have any number of digits.