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:

Post by Rajputro » Mon Aug 11, 2003 12:03 am

Got it accepted at last. :lol:

Don't know why (str[0][0]==str[1][1]==str[2][2]) was always true :x
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:

Post by Larry » Mon Aug 11, 2003 2:53 am

Make sure it's equal to 'X' or 'O' instead of blanks..?

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Mon Aug 11, 2003 3:11 am

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

Post by dootzky » Sun May 08, 2005 11:05 pm

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

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. 8) :-?

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.

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Mon May 09, 2005 1:05 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:

Post by mf » Mon May 09, 2005 1:43 am

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:

Post by dootzky » Mon May 09, 2005 11:51 am

oh, i see what you mean... :o

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! :P

dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Location: belgrade, serbia (ex yugoslavia)
Contact:

finaly, a good solution!

Post by dootzky » Wed May 11, 2005 7:54 pm

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!

Post by dootzky » Wed May 11, 2005 7:56 pm

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! :D cheers!

User avatar
Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

Extra input/output sample

Post by Jemerson » Tue Jul 19, 2005 6:04 pm

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?

Post by vijay03 » Thu Jan 11, 2007 8:32 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Re: WA?

Post by little joey » Thu Jan 11, 2007 8:55 pm

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:

Post by vijay03 » Sat Jan 13, 2007 12:46 pm

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:

Post by mf » Sat Jan 13, 2007 1:05 pm

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!

Post by vijay03 » Sun Jan 14, 2007 6:31 am

Thanks a lot little joey and mf! Sorry to have bothered u for such a silly error :oops: 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! :D

Post Reply

Return to “Volume 103 (10300-10399)”