Skip to content

Instantly share code, notes, and snippets.

@thuzhf

thuzhf/tmp.py Secret

Last active January 22, 2018 13:06
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save thuzhf/6669249a397ecf932145dc13133968e0 to your computer and use it in GitHub Desktop.
Save thuzhf/6669249a397ecf932145dc13133968e0 to your computer and use it in GitHub Desktop.
optimal strategy for drawing a deck of cards
#!/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