1. Problems
  2. classical
  3. Ada and TicTacToe
  1. Status
  2. Ranking

ADAQUBIC - Ada and TicTacToe

#dynamic-programming #game-theory-1 #optimization

Ada the Ladybug was playing 3D Tic-Tac-Toe against her good friend Velvet Mite Vinit. They were playing on 3x3x3 field. Sadly, Vinit had to go home earlier so the game was left unfinished. Ada wants to know who would win the match (if they both played optimally). You also know that Ada started.

Input

The first line contains a single integer 1 ≤ T ≤ 1000, number of test-cases.

Each test-case will contain 9 lines with three character each, representing the field ('.' for empty place, 'x' for move of Ada and 'o' for move of Vinit). You are assured that the game is unfinished and valid.

First three lines represent the top field, the next three lines represent middle field and the last three lines represent the bottom field.

There will be a blank line before each test-case.

Output

For each test-case, print the name of winner (Ada or Vinit);

Example Input

7

..o
o.x
xox
x.x
...
x.o
...
o.o
.x.

.x.
...
..o
o.x
x..
..o
..x
...
...

o..
...
o.x
.x.
...
.x.
o.o
.xx
oox

..x
..x
.o.
..x
..x
xo.
o..
..o
...

...
..x
..x
.o.
..x
o..
...
...
x.o

...
..x
..o
...
...
xo.
ox.
...
.ox

o..
x..
...
oxx
..o
.ox
..o
.x.
.x.

Example Output

Vinit
Vinit
Ada
Vinit
Ada
Vinit
Vinit

Example Input 2

1

xox
x.o
oox
o.o
x.x
xxo
x.o
oxo
ox.

Example Output 2

Ada
Submit solution!
hide comments
morass: 2018-11-06 17:00:08

@:D

Good day to you,

sorry for late reply - and thank you.

Mine best was "0.430000" on a test-case :'(

And your assumption is right: I can't prove it myself too (well unless brute-force everything - so basically I can :D ), but there are multiple articles which do so! Well in fact, there is some much more general proof: For size AND dimension :)

Have nice day ^_^
:D: 2018-10-23 20:43:55

I assume the draw is impossible in this game variant. I didn't analyze this aspect properly.

Phenomenal problem. One of the best coding experiences I had on SPOJ. There's a lot of room for various approaches and adding different heuristics for performance gain. It rewards good program planning. It was also interesting trying to code generic methods that would also be applicable to other tic-tac-toe game variants.

Now I will probably try to optimize my program somewhat. For reference Miloslav, what is the total time for your solution?
EDIT: Ok, I think it's optimized enough :)

Last edit: 2018-10-24 02:53:22
stcsteven: 2017-09-19 02:12:29

@morass: hmm... thanks for the brief explanation man.. hahaha it is really helpful :D
morass: 2017-09-19 00:22:04

@stcsteven: This one?

...
..x
..x

.o.
..x
o..

...
...
x.o

Well Vinit ('o') is on move, but he can't win in one turn... anyway Ada ('x') is attacking on two places (top-right-column) and right-middle on all three levels (top-middle-botom):

a)

..!
..X
..X

.o.
..x
o..

...
...
x.o

b)

..!
..X
..x

.o.
..X
o..

...
..!
x.o

Does it seem valid? (Big X + ! are those attacking positions).

Well to the "middle" - yes, it is indeed a very good strategical position, since it has highest number of triples going through it. Nevertheless as some of the moves are already on, it might not always be optimal (you might have to defend OR you could have better "attack" option)

~/Morass
stcsteven: 2017-09-18 19:09:16

@morass: Woww. Thank you for the clarification hahaha... I was wandering if thy code really make it, but I guess my logic takes too long :/ . My basic idea is that making in 2d before expanding to 3d tic tac toe.

EDIT: By the way, is the test case number 5 correct? The player who controls the center wins the game right?

Last edit: 2017-09-18 19:32:21
morass: 2017-09-18 18:29:33

@stcsteven: Good day to you,

Well I agree, but at the moment (if I'm not mistaken) Vinit is on the move.

Ada has started and made 7 moves already. Vinit made only 6, so it is his turn now.

If I made i mistake or there is an ambiguity in statement, please tell me!

Thnax

Good Luck & Have Nice Day ^_^
stcsteven: 2017-09-18 17:07:59

Can you explain about the winning condition in this 3x3x3 tic tac toe game?
If the winning condition is by making any 3 objects straight horizontally, vertically or diagonally in either one board or multi-board, there is a flaw in the first test case in which Ada can win directly.
The explanation for the first test case:
. . o
o.x
xox

x.x
. . .
x.o

. . .
o.o
. x .

Then Ada can put another x at the center of board 2. Even when the center of board 2 is closed, Ada has 2 other alternatives in winning the game just relying on board 2.

Last edit: 2017-09-18 17:14:21

Added by:Morass
Date:2017-09-17
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.