Problem G
Interactive Tic-Tac-Toe

Mårten is extremely good at tic-tac-toe. He’s so good you’ve never managed to beat him. Write a program that plays tic-tac-toe for you, and you might have a chance.

If you don’t know the rules of the game, you can read them on Wikipedia.

Interactivity

This problem is interactive. First, you should read one line containing either first or second, depending on whether you move first or not.

Then, you should repeatedly read in a tic-tac-toe grid containing the current game state (blank if you’re making the first move, otherwise containing Mårten’s last move). After reading the grid, you should output a grid with the move you performed.

If you output a grid where you win or play a draw your program should terminate. If you read a grid where Mårten won or drew your program should terminate.

A grid is output and read as a 3 lines with 3 characters each – . for an empty square, o for Mårten’s pieces, or x for your pieces (note lower-case letters).

Grading

Your solution will be tested on several groups of test cases. To get points for a group you need to pass all the tests of that group.

 first
 ...
 ...
 ...

 ...
 .x.
 ...

 .o.
 .x.
 ...

 xo.
 .x.
 ...

 xo.
 .x.
 ..o

 xo.
 .x.
 x.o

 xo.
 ox.
 x.o

 xox
 ox.
 x.o

 second
 xo.
 xoo
 o.x

 xo.
 xoo
 oxx

 xox
 xoo
 oxx