代码
比这篇新的文章:
python.普通 IP 转换为十进制 IP
比这篇旧的文章: 计算python函数性能的小程序
作者: 半瓶墨水, 点击761次, 评论(0), 收藏者(1)
打分:
所有评论，共0条：( 我也来说两句)
比这篇旧的文章: 计算python函数性能的小程序
猜数字游戏的八步以内求解程序
语言: Python, 标签: 猜数字 求解程序 2008/06/22发布 5个月前更新 更新记录作者: 半瓶墨水, 点击761次, 评论(0), 收藏者(1)
Python语言: 猜数字游戏的八步以内求解程序
001 #coding=utf-8
002
003 #猜数字游戏8步以内的求解程序
004 #每次给出结果，要求输入xAyB，比如2A0B这样的结果，不分大小写
005 #
006 #解题思路很简单：
007 #1. 生成所有的四位不重复的0-9的数字组合的集合
008 #2. 随便找四个数字，比如0123
009 #3. 根据用户返回结果(xAyB)，砍掉集合里面不符合结果的
010 #4. 根据现有数字组合，猜下一个，主要技术含量在这里：
011 # a. 贪心算法，每次都找当前步骤里最优的
012 # b. “最优”的定义：
013 # b1. 选择一个组合
014 # b2. 把这个组合和剩下的组合进行匹配，统计xAyB出现的次数，
015 # 比如0A0B出现了10次，1A3B出现了0次等等
016 # b3. 如果xAyB的所有可能出现的机会最为均等，那么这个选择的“区分度”就很大
017 # 这个可以通过信息量理论进行衡量，也可以简化为通过“最小标准差”来衡量
018 # b4. 遍历所有组合，找出“区分度”最大的
019 #5. 重复步骤3, 4，直到用户给出4A0B或者集合里面只剩下一个元素
020 #
021
022 #生成所有的四位不重复的0-9的数字组合
023 # by Leo Jay
024 # 灭掉了所有的判断语句，同时用展开的方法灭掉了set，目前已知最快的
025 # 应该不能更快了，因为这个版本已经没有多余的操作了
026 #其他方法参见：http://www.fayaa.com/code/view/114/
027 def init_set():
028 ret = []
029 for i in xrange(0, 10):
030 for j in xrange(i+1, 10):
031 for k in xrange(j+1, 10):
032 for l in xrange(k+1, 10):
033 ret.append((i, j, k, l))
034 ret.append((i, j, l, k))
035 ret.append((i, k, j, l))
036 ret.append((i, k, l, j))
037 ret.append((i, l, j, k))
038 ret.append((i, l, k, j))
039 ret.append((j, i, k, l))
040 ret.append((j, i, l, k))
041 ret.append((j, k, i, l))
042 ret.append((j, k, l, i))
043 ret.append((j, l, i, k))
044 ret.append((j, l, k, i))
045 ret.append((k, i, j, l))
046 ret.append((k, i, l, j))
047 ret.append((k, j, i, l))
048 ret.append((k, j, l, i))
049 ret.append((k, l, i, j))
050 ret.append((k, l, j, i))
051 ret.append((l, i, j, k))
052 ret.append((l, i, k, j))
053 ret.append((l, j, i, k))
054 ret.append((l, j, k, i))
055 ret.append((l, k, i, j))
056 ret.append((l, k, j, i))
057 return ret
058
059 #对给定的两组数，计算xAyB
060 #不知道能不能更快些
061 def get_match_ab(target, source):
062 la, lb = 0, 0
063 for (i, t) in enumerate(target):
064 for (j, s) in enumerate(source):
065 if s == t:
066 if i == j:
067 la += 1
068 else:
069 lb += 1
070 #break this loop since we already found match
071 break
072 return (la, lb)
073
074 #检查target与source是否符合aAbB
075 def match_guess(target, source, a, b):
076 (la, lb) = get_match_ab(target, source)
077 return la == a and lb == b
078
079 #nums: the number_set list to be checked
080 #guess: last guess
081 #a, b: the number of aAbB
082 #@return: the rest number_sets which matche last guess
083 def check_and_remove(nums, guess, a, b):
084 rest_nums = []
085 for num_set in nums:
086 if match_guess(num_set, guess, a, b):
087 rest_nums.append(num_set)
088 return rest_nums
089
090 #计算一个选择相对于选择集的“标准差”
091 def calc_standard_deviation(target, nums):
092 #a * 10 + b is used to indicate an "a & b" combination
093 ab_map = {}
094 #init ab_map
095 abs = (0, 1, 2, 3, 4, 10, 11, 12, 13, 20, 21, 22, 30, 31, 40)
096 for ab in abs:
097 ab_map[ab] = 0
098 #let's do the calculation
099 for num_set in nums:
100 (a, b) = get_match_ab(num_set, target)
101 ab_map[a * 10 + b] += 1
102 ab_counts = [ab_map[ab] for ab in abs]
103 total = sum(ab_counts)
104 avg = float(total) / len(abs)
105 sd = sum([(abc - avg)**2 for abc in ab_counts])
106 return sd
107
108 #根据现有集合寻找下一个集合
109 #采用“最小标准差”作为衡量标准
110 def next_guess(nums):
111 min_sd = 0
112 min_set = ()
113 touched = False
114 for num_set in nums:
115 sd = calc_standard_deviation(num_set, nums)
116 if not touched or min_sd > sd:
117 touched = True
118 min_set = num_set
119 min_sd = sd
120 return min_set
121
122 #猜数字的过程
123 def play():
124 nums = init_set()
125 guess = (0, 1, 2, 3)
126 done = False
127 retry = 1
128 while not done:
129 print retry, u'我猜是：', guess
130 retry += 1
131 a, b = 4, 4
132 while a + b > 4:
133 in_str = raw_input(u'请输入这次猜测的结果(xAyB)：'.encode('GBK'))
134 try:
135 a = int(in_str[0])
136 b = int(in_str[2])
137 except:
138 print u'输入有误，请重新输入'
139 continue
140 if a + b > 4:
141 print u'输入有误，AB数目和大于4了，请重新输入'
142 nums = check_and_remove(nums, guess, a, b)
143 if len(nums) <= 0:
144 break
145 elif len(nums) == 1:
146 done = True
147 else:
148 print u' 范围缩小到%d个数字了...' % len(nums)
149
150 #为了效率所做的妥协:第一次返回结果以后直接取剩下的里面的第一个
151 #TODO:有时间就来做个全排列证明一下8次以内这种方法可行
152 #TODO:说不定八次都直接选取第一个就可以，那还要什么算法...:(
153 if retry < 3:
154 guess = nums[0]
155 else:
156 guess = next_guess(nums)
157 #拆数字结束了
158 if done: #出错则为False
159 print u'搞定! 目标数字是：', nums[0]
160 else:
161 print u'您输入的结果中某一步有错误，请检查一下'
162 print
163
164 #来玩玩
165 while True:
166 print
167 print '----------------------------'
168 print u'猜数字游戏八步以内求解程序'
169 print u'按 Ctrl + C 退出'
170 print '----------------------------'
171 print
172 play()
002
003 #猜数字游戏8步以内的求解程序
004 #每次给出结果，要求输入xAyB，比如2A0B这样的结果，不分大小写
005 #
006 #解题思路很简单：
007 #1. 生成所有的四位不重复的0-9的数字组合的集合
008 #2. 随便找四个数字，比如0123
009 #3. 根据用户返回结果(xAyB)，砍掉集合里面不符合结果的
010 #4. 根据现有数字组合，猜下一个，主要技术含量在这里：
011 # a. 贪心算法，每次都找当前步骤里最优的
012 # b. “最优”的定义：
013 # b1. 选择一个组合
014 # b2. 把这个组合和剩下的组合进行匹配，统计xAyB出现的次数，
015 # 比如0A0B出现了10次，1A3B出现了0次等等
016 # b3. 如果xAyB的所有可能出现的机会最为均等，那么这个选择的“区分度”就很大
017 # 这个可以通过信息量理论进行衡量，也可以简化为通过“最小标准差”来衡量
018 # b4. 遍历所有组合，找出“区分度”最大的
019 #5. 重复步骤3, 4，直到用户给出4A0B或者集合里面只剩下一个元素
020 #
021
022 #生成所有的四位不重复的0-9的数字组合
023 # by Leo Jay
024 # 灭掉了所有的判断语句，同时用展开的方法灭掉了set，目前已知最快的
025 # 应该不能更快了，因为这个版本已经没有多余的操作了
026 #其他方法参见：http://www.fayaa.com/code/view/114/
027 def init_set():
028 ret = []
029 for i in xrange(0, 10):
030 for j in xrange(i+1, 10):
031 for k in xrange(j+1, 10):
032 for l in xrange(k+1, 10):
033 ret.append((i, j, k, l))
034 ret.append((i, j, l, k))
035 ret.append((i, k, j, l))
036 ret.append((i, k, l, j))
037 ret.append((i, l, j, k))
038 ret.append((i, l, k, j))
039 ret.append((j, i, k, l))
040 ret.append((j, i, l, k))
041 ret.append((j, k, i, l))
042 ret.append((j, k, l, i))
043 ret.append((j, l, i, k))
044 ret.append((j, l, k, i))
045 ret.append((k, i, j, l))
046 ret.append((k, i, l, j))
047 ret.append((k, j, i, l))
048 ret.append((k, j, l, i))
049 ret.append((k, l, i, j))
050 ret.append((k, l, j, i))
051 ret.append((l, i, j, k))
052 ret.append((l, i, k, j))
053 ret.append((l, j, i, k))
054 ret.append((l, j, k, i))
055 ret.append((l, k, i, j))
056 ret.append((l, k, j, i))
057 return ret
058
059 #对给定的两组数，计算xAyB
060 #不知道能不能更快些
061 def get_match_ab(target, source):
062 la, lb = 0, 0
063 for (i, t) in enumerate(target):
064 for (j, s) in enumerate(source):
065 if s == t:
066 if i == j:
067 la += 1
068 else:
069 lb += 1
070 #break this loop since we already found match
071 break
072 return (la, lb)
073
074 #检查target与source是否符合aAbB
075 def match_guess(target, source, a, b):
076 (la, lb) = get_match_ab(target, source)
077 return la == a and lb == b
078
079 #nums: the number_set list to be checked
080 #guess: last guess
081 #a, b: the number of aAbB
082 #@return: the rest number_sets which matche last guess
083 def check_and_remove(nums, guess, a, b):
084 rest_nums = []
085 for num_set in nums:
086 if match_guess(num_set, guess, a, b):
087 rest_nums.append(num_set)
088 return rest_nums
089
090 #计算一个选择相对于选择集的“标准差”
091 def calc_standard_deviation(target, nums):
092 #a * 10 + b is used to indicate an "a & b" combination
093 ab_map = {}
094 #init ab_map
095 abs = (0, 1, 2, 3, 4, 10, 11, 12, 13, 20, 21, 22, 30, 31, 40)
096 for ab in abs:
097 ab_map[ab] = 0
098 #let's do the calculation
099 for num_set in nums:
100 (a, b) = get_match_ab(num_set, target)
101 ab_map[a * 10 + b] += 1
102 ab_counts = [ab_map[ab] for ab in abs]
103 total = sum(ab_counts)
104 avg = float(total) / len(abs)
105 sd = sum([(abc - avg)**2 for abc in ab_counts])
106 return sd
107
108 #根据现有集合寻找下一个集合
109 #采用“最小标准差”作为衡量标准
110 def next_guess(nums):
111 min_sd = 0
112 min_set = ()
113 touched = False
114 for num_set in nums:
115 sd = calc_standard_deviation(num_set, nums)
116 if not touched or min_sd > sd:
117 touched = True
118 min_set = num_set
119 min_sd = sd
120 return min_set
121
122 #猜数字的过程
123 def play():
124 nums = init_set()
125 guess = (0, 1, 2, 3)
126 done = False
127 retry = 1
128 while not done:
129 print retry, u'我猜是：', guess
130 retry += 1
131 a, b = 4, 4
132 while a + b > 4:
133 in_str = raw_input(u'请输入这次猜测的结果(xAyB)：'.encode('GBK'))
134 try:
135 a = int(in_str[0])
136 b = int(in_str[2])
137 except:
138 print u'输入有误，请重新输入'
139 continue
140 if a + b > 4:
141 print u'输入有误，AB数目和大于4了，请重新输入'
142 nums = check_and_remove(nums, guess, a, b)
143 if len(nums) <= 0:
144 break
145 elif len(nums) == 1:
146 done = True
147 else:
148 print u' 范围缩小到%d个数字了...' % len(nums)
149
150 #为了效率所做的妥协:第一次返回结果以后直接取剩下的里面的第一个
151 #TODO:有时间就来做个全排列证明一下8次以内这种方法可行
152 #TODO:说不定八次都直接选取第一个就可以，那还要什么算法...:(
153 if retry < 3:
154 guess = nums[0]
155 else:
156 guess = next_guess(nums)
157 #拆数字结束了
158 if done: #出错则为False
159 print u'搞定! 目标数字是：', nums[0]
160 else:
161 print u'您输入的结果中某一步有错误，请检查一下'
162 print
163
164 #来玩玩
165 while True:
166 print
167 print '----------------------------'
168 print u'猜数字游戏八步以内求解程序'
169 print u'按 Ctrl + C 退出'
170 print '----------------------------'
171 print
172 play()
所有评论，共0条：( 我也来说两句)