猜数字游戏8步以内的完全求解决策树生成程序

Python代码 : 猜数字游戏8步以内的完全求解决策树生成程序

001 #coding=utf-8
002
003 #猜数字游戏8步以内的求解决策树生成程序
004 #    解题思路与一步步的解题程序参见：
005 #       http://www.fayaa.com/code/view/116/
006 #
007
008 #使用方法：
009 # 1. 保存代码为guessall.py
010 # 2. 执行python guessall.py > result.txt
011 # 3. 打开result.txt看结果
012
013 #为了可读性和简单性使用了列表推导，其他方法参见：
014 #  http://www.fayaa.com/code/view/114/
015 #  http://www.fayaa.com/code/view/118/
016 def init_set ():
017     r10 = range ( 10 )
018     return [( i , j , k , l )
019             for i in r10 for j in r10 for k in r10 for l in r10
020             if ( i != j and i != k and i != l and j != k and j != l and k != l ) ]
021
022 #对给定的两组数，计算xAyB
023 #不知道能不能更快些
024 def get_match_ab ( target , source ):
025     la , lb = 0 , 0
026     for ( i , t ) in enumerate ( target ):
027         for ( j , s ) in enumerate ( source ):
028             if s == t :
029                 if i == j :
030                     la += 1
031                 else :
032                     lb += 1
033                 #break this loop since we already found match
034                 break
035     return ( la , lb )
036
037 #by lancer
038 #思路很好，把原来的16次比较变成了8次
039 #经过timeit验证确实速度有所提高
040 def get_match_ab2 ( target , source ):
041     table = [ - 1 ] * 10
042     la , lb = 0 , 0
043     for i in xrange ( len ( source )):
044         table [ source [ i ]] = i
045     for i in xrange ( len ( target )):
046         if table [ target [ i ]] == i :
047             la += 1
048         elif table [ target [ i ]] != - 1 :
049             lb += 1
050     return ( la , lb )
051
052 #nums: the number_set list to be checked
053 #guess: last guess
054 #a, b: the number of aAbB
055 #@return: the rest number_sets which matche last guess
056 def check_and_remove ( nums , guess , a , b ):
057     rest_nums = []
058     for num_set in nums :
059         if ( a , b ) == get_match_ab ( num_set , guess ):
060             rest_nums . append ( num_set )
061     return rest_nums
062
063 #计算在nums中选择target以后，所有ab分支里面的剩余组合个数
064 def calc_ab_counts ( target , nums ):
065     #a * 10 + b is used to indicate an "a & b" combination
066     ab_map = {}
067     #init ab_map
068     abs = ( 0 , 1 , 2 , 3 , 4 , 10 , 11 , 12 , 13 , 20 , 21 , 22 , 30 , 31 , 40 )
069     for ab in abs :
070         ab_map [ ab ] = 0
071     #let's do the calculation
072     for num_set in nums :
073         ( a , b ) = get_match_ab ( num_set , target )
074         ab_map [ a * 10 + b ] += 1
075     return [ ab_map [ ab ] for ab in abs ]
076
077 #计算一个选择相对于选择集的“标准差”
078 def calc_standard_deviation ( target , nums ):
079     ab_counts = calc_ab_counts ( target , nums )
080     total = sum ( ab_counts )
081     avg = float ( total ) / len ( ab_counts )
082     sd = sum ([( abc - avg ) ** 2 for abc in ab_counts ])
083     return sd
084
085 #根据现有集合寻找下一个集合
086 #采用“最小标准差”作为衡量标准
087 def next_guess ( nums ):
088     min_sd = 0
089     min_set = ()
090     touched = False
091     for num_set in nums :
092         sd = calc_standard_deviation ( num_set , nums )
093         if not touched or min_sd > sd :
094             touched = True
095             min_set = num_set
096             min_sd = sd
097     return min_set
098
099 #根据现有集合寻找下一个集合
100 #随机选取，会有4-5个超过八次
101 def next_guess2 ( nums ):
102     return nums [ 0 ]
103
104 #折衷的方法：小于500用最小标准差
105 def next_guess3 ( nums ):
106     if len ( nums ) > 500 :
107         return next_guess2 ( nums )
108     else :
109         return next_guess ( nums )
110
111 #计算熵
112 import math
113 def calc_entropy ( target , nums ):
114     ab_counts = calc_ab_counts ( target , nums )
115     total = sum ( ab_counts )
116     hs = []
117     for abc in ab_counts :
118         h = 0
119         if abc :
120             p = float ( abc ) / total
121             h = p * math . log ( p , 2 )
122         hs . append ( h )
123     return sum ( hs )
124
125 #使用信息量作为衡量标准
126 def next_guess4 ( nums ):
127     min_sd = 0
128     min_set = ()
129     touched = False
130     for num_set in nums :
131         sd = calc_entropy ( num_set , nums )
132         if not touched or min_sd > sd :
133             touched = True
134             min_set = num_set
135             min_sd = sd
136     return min_set
137
138 #决策树生成思路
139 #1. 生成所有的四位0-9数字组合，用0123做初始选择，空列表queue=[], result={}
140 #   result: (当前选择, {21:(下一个选择, {})}, 13:abcd<最终结果值>, ...})
141 #   queue: [(rest_nums, 对应当前猜测状态的result节点), ...]
142