-
-
Save thuzhf/6669249a397ecf932145dc13133968e0 to your computer and use it in GitHub Desktop.
optimal strategy for drawing a deck of cards
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
# -*- coding: utf-8 -*- | |
import sys,os,json,gzip,math,time,datetime,random,copy | |
from pprint import pprint | |
# x means the color of the last card we drew, can be 'h' or 't' | |
# nh means the number of cards of color 'h' that we drew before x | |
# nt means the number of cards of color 't' that we drew before x | |
# k1, k2 mean the total number of cards of color 'h' and 't' respectively | |
# results is a dict for storing results. Its keys are of form (nh, nt, x) and values are of form [win_rate, 'stop'/'continue'/'either'] | |
def p(nh,nt,x,k1,k2,results): | |
s=k1+k2 | |
if (nh,nt,x) in results: | |
return results[(nh,nt,x)][0] | |
if nh==k1-1 and nt==k2-1: | |
results[(nh,nt,x)]=[0,'stop'] | |
return results[(nh,nt,x)][0] | |
if nt==k2 or nh==k1: | |
results[(nh,nt,x)]=[1,'stop'] | |
return results[(nh,nt,x)][0] | |
if x=='h': | |
tmp1=(k1-nh-1)/(s-nh-nt-1) | |
tmp2=(k1-nh-1)/(s-nh-nt-1) * p(nh+1,nt,'h',k1,k2,results) + (k2-nt)/(s-nh-nt-1) * p(nh+1,nt,'t',k1,k2,results) | |
else: | |
tmp1=(k2-nt-1)/(s-nh-nt-1) | |
tmp2=(k2-nt-1)/(s-nh-nt-1) * p(nh, nt+1, 't', k1, k2, results) + (k1-nh)/(s-nh-nt-1) * p(nh, nt+1, 'h', k1, k2, results) | |
if tmp1 < tmp2: | |
results[(nh,nt,x)]=[tmp2,'continue'] | |
elif tmp1 > tmp2: | |
results[(nh,nt,x)]=[tmp1,'stop'] | |
print(nh,nt,x, results[(nh,nt,x)]) | |
else: | |
results[(nh,nt,x)]=[tmp1,'either'] | |
print(nh,nt,x, results[(nh,nt,x)]) | |
return results[(nh,nt,x)][0] | |
def f(k1,k2): | |
results={} | |
p(0, 0, 'h', k1, k2, results) | |
p(0, 0, 't', k1, k2, results) | |
return results | |
def main(): | |
r=f(26,26) | |
with open('tmp.txt', 'w') as fout: | |
pprint(r,stream=fout) | |
if __name__ == '__main__': | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment