## 10363 - Tic Tac Toe

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Rajputro
New poster
Posts: 6
Joined: Fri Jan 10, 2003 4:19 pm
Location: Dhaka,Bangladesh
Contact:
Got it accepted at last.

Don't know why (str[0][0]==str[1][1]==str[2][2]) was always true
And that was my problem
Can anybody say why?
Thank You.
-->Shafi

" Rajputro has spoken. "
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Make sure it's equal to 'X' or 'O' instead of blanks..?
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Assuming the characters are still 'X' 'O' and '.' .. the expression x==y==z should always be false, since the first boolean expression will evaluate to 0 or 1, and that will never equal the character in z.

Of course, if you made your 'X's 'O's and blanks to 0s, 1s, and 2s, then it may or may not be true. But it's still not what you would want to write.
dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Location: belgrade, serbia (ex yugoslavia)
Contact:

### 10363

OMG OMG OMG!!
why doesn't this work?!

it's very very simple:

1) check if number of "X" is equal or 1 bigger from number of "O"
2) check if somebody wins. if they both win - print "no". else print "yes".

so, if 1), go to 2), and 2) is really simple.

it's not really importan if X or O has 1 or more WIN situations, because, if X wins, with two possitions:

XXX
XOO
XOO

the condition 1) will be ok, and this IS really ok situation
BUT, if the board is:
XXX
OOO
XXX
number of X is bigger then number of O by 2, therefore, the condition 1) will not pass!! so the answer is "no".

why doesn't this work??

maybe i'm handling INPUT wrongly?!?!
anyway, here's my code, hope somebody gives me a test run, or some usefull input/output, and prove me wrong.

Code: Select all

``````code removed, thank GOD!
``````
cheers guys,
greetz,
dootzky
Last edited by dootzky on Wed May 11, 2005 7:55 pm, edited 1 time in total.
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
Did you consider that only the player that moved last can be in a winning position?

Ex:

Code: Select all

``````2
OO.
O..
XXX

XX.
XX.
OOO

no
no``````
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Hi, dootzky. Actually, your algorithm is wrong. I found 412 counter-examples by exhaustive search.

To name a few,

Code: Select all

``````..X
.XO
XOO

..X
.OX
OOX

..X
O.X
OOX

.XX
OOO
XX.

OOO
XX.
XX.``````
dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Location: belgrade, serbia (ex yugoslavia)
Contact:
oh, i see what you mean...

my bad, my bad. it was late, and i was so sure i got it right.

anyhow, i corrected my algorithm now, and this is how i check the table:

1) if they both win - NO - break;
2) if X wins && (numberO+1 == numberX) - YES - else NO; break;
3) if O wins && (numberO == numberX) - YES - else NO; break;
4) if nobody wins, if (numberO == numberX) || (numberO+1 == numberX) - YES - else NO - break;

but i still get WA?
did i miss something, again?

i can post the new code here, but i think it will be more of distraction then some real debug help.

thx guys for your quick replys!
greetzs,
dootzky

p.s. i tested my new algo on both of yours sample input/output, and now it works fine!
dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Location: belgrade, serbia (ex yugoslavia)
Contact:

### finaly, a good solution!

this is how i solved the problem, after 9 WA.

Code: Select all

``````	if ( X && O ) goto no;
if ( X && (a==b+1) ) goto yes;
if ( X && (a!=b+1) ) goto no;
if ( O && (a==b) ) goto yes;
if ( O && (a!=b) ) goto no;
if ( (a==b) || (a==b+1) ) goto yes; else goto no;

// check out
yes:  cout << "yes"; goto end;

no:   cout << "no"; goto end;

end: cout << "\n";
``````
where "bool X" is test for X win, "bool O" is test for O win, "int a" is number of X, and "int b" is number of O.

i used "goto command" just so i wouldn't have to use "break" or something like that. bottom line - i lost way too much nervs on very easy problem.

this was no fun at all.

anyway, i hope i helped somebody with this "algo",
best regards,
dootzky
dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Location: belgrade, serbia (ex yugoslavia)
Contact:

### FINALY!

this is how i solved the problem, after 9 WA.

Code: Select all

``````	if ( X && O ) goto no;
if ( X && (a==b+1) ) goto yes;
if ( X && (a!=b+1) ) goto no;
if ( O && (a==b) ) goto yes;
if ( O && (a!=b) ) goto no;
if ( (a==b) || (a==b+1) ) goto yes; else goto no;

// check out
yes:  cout << "yes"; goto end;

no:   cout << "no"; goto end;

end: cout << "\n";
``````
where "bool X" is test for X win, "bool O" is test for O win, "int a" is number of X, and "int b" is number of O.

i used "goto command" just so i wouldn't have to use "break" or something like that. bottom line - i lost way too much nervs on very easy problem.

this was no fun at all.

anyway, i hope i helped somebody with this "algo",
best regards,
dootzky

p.s. thx to you fella's, you helped! cheers!
Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

### Extra input/output sample

Extra Input/Output sample for helping people

Input:

Code: Select all

``````8
XX.
XX.
OOO

XX.
...
OOO

OX.
OX.
OX.

X..
OXO
OXX

X..
OXO
O.X

XXO
.OX
O..

XXO
.OX
O.X

XXX
X00
...
``````
Output:

Code: Select all

``````no
no
no
yes
no
yes
no
no
``````
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!
vijay03
New poster
Posts: 33
Joined: Wed Sep 13, 2006 6:46 pm
Contact:

### WA?

My program runs perfectly on my comp and gives correct output for the all the inputs given on this forum. Yet i get WA. Here is my code:

Code: Select all

``````
Cut after ACC

``````
I`ve used the logic suggested by someone here. Am i missing something very obvious?
Last edited by vijay03 on Sun Jan 14, 2007 12:08 pm, edited 1 time in total.
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### Re: WA?

Code: Select all

``````<SNIP>
else if((no==nx)||(nx=no+1))
printf("yes\n");
<SNAP>
``````
Looks suspect
Haven't looked at all of your code...
vijay03
New poster
Posts: 33
Joined: Wed Sep 13, 2006 6:46 pm
Contact:
dootzky wrote:this is how i solved the problem, after 9 WA.

Code: Select all

``````	if ( X && O ) goto no;
if ( X && (a==b+1) ) goto yes;
if ( X && (a!=b+1) ) goto no;
if ( O && (a==b) ) goto yes;
if ( O && (a!=b) ) goto no;
if ( (a==b) || (a==b+1) ) goto yes; else goto no;

// check out
yes:  cout << "yes"; goto end;

no:   cout << "no"; goto end;

end: cout << "\n";
``````
where "bool X" is test for X win, "bool O" is test for O win, "int a" is number of X, and "int b" is number of O.

dootzky
I merely used dootzky`s algorithm.. Instead of goto i used a if then else construct to achieve the same effect
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
You have an assignment operator instead of comparison in "else if((no==nx)||(nx=no+1))".
vijay03
New poster
Posts: 33
Joined: Wed Sep 13, 2006 6:46 pm
Contact:

### Thanks a lot!

Thanks a lot little joey and mf! Sorry to have bothered u for such a silly error It never struck me to check the conditions themselves as i was getting correct output for all the input.. I thought i was missing a condition. Thanks a lot!