The 2004 British Informatics Olympiad - Round One question 2

In the game of Four in a Line, two players alternate dropping pieces of their own colour into a vertical board. The board consists of seven columns, each of which can hold six pieces. On their turn, a player can choose to drop their piece into any column which still has an empty space. When a piece is dropped into a column, it falls to the lowest unused position in that column.

The winner is the first player to form a line of four adjacent pieces of their own colour; horizontally, vertically or diagonally.

A simple strategy is for a player to choose their moves based on the following rules:

1. If there is a move which will win the game immediately, this move is played. If several such moves exist, the leftmost one is played.
2. If rule 1 does not indicate which move to take and there is a move which, if played by the other player would cause them to win immediately, this move is played. If several such moves exist, the leftmost one is played.
3. If neither rule 1 nor rule 2 indicates which move to take, play in the leftmost column which still has empty space.

The following examples demonstrate the simple strategy on some typical boards. Note that the boards themselves have arisen from an initial sequence of moves that did not follow the strategy.

The first player's pieces are shown using and the second player's pieces are shown using . The columns are numbered from left to right, with the leftmost column being number 1.

If it is the first player's turn on the following board, they must play in column 3, according to rule 1, to win with a horizontal line of four pieces.

Write a program to play Four in a Line. Both players will be controlled by the computer and play using the simple strategy.

Your program should first read in a single integer, n (1≤n≤10). This will be followed by a line containing n integers, indicating the columns for the first few moves of the game; the first number indicating the first move for player one, the next number indicating the first move for player two, etc. The columns are numbered from left to right, with the leftmost column being number 1. None of these initial moves will generate a winning line.

You should then output the board, indicating empty spaces with a -, pieces belonging to player 1 with a * and pieces belonging to player 2 with an o.

Until your program terminates you should repeatedly wait for input, and then:

• If you receive the letter n, you should play the next move of the game.
• If you receive the letter r, you should play the rest of the game, until one player has won or the board is full.
• Ignore any other input

After each command, you should output the board. If the game has been won you should output Player 1 wins (for a first player win) or Player 2 wins (for a second player win), and then terminate. If the board is full, you should output Draw and then terminate.

[In the sample run, the comments shown in italics in square brackets are for information only. These should not be entered into, or produced by, your program.]