hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
Tic Tac Blah
Goto page 1, 2, 3  Next
 
Reply to topic    hacker.org Forum Index » Challenges View previous topic
View next topic
Tic Tac Blah
Author Message
bass



Joined: 02 Jul 2007
Posts: 6

Post Tic Tac Blah Reply with quote
I don't seem to be able to solve the Tic Tac Blah challenge, so please tell me whether I have made a mistake, or if there is a mistake in the challenge itself. Here's my reasoning, which produced the non-accepted answer:

A win will not turn into a draw by further plays, so any won game can be continued until the board is filled. There are exactly M (no solutions on the forum, you said) distinct patterns which fill the tic-tac-toe board with an O in the middle and four of both Os and Xs elsewhere. Every one of these patterns can be reached in an equal number of ways, since there are equally many Xs and Os, and there are no symmetry considerations to take into account. As the players play randomly, this means that every pattern is equally probable.

Now, counting that out of these M possible patterns exactly N are draws, the probability of a draw should be exactly N/M.

As my final attempt(s) a couple of minutes ago I submitted the result as a fraction, in case you want to check against my making a silly rounding error or some other likely idiocy.

Cheers,

-bass
Thu Jun 05, 2008 12:04 am View user's profile Send private message
adum



Joined: 19 Apr 2007
Posts: 391

Post Reply with quote
i think your reasoning is slightly off: you have to put the _first_ move in the center.

i'm pretty confident the challenge is correct because bok independently solved it without issue.

cheers,
adum
Thu Jun 05, 2008 12:12 am View user's profile Send private message Visit poster's website
adum



Joined: 19 Apr 2007
Posts: 391

Post Reply with quote
PS: please submit as decimal -- i just check with a string compare, so a fraction won't get computed
Thu Jun 05, 2008 12:12 am View user's profile Send private message Visit poster's website
bass



Joined: 02 Jul 2007
Posts: 6

Post Reply with quote
[quote="adum"]
i'm pretty confident the challenge is correct because bok independently solved it without issue.
[/quote]

That's what I thought too. So I programmed it another way, to see where I went wrong. No help, still got the same result, (now with an extra factor of 576 in both the numerator and the denominator. And yes, I do submit in decimal. :-)

Then I tried the trick of trying to explain my program to an imaginary someone, but even THAT did not help, so my choices are down to a) trying to guess where two people might make the same error and attempt to reproduce it, or b) email you my (now recoded, polished and thoroughly commented) solver, so you can just point at it and say "silly bass, you make a mistake on line 2!". (which I intentionally left empy, so the joke is on you! ha!)

Cheers,

-bass
Thu Jun 05, 2008 5:45 pm View user's profile Send private message
adum



Joined: 19 Apr 2007
Posts: 391

Post Reply with quote
i will quietly note that bass has now solved this challenge =)

adum
Thu Jun 05, 2008 10:21 pm View user's profile Send private message Visit poster's website
bass



Joined: 02 Jul 2007
Posts: 6

Post Reply with quote
[quote="adum"]i will quietly note that bass has now solved this challenge =)

adum[/quote]

Nearly silently I'll add that I'd never have found the required answer without the additional information that two people have independently reached the same result :-)
Mon Jun 09, 2008 8:51 pm View user's profile Send private message
adum



Joined: 19 Apr 2007
Posts: 391

Post Reply with quote
i will also note that bass was right, i was wrong, and i've updated the challenge text Very Happy

adum
Mon Jun 09, 2008 8:55 pm View user's profile Send private message Visit poster's website
therethinker



Joined: 28 Mar 2008
Posts: 144
Location: #hacker.org on Freenode

Post Reply with quote
I'm still having trouble with the challenge, and the added text just confused me.

Could you explain more? I can't figure out a difference between the two descriptions.
Mon Jun 09, 2008 11:18 pm View user's profile Send private message AIM Address
adum



Joined: 19 Apr 2007
Posts: 391

Post Reply with quote
in short, you want to divide the number of draws by the number of possible games.

