Let the Wookiee Win!

Interview

Time limit1sMemory limit128 MB

Summary
On a 5x5 board, find the single empty square where playing O neither makes four O in a row nor blocks any of X's winning squares.
Level

Medium4 of 10

Topics
Implementation, Brute force, Array, Simulation
Solved
No attempts yet

Problem

You are playing Galactic Tic-Tac-Toe against Chewbacca. It works just like ordinary Tic-Tac-Toe, except the board is 5×55 \times 5 and the goal is to get four in a row (horizontally, vertically, or diagonally).

In response to a brilliant move of yours, Chewbacca protests loudly and plays a move that sets you up to win. Before you can claim victory, Han Solo warns you that it is unwise to upset a Wookiee — they have been known to pull people's arms out of their sockets when they lose.

Wisely, you decide on a new strategy: let the Wookiee win!

You play O, Chewbacca plays X, and it is your turn. You must choose the single empty square to play so that:

  • placing your O there does not complete four of your own marks in a row (you must not win), and
  • the square is not one where Chewbacca could complete four X in a row on his next turn (you must not block any of his winning moves).

It is guaranteed that exactly one empty square satisfies both conditions.

Input

The input consists of one or more 5×55 \times 5 boards, each separated from the next by a blank line. Within a board, the five cells of a row are separated by single spaces. You are O, Chewbacca is X, and an empty cell is written as *.

For every board it is guaranteed that exactly one empty square can be played that does not cause you to win and does not block any of Chewbacca's winning moves on his next turn.

The last board is followed by a line containing the word Finished.

Output

For each board, print on its own line the number of the square you should play. Squares are numbered as follows.

12345
678910
1112131415
1617181920
2122232425

Examples1

  1. Example 1

    Input
    X O * X X
O O X X *
O O * X X
O X O O X
X O O X O

X X X * O
O * * O X
O O X * X
O * X X O
* X O O O

Finished
    Expected output
    3
17