| Submit | All submissions | Best solutions | Back to list |
OVOXO - Tic-tac-toe 3 |
Bored to death working at the Byteland Office...your colleagues have resorted to game of crosses Xs and noughts Os or Tic-tac-toe. One of them keeps on losing and is tired of the jokes. He plans to have an Android app in his phone to help him out. He is your good friend and seeks your assistance. "Treat at ANC is guaranteed", he says.
He also is very frugal when it comes to memory usage. So please don't write a long if else chain... because you have to do the task within 999 bytes.
Input
An integer T - the number of test cases. (T < 1000). T test cases follow.
Each test case comprises 3 strings each separated by newline and containing exactly 3 characters (either 'X','O' or '_') per line. An empty line follows each test case. Each input position is guaranteed to be a valid tic-tac-toe position such that the game is still not over.
Output
For each test case print "WON" if it is a sure shot winning position, else print "CONTINUE". Then output the game after having made your move. If more than one move are equally good try playing the move on the first empty spot.
Example
Input: 2 OOX OX_ __X XX_ XOO _O_ Output: WON OOX OXX __X WON XXX XOO _O_
Info
- X always moves first (it is the standard) and whose move it currently is can be computed.
- Winning position is meant for the current player.
- Winning in fewer moves is better, and drawing is better than losing as in general AI.
- You need to print the board as it looks after making the best move.
- Print WON if the current player can win in the case when both players play optimally from here on.
| Added by: | Aditya Pande |
| Date: | 2013-01-14 |
| Time limit: | 1s |
| Source limit: | 999B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | TOE2 |
hide comments
|
|||||
|
2016-02-03 04:39:56 [Rampage] Blue.Mary
Thanks very much :D. BTW, output WON not WIN. |
|||||
|
2015-09-06 00:33:03 :D
Summary of rules confirmed by AC solution: 1) 'X' always starts. 2) The field in the input is a valid unfinished game, but it could results from sub-optimal plays. 3) You look for an optimal play for the player making the next move. 4) Win, draw, loss mean certain results after next move assuming optimal play from that point. You print "WON" for Win start and "CONTINUE" for draw and loss. 5) In terms of optimal plays: Win > Draw > Loss. Winning in lesser number of moves is better. Draw or Loss in greater number of moves is better. 6) In case of the same quality moves pick top-most row and left-most field in that row. Last edit: 2020-04-11 18:03:52 |
|||||
|
2013-01-19 05:58:00 Aditya Pande
@mitch: my mistake forced win in 3 moves is possible... Also I have added a few stronger test cases...and rejudged all submissions Last edit: 2013-01-19 05:53:13 |
|||||
|
2013-01-19 05:58:00 Mitch Schwartz
Ok thanks for clarifying Robert and Aditya, but you gave slightly different rules, so it seems likely the test data is weak! Based on Aditya's rules, we should then also prefer a 2-move loss over a 1-move loss (and so on), is that right? This is not "standard", it's just one possible definition of what constitutes optimal play. Another entirely acceptable definition is to treat all winning moves (for example) as equally good, regardless of how long it takes to get there. It's an interesting twist, and I'm examining my approach to see whether it can be modified accordingly. Although I get the feeling I'm analysing the problem more carefully than the problem setter did. :P Edit: Well, I got AC under the assumption that in a winning position we try to win as fast as possible, and in a losing or drawn position we try to lose/draw as slowly as possible. --> The test cases are weak. I agree and I will add stronger ones ...but not now... Hope the problem did make you think....:) --->Edit( ADITYA ):- Draw cannot be fast or slow... Yes you're right, in this game draw can't be fast or slow, anyway in my implementation the piece of code that deals with it handles case of draw and lose simultaneously. Last edit: 2013-01-18 08:45:49 |
|||||
|
2013-01-19 05:58:00 Mitch Schwartz
Description not really clear. (1) Is it guaranteed always to be X's move? (2) If not: Does "winning position" mean winning for the person whose turn it is now, or winning for X? (3) "equally good" is not defined -- is winning in 1 move considered better than winning in 2 moves, or are they equal? Robert Gerbicz also commented about this, but I can't tell from his comment which option we are required to print. (4) If it is not a winning position, do we still need to choose and print the next move? And if so, presumably we should choose a drawing move over a losing move? Also, I think it's an easier version of MYQ8. :p ans (Gerbicz): X is the first player in every game (this is the standard tic-tac-toe), but it is possible that the current turn is for the "O" player. (2) print WON, if it is winning for the current player, who takes the move. (3) Winning in 1 move is better than winning in 2 or more moves. But going higher this is not true, so say winning in 2 moves is NOT better than winning in 3 moves. (4) Choose (and print!) the better move so for example the drawing move over the losing move. And in these cases still choose the first such move. Edit( ADITYA ): @Robert thank you for the explanation @Mitch: sorry for the ambiguity 1) it is the standard and whose move it currently is can be computed... 2) winning position is meant for the current player 3) winning in lesser number of moves is better and drawing is better than losing as in general AI 4) you need to print the board as it looks after making the best move 5) print WIN if the current player can win in the case when both players play optimally from here on... also MYQ8 seems much easier than this... if nothing comes to the mind, it can be solved by a long chain of if else... i shall try it later :p Last edit: 2013-01-19 05:45:21 |
|||||
|
2013-01-19 05:58:00 Robert Gerbicz
When should we print "WON"? I print when there is a winning move and after it the game is over. And in this case I choose the move that comes first. Is it a correct interpretation? -->no ( if a win can be forced print WON) --->congrats you are the first one to solve it... Last edit: 2013-01-14 18:37:24 |
|||||
RSS