GCJ 2013 - Tic-Tac-Toe-Tomek

Below is the problem statement for 'Tic-Tac-Toe-Tomek' from 'Google Code Jam - 2013':


Problem
-------

Tic-Tac-Toe-Tomek is a game played on a 4 x 4 square board. The board starts empty, except that a single 'T' symbol may appear in one of the 16 squares. There are two players: X and O. They take turns to make moves, with X starting. In each move a player puts her symbol in one of the empty squares. Player X's symbol is 'X', and player O's symbol is 'O'.

After a player's move, if there is a row, column or a diagonal containing 4 of that player's symbols, or containing 3 of her symbols and the 'T' symbol, she wins and the game ends. Otherwise the game continues with the other player's move. If all of the fields are filled with symbols and nobody won, the game ends in a draw. See the sample input for examples of various winning positions.

Given a 4 x 4 board description containing 'X', 'O', 'T' and '.' characters (where '.' represents an empty square), describing the current state of a game, determine the status of the Tic-Tac-Toe-Tomek game going on. The statuses to choose from are:

"X won" (the game is over, and X won)
"O won" (the game is over, and O won)
"Draw" (the game is over, and it ended in a draw)
"Game has not completed" (the game is not over yet)
If there are empty cells, and the game is not over, you should output "Game has not completed", even if the outcome of the game is inevitable.

Input
-----

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of 4 lines with 4 characters each, with each character being 'X', 'O', '.' or 'T' (quotes for clarity only). Each test case is followed by an empty line.

Output
------

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is one of the statuses given above. Make sure to get the statuses exactly right. When you run your code on the sample input, it should create the sample output exactly, including the "Case #1: ", the capital letter "O" rather than the number "0", and so on.

Limits
------

The game board provided will represent a valid state that was reached through play of the game Tic-Tac-Toe-Tomek as described above.

Small dataset
-------------

1 ≤ T ≤ 10.

Large dataset
-------------

1 ≤ T ≤ 1000.

Sample Input
------------
6
XXXT
....
OO..
....

XOXT
XXOO
OXOX
XXOO

XOX.
OX..
....
....

OOXX
OXXX
OX.T
O..O

XXXO
..O.
.O..
T...

OXXX
XO..
..O.
...O

Output
------

Case #1: X won
Case #2: Draw
Case #3: Game has not completed
Case #4: O won
Case #5: O won
Case #6: O won

From the above problem statement, it is clear that we have to check all the rows, columns and diagonals to determine the status of the game. Since it's a small 4*4 board, it was easy for me to build a set of constant strings, which will help my program decide the status of the game. For X to win, the possible set of winning combination strings are: XXXX, XXXT, XXTX, XTXX, TXXX. Similarly, for O to win, the possible set of winning combination strings are: OOOO, OOOT, OOTO, OTOO, TOOO. After knowing this, it was easy for me to loop through rows, columns and diagonals, to determine the status of the game.

Initially, that was the logic (above paragraph) for my solution. After I re-read the problem statement, I wrongly assumed that I have to determine the status of the game, after the next step (future). So, I changed my code to find out who's gonna make the next move (by counting the number of X's and O's - If they are equal, X moves, otherwise O moves) and tried to find the status of the game, after the next step. This was obviously wrong...So, I reverted back to my old code. Here's the solution for the above problem statement:

In the below solution, I'm parsing the input from the file and storing the String input (rows) in an String array of length 4 and passing it to the getStatusQuo method, as shown in the below code:



You can also find the source code at: GCJ 2013 - TicTacToeTomek

2 comments:

  1. I want to thank Julia Navaro for the loan given to me by her loan company NAVARO LOAN COMPANY. Needed a loan to start a my boutique and didn't know how to get a loan until I was introduce to NAVARO LOAN COMPANY by a friend online and she approved my loan of $300,000 with minimum income of $10 and now am a successful woman. If you need any type of loan from any country and of any amount at an interest rate of 2% contact Julia Navaro at
    Navaroloancompany@yahoo.com and live a happy life.

    ReplyDelete
  2. HOW I GOT MY LOAN (Lexieloancompany@yahoo.com)!!!

    My Name is Nicole Marie, I live in USA and life is worth living comfortably for me and my family now and i really have never seen goodness shown to me this much in my life, As i am a struggling mum with two kids and i have been going through a serious problem as my husband encountered a terrible accident last two weeks, and the doctors stated that he needs to undergo a delicate surgery for him to be able to walk again and i could not afford the bills for his surgery then i went to the bank for a loan and they turn me down stating that i have no credit card, from there i ran to my father and he was not able to help me, then when i was browsing through yahoo answers i came across a God fearing man (Mr Martinez Lexie) who provides loans at an affordable interest rate and i have been hearing about so many scams on the Internet mostly Africa, but at this my desperate situation, i had no choice than to give it an attempt due to the fact that the company is from United State of America, and surprisingly it was all like a dream, i received a loan of $82,000.00 USD and i payed for my husband surgery and thank GOD today he is ok and can walk, my family is happy and i said to myself that i will shout to the world the wonders this great and God fearing Man Mr Martinez Lexie did for me and my family; so if anyone is in genuine and serious need of a loan do contact this GOD fearing man via Email: ( Lexieloancompany@yahoo.com ) or through the Company website: http://lexieloans.bravesites.com OR text: +18168926958 thanks


    ReplyDelete

Note: Only a member of this blog may post a comment.