import random
from itertools import izip, imap
from math import log
digits = 4
trials = 100
fmt = '%0' + str(digits) + 'd'
searchspace = tuple([tuple(map(int,fmt % i)) for i in range(0,10**digits)])
def compare(a, b, imap=imap, sum=sum, izip=izip, min=min):
count1 = [0] * 10
count2 = [0] * 10
strikes = 0
for dig1, dig2 in izip(a,b):
if dig1 == dig2:
strikes += 1
count1[dig1] += 1
count2[dig2] += 1
balls = sum(imap(min, count1, count2)) - strikes
return (strikes, balls)
def rungame(target, strategy, verbose=True, maxtries=15):
possibles = list(searchspace)
for i in xrange(maxtries):
g = strategy(i, possibles)
if verbose:
print "Out of %7d possibilities. I'll guess %r" % (len(possibles), g),
score = compare(g, target)
if verbose:
print ' ---> ', score
if score[0] == digits:
if verbose:
print "That's it. After %d tries, I won." % (i+1,)
break
possibles = [n for n in possibles if compare(g, n) == score]
return i+1
############################################### Strategy support
def info(seqn):
bits = 0
s = float(sum(seqn))
for i in seqn:
p = i / s
bits -= p * log(p, 2)
return bits
def utility(play, possibles):
b = {}
for poss in possibles:
score = compare(play, poss)
b[score] = b.get(score, 0) + 1
return info(b.values())
def hasdup(play, set=set, digits=digits):
return len(set(play)) != digits
def nodup(play, set=set, digits=digits):
return len(set(play)) == digits
################################################ Strategies
def s_allrand(i, possibles):
return random.choice(possibles)
def s_trynodup(i, possibles):
for j in xrange(20):
g = random.choice(possibles)
if nodup(g):
break
return g
def s_bestinfo(i, possibles):
if i == 0:
return s_trynodup(i, possibles)
plays = random.sample(possibles, min(20, len(possibles)))
_, play = max([(utility(play, possibles), play) for play in plays])
return play
def s_worstinfo(i, possibles):
if i == 0:
return s_trynodup(i, possibles)
plays = random.sample(possibles, min(20, len(possibles)))
_, play = min([(utility(play, possibles), play) for play in plays])
return play
def s_samplebest(i, possibles):
if i == 0:
return s_trynodup(i, possibles)
if len(possibles) > 150:
possibles = random.sample(possibles, 150)
plays = possibles[:20]
elif len(possibles) > 20:
plays = random.sample(possibles, 20)
else:
plays = possibles
_, play = max([(utility(play, possibles), play) for play in plays])
return play
## Evaluate Strategies
def average(seqn):
return sum(seqn) / float(len(seqn))
def counts(seqn):
limit = max(10, max(seqn)) + 1
tally = [0] * limit
for i in seqn:
tally[i] += 1
return tuple(tally[1:])
from time import clock
print '-' * 60
##for ss in searchspace, filter(hasdup, searchspace), filter(nodup, searchspace):
## print 'spacesize:', len(ss), ' = ', log(len(ss),2), 'bits'
##for play in [(1,2,3,4,5), (1,1,2,3,4), (1,1,1,2,3), (1,1,2,2,3), (1,1,1,2,2)]:
## print 'First play:', play, 'has info content', utility(play, searchspace)
## print 'First play:', play, 'has info content', utility(play, filter(hasdup, searchspace)), 'against dups'
## print 'First play:', play, 'has info content', utility(play, filter(nodup, searchspace)), 'against nodups'
## print
for strategy in (s_bestinfo, s_samplebest, s_worstinfo, s_allrand, s_trynodup, s_bestinfo):
start = clock()
data = [rungame(random.choice(searchspace), strategy, verbose=False) for i in xrange(trials)]
#print '[%d %d| median %.2f mean %.2f |%d %d] dig=%d n=%d %s' % (min(data), lq(data), median(data),average(data), uq(data), max(data), digits, len(data), strategy.__name__)
print 'mean=%.2f %r %s n=%d dig=%d' % (average(data), counts(data), strategy.__name__, len(data), digits)
print 'Time elapsed %.2f' % (clock() - start,)
""" Analysis of strategies with four digit targets
s_worstinfo [3 | median 7.00 mean 6.76 | 10] n=120
s_allrand [3 | median 6.00 mean 6.19 | 9] n=120
s_firstnodup [3 | median 6.00 mean 6.24 | 9] n=120
s_trynodup [3 | median 6.00 mean 5.99 | 9] n=120
s_bestinfo [2 | median 6.00 mean 5.75 | 10] n=120
s_worstinfo [3 | median 7.00 mean 6.86 | 10] n=200
s_allrand [4 | median 6.00 mean 6.52 | 10] n=200
s_firstnodup [1 | median 6.00 mean 6.19 | 10] n=200
s_firstdup_restnodup [3 | median 6.00 mean 6.13 | 10] n=200
s_trynodup [3 | median 6.00 mean 6.11 | 10] n=200
s_bestinfo [2 | median 6.00 mean 5.73 | 9] n=200
[3 6| median 7.00 mean 6.78 |8 11] dig=4 n=200 s_worstinfo 6.77
[3 5| median 6.00 mean 6.24 |7 10] dig=4 n=200 s_allrand 6.38
[2 6| median 6.00 mean 6.26 |7 9] dig=4 n=200 s_firstnodup 6.22
[2 5| median 6.00 mean 5.93 |7 9] dig=4 n=200 s_firstdup_restnodup 6.03
[4 5| median 6.00 mean 6.14 |7 9] dig=4 n=200 s_trynodup 6.12
[3 5| median 6.00 mean 5.87 |6 9] dig=4 n=200 s_bestinfo 5.74
[1 6| median 7.00 mean 6.93 |8 11] dig=4 n=500 s_worstinfo
[2 5| median 6.00 mean 6.11 |7 10] dig=4 n=500 s_allrand
[3 5| median 6.00 mean 6.12 |7 10] dig=4 n=500 s_firstnodup
[2 5| median 6.00 mean 6.07 |7 10] dig=4 n=500 s_firstdup_restnodup
[2 5| median 6.00 mean 6.03 |7 9] dig=4 n=500 s_trynodup
[2 5| median 6.00 mean 5.82 |6 9] dig=4 n=500 s_bestinfo
[2 5| median 6.00 mean 5.82 |6 9] dig=4 n=500 s_bestinfo_randfirst
spacesize: 100000 = 16.6096404744 bits
spacesize: 69760 = 16.0901124197 bits
spacesize: 30240 = 14.8841705191 bits
First play: (1, 2, 3, 4, 5) has info content 2.72731327592
First play: (1, 2, 3, 4, 5) has info content 2.54363363003 against dups
First play: (1, 2, 3, 4, 5) has info content 2.77115216576 against nodups
First play: (1, 1, 2, 3, 4) has info content 2.57287940403
First play: (1, 1, 2, 3, 4) has info content 2.51059435464 against dups
First play: (1, 1, 2, 3, 4) has info content 2.56508152257 against nodups
First play: (1, 1, 1, 2, 3) has info content 2.16683284403
First play: (1, 1, 1, 2, 3) has info content 2.11526590293 against dups
First play: (1, 1, 1, 2, 3) has info content 2.13291456398 against nodups
First play: (1, 1, 2, 2, 3) has info content 2.28656723529
First play: (1, 1, 2, 2, 3) has info content 2.28606417747 against dups
First play: (1, 1, 2, 2, 3) has info content 2.14424289741 against nodups
First play: (1, 1, 1, 2, 2) has info content 2.16683284403
First play: (1, 1, 1, 2, 2) has info content 2.11526590293 against dups
First play: (1, 1, 1, 2, 2) has info content 2.13291456398 against nodups
mean=6.22 (0, 0, 0, 4, 33, 130, 72, 9, 2, 0) s_samplebest n=250 dig=5
Time elapsed 1395.75
"""
