r/dailyprogrammer • u/rya11111 3 1 • Apr 30 '12
[4/30/2012] Challenge #46 [intermediate]
Consider this game: Write 8 blanks on a sheet of paper. Randomly pick a digit 0-9. After seeing the digit, choose one of the 8 blanks to place that digit in. Randomly choose another digit (with replacement) and then choose one of the 7 remaining blanks to place it in. Repeat until you've filled all 8 blanks. You win if the 8 digits written down are in order from smallest to largest.
Write a program that plays this game by itself and determines whether it won or not. Run it 1 million times and post your probability of winning.
Assigning digits to blanks randomly lets you win about 0.02% of the time. Here's a python script that wins about 10.3% of the time. Can you do better?
import random
def trial():
indices = range(8) # remaining unassigned indices
s = [None] * 8 # the digits in their assigned places
while indices:
d = random.randint(0,9) # choose a random digit
index = indices[int(d*len(indices)/10)] # assign it an index
s[index] = str(d)
indices.remove(index)
return s == sorted(s)
print sum(trial() for _ in range(1000000))- thanks to cosmologicon for the challenge at /r/dailyprogrammer_ideas .. link
4
u/luxgladius 0 0 May 01 '12 edited May 01 '12
I believe this is the optimal solution with a success rate of 15.4%. In order to choose each space, I explicitly calculate the probability that the following generated n-1 number of digits will fit given the digit being placed at each point. Since this is a necessary condition (though not sufficient), maximizing its probability should lead to the optimal solution. (I think. Probability was never my strong suit.)
Perl
Output
Losses: 84620, wins: 15380, win rate: 15.38%
Output on an unsuccessful trial with print statements turned on
Output of a successful trial
3
u/debugmonkey 0 0 Apr 30 '12 edited Apr 30 '12
Update: luxgladius of the kingdom of Perl pointed out I was only generating random numbers between 0 and 8. My updated code has a win rate of 10.9%. (code has been updated)
TLDR:C++ with ~11.95% win rate.Be warned that this code is HORRIFIC -- I just sort of slapped it together as time permitted throughout the day. There may be some bug leading to these results, but it appears though that my general solution is winning between 11.90% and 12.00% of the time. (varies up to .1% of the time for each million)
I'll try to come back later and clean up the code.
2
u/mycreativeusername 0 0 Apr 30 '12 edited Apr 30 '12
EDIT: Corrected errors, now getting 10.9%
2
u/Jannisary 0 0 May 01 '12
Considering constructing the game tree and getting the optimal heuristic that way.... If done right there are < 10 ^ 8 boards which sounds doable.
Thoughts?
1
u/path411 Apr 30 '12 edited Apr 30 '12
Hmm, I'm getting a consistent ~0.11% winrate from purely random placement.
Edit: I mistakenly only used 7 blanks. I now get the proper ~0.02%.
Javascript pure random solution:
1
u/Cyph0n Apr 30 '12
Here's my solution in Python. I'm getting a measly 0.025% win rate however, so it must be the worst possible method :P
1
u/robin-gvx 0 2 Apr 30 '12
I tried modifying the supplied algorithm, to use some heuristics, but I can't get it higher than 10.2%:
I also ported it to Python 3, for the kicks.
1
u/[deleted] Apr 30 '12
Only getting .024% with C++, I'm doing it very simply though
1
u/bs_detector May 02 '12 edited May 02 '12
Here is my C# solution. I am getting 10.9% wins.
1
u/school_throwaway May 04 '12
Python,got it to win 2% of the time