Welcome, guest | Sign In | My Account | Store | Cart
```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

"""
```

### History

• revision 2 (11 years ago)
• previous revisions are not available