代码
比这篇新的文章:
PolicyKit SetTimeZone Demo
比这篇旧的文章: test
作者: 半瓶墨水, 点击916次, 评论(10), 收藏者(1)
打分:
所有评论，共10条：( 我也来说两句)
比这篇旧的文章: test
猜数字游戏8步以内的完全求解决策树生成程序
语言: Python, 标签: 猜数字 2008/06/23发布 4个月前更新 更新记录作者: 半瓶墨水, 点击916次, 评论(10), 收藏者(1)
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 #2. 把组合集与初始选择作为元组(rest_nums, [(0,1,2,3)], ())追加到queue
143 #3. 从queue头部取出一个元组(并从queue中删除之)
144 #4. 对该元组的最新guess(guess列表最后一个)，遍历十五种xAyB组合：
145 #5. 对每一种xAyB组合，删除rest_nums里面不符合的组合，得到新的rest_nums
146 # 如果新rest_nums长度：
147 # a. 为0: 什么也不干
148 # b. 为1: 则
149 # b1. 如果xAyB是4A0B，什么也不干
150 # b2. 否则，在result_set的映射(第二个元素)中添加映射xy:rest_nums[0]
151 # c. 如果结果长度大于1
152 # c1. 在queue的最后面添加(rest_nums, (当前猜测, {})
153 #5. 重复3,4，直到queue为空
154 #6. 以一种非常漂亮的方式打印result
155 def make_decision_tree():
156 from Queue import Queue
157 result = ((0, 1, 2, 3), {})
158 queue = Queue()
159 rest_nums = init_set()
160 queue.put((rest_nums, result))
161 #all xAyB set
162 abs = [(a, b) for a in range(5) for b in range(5 - a)]
163 while not queue.empty():
164 (rest_nums, (guess, mapping)) = queue.get()
165 for (a, b) in abs:
166 new_rest_nums = check_and_remove(rest_nums, guess, a, b)
167 length = len(new_rest_nums)
168 if length == 1:
169 if a != 4: #b can't be other than 0 when a == 4
170 mapping[a * 10 + b] = new_rest_nums[0]
171 elif length > 1:
172 new_guess = next_guess4(new_rest_nums) #TODO: 替换guess函数调整算法
173 new_result = (new_guess, {})
174 mapping[a * 10 + b] = new_result
175 queue.put((new_rest_nums, new_result))
176 return result
177
178 max_level = 0
179 level7_plus_tups = []
180 def pprint_result(result, level = 0):
181 global max_level, max_level_tup
182 (tup, mapping) = result
183 print tup
184 level += 1
185 if level > max_level:
186 max_level = level
187 if len(mapping) == 0:
188 print
189 else:
190 for key in mapping:
191 val = mapping[key]
192 #打印前缀
193 print u"%d|\t" * level % tuple(range(1, level + 1)),
194 print u"%d:" % (level + 1),
195 #打印xAyB
196 print u"%dA%dB" % (key / 10, key % 10),
197 if len(val) == 4: #direct result
198 #打印结果
199 print val
200 if level >= 7:
201 level7_plus_tups.append((level, val))
202 else:
203 pprint_result(val, level)
204
205 #来玩玩
206 print u"Notice: 4A0B is NOT included, since it result to Game Over"
207 pprint_result(make_decision_tree())
208 print
209 print u"max level is:", max_level + 1
210 print u"level7 plus tuples:"
211 for (level, tup) in level7_plus_tups:
212 print u"level:", level + 1, u"\ttup:", tup
213 print
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 #2. 把组合集与初始选择作为元组(rest_nums, [(0,1,2,3)], ())追加到queue
143 #3. 从queue头部取出一个元组(并从queue中删除之)
144 #4. 对该元组的最新guess(guess列表最后一个)，遍历十五种xAyB组合：
145 #5. 对每一种xAyB组合，删除rest_nums里面不符合的组合，得到新的rest_nums
146 # 如果新rest_nums长度：
147 # a. 为0: 什么也不干
148 # b. 为1: 则
149 # b1. 如果xAyB是4A0B，什么也不干
150 # b2. 否则，在result_set的映射(第二个元素)中添加映射xy:rest_nums[0]
151 # c. 如果结果长度大于1
152 # c1. 在queue的最后面添加(rest_nums, (当前猜测, {})
153 #5. 重复3,4，直到queue为空
154 #6. 以一种非常漂亮的方式打印result
155 def make_decision_tree():
156 from Queue import Queue
157 result = ((0, 1, 2, 3), {})
158 queue = Queue()
159 rest_nums = init_set()
160 queue.put((rest_nums, result))
161 #all xAyB set
162 abs = [(a, b) for a in range(5) for b in range(5 - a)]
163 while not queue.empty():
164 (rest_nums, (guess, mapping)) = queue.get()
165 for (a, b) in abs:
166 new_rest_nums = check_and_remove(rest_nums, guess, a, b)
167 length = len(new_rest_nums)
168 if length == 1:
169 if a != 4: #b can't be other than 0 when a == 4
170 mapping[a * 10 + b] = new_rest_nums[0]
171 elif length > 1:
172 new_guess = next_guess4(new_rest_nums) #TODO: 替换guess函数调整算法
173 new_result = (new_guess, {})
174 mapping[a * 10 + b] = new_result
175 queue.put((new_rest_nums, new_result))
176 return result
177
178 max_level = 0
179 level7_plus_tups = []
180 def pprint_result(result, level = 0):
181 global max_level, max_level_tup
182 (tup, mapping) = result
183 print tup
184 level += 1
185 if level > max_level:
186 max_level = level
187 if len(mapping) == 0:
188 print
189 else:
190 for key in mapping:
191 val = mapping[key]
192 #打印前缀
193 print u"%d|\t" * level % tuple(range(1, level + 1)),
194 print u"%d:" % (level + 1),
195 #打印xAyB
196 print u"%dA%dB" % (key / 10, key % 10),
197 if len(val) == 4: #direct result
198 #打印结果
199 print val
200 if level >= 7:
201 level7_plus_tups.append((level, val))
202 else:
203 pprint_result(val, level)
204
205 #来玩玩
206 print u"Notice: 4A0B is NOT included, since it result to Game Over"
207 pprint_result(make_decision_tree())
208 print
209 print u"max level is:", max_level + 1
210 print u"level7 plus tuples:"
211 for (level, tup) in level7_plus_tups:
212 print u"level:", level + 1, u"\ttup:", tup
213 print
所有评论，共10条：( 我也来说两句)
| 1 |
半瓶墨水
5个月前
回复
用这种算法，最难猜的几组数是：
|
| 2 |
改进一下 get_match_ab:
|
| 3 |
comment里的代码不支持格式呀
|
| 4 |
@lanser
|
| 5 |
@lanser 格式的问题部分搞定：现在至少支持缩进了
|
| 6 |
现在有三种方法来选下一个：
|
| 7 |
用timeit试过，从6s降到4s
|
| 8 |
应该是从16次比较降到8次比较吧
|
| 9 |
@lancer 确实，是我算错了，我试了一下，效果跟你说的差不多，多谢提供这个方法。
|
| 10 |
我怀疑可以用信息论的方法证明次数，说不定就是7~8次
|
