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()