the original description technically asked for something else, which is how likely a draw will be with both players playing randomly. the reason this is different is some games end earlier with a win, so they're more likely.

adum
Tue Jun 10, 2008 12:45 am View user's profile Send private message Visit poster's website
Allosentient



Joined: 10 Apr 2008
Posts: 273

Post Reply with quote
I still do not understand this problem or am doing it wrong. I am searching through all possible move combinations (starting with 8 possible moves excluding center). I do not count moves that occur after a win (though I have tried counting all moves including moves made after a win and still not getting anything).

All decimal points I have tried have not worked (I have included a trailing 0 to the left of the decimal, and have rounded to 8 decimal places).

I probably have a flaw somewhere, but if someone could point me in the right direction that would be great.
Fri Jun 13, 2008 7:46 pm View user's profile Send private message
bok
Site Admin


Joined: 30 Jan 2007
Posts: 24

Post Reply with quote
I've looked at the answers you've submitted, and I can tell you that they are not being rejected because of a rounding error or a syntax issue. The values are pretty far off.
Maybe I can try to give an example to clarify what's being asked:
The first player plays in the center. After that, the second player plays randomly (in one of the 8 free positions), then the first player plays randomly (in one of the 7 remaining locations), etc... until one player wins, or the board is full (draw). Compute how many different ways there are to get to a draw, and divide by how many ways there are to get to any end of game. That's your solution.

So far, 5 people have found the correct solution independently, so it is safe to say that there is a 'common' understanding of what the required answer is.
Sat Jun 14, 2008 8:27 am View user's profile Send private message Send e-mail
Allosentient



Joined: 10 Apr 2008
Posts: 273

Post Reply with quote
hmm, I have tried doing that. There must be a bug in my program. Thank you everyone who gave advice.

By the way, I am at the very last challenge, and I can't believe it is even possible to do what you are asking (you guys really come up with some brilliant things). I am sure gonna lose a lot of sleep on this one!
Sat Jun 14, 2008 9:02 am View user's profile Send private message
sky



Joined: 06 Jun 2008
Posts: 17

Post Two advices Reply with quote
A pair of errors that made me waste too much time:
1) Be sure you are posting the floating point with a "." not a "," .It will sound like a joke but the first version of the ruby program i wrote to solve the problem gave as output the number in "fraction form", i made the floating point conversion with the gnome calculator and its output was a fp with a "," . The funny thing is that the answer was right but i didn't realize what the problem was Laughing

2) Endgames have to be counted with the right multiplicity Razz I mean that there can be two or more (many in fact) different games that end in the same way. Those games should be counted as different

Ps.: yes, after the lame thing of the ","-floating point i thought that maybe the order should count but i got negative response even in that case, so i smashed my head against a wall until god blessed me with the solution
Sat Jun 14, 2008 3:40 pm View user's profile Send private message
YesItsMe



Joined: 06 Nov 2008
Posts: 1

Post description misleading Reply with quote
i solved this challenge, but found the description misleading as the note in parenthesis seems to describe exactly the number that solved it.

this is how i would describe what's asked for:
d = Number of possible draws starting with the first move in the center.
g = Possible games (incuding draws) starting with the first move in the center.

solution: d/g
Wed Nov 12, 2008 11:00 pm View user's profile Send private message
samc



Joined: 20 Aug 2009
Posts: 4

Post also found description misleading Reply with quote
Let:
d = number of draws where player 1 starts in center
gc = number of possible games where player 1 starts in center
g = number of all possible games (regardless of where player 1 starts)

I interpreted "What fraction of all possible games are draws? (Note: that means something different from what fraction of random games played from this point would be draws.)" to mean d/g whereas the answer is actually d/gc.
Sun Aug 23, 2009 11:48 pm View user's profile Send private message
Display posts from previous:    
Reply to topic    hacker.org Forum Index » Challenges All times are GMT
Goto page 1, 2, 3  Next
Page 1 of 3

 
Jump to: 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group
Design by Freestyle XL / Flowers Online.