#coding=utf-8

#猜数字游戏8步以内的求解程序
#每次给出结果，要求输入xAyB，比如2A0B这样的结果，不分大小写
#
#解题思路很简单：
#1. 生成所有的四位不重复的0-9的数字组合的集合
#2. 随便找四个数字，比如0123
#3. 根据用户返回结果(xAyB)，砍掉集合里面不符合结果的
#4. 根据现有数字组合，猜下一个，主要技术含量在这里：
#   a. 贪心算法，每次都找当前步骤里最优的
#   b. “最优”的定义：
#      b1. 选择一个组合
#      b2. 把这个组合和剩下的组合进行匹配，统计xAyB出现的次数，
#          比如0A0B出现了10次，1A3B出现了0次等等
#      b3. 如果xAyB的所有可能出现的机会最为均等，那么这个选择的“区分度”就很大
#          这个可以通过信息量理论进行衡量，也可以简化为通过“最小标准差”来衡量
#      b4. 遍历所有组合，找出“区分度”最大的
#5. 重复步骤3, 4，直到用户给出4A0B或者集合里面只剩下一个元素
#

#生成所有的四位不重复的0-9的数字组合
#  by Leo Jay
#  灭掉了所有的判断语句，同时用展开的方法灭掉了set，目前已知最快的
#  应该不能更快了，因为这个版本已经没有多余的操作了
#其他方法参见：http://www.fayaa.com/code/view/114/
def init_set():
    ret = []
    for i in xrange(0, 10):
       for j in xrange(i+1, 10):
           for k in xrange(j+1, 10):
               for l in xrange(k+1, 10):
                   ret.append((i, j, k, l))
                   ret.append((i, j, l, k))
                   ret.append((i, k, j, l))
                   ret.append((i, k, l, j))
                   ret.append((i, l, j, k))
                   ret.append((i, l, k, j))
                   ret.append((j, i, k, l))
                   ret.append((j, i, l, k))
                   ret.append((j, k, i, l))
                   ret.append((j, k, l, i))
                   ret.append((j, l, i, k))
                   ret.append((j, l, k, i))
                   ret.append((k, i, j, l))
                   ret.append((k, i, l, j))
                   ret.append((k, j, i, l))
                   ret.append((k, j, l, i))
                   ret.append((k, l, i, j))
                   ret.append((k, l, j, i))
                   ret.append((l, i, j, k))
                   ret.append((l, i, k, j))
                   ret.append((l, j, i, k))
                   ret.append((l, j, k, i))
                   ret.append((l, k, i, j))
                   ret.append((l, k, j, i))
    return ret

#对给定的两组数，计算xAyB
#不知道能不能更快些
def get_match_ab(target, source):
    la, lb = 0, 0
    for (i, t) in enumerate(target):
        for (j, s) in enumerate(source):
            if s == t:
                if i == j:
                    la += 1
                else:
                    lb += 1
                #break this loop since we already found match
                break
    return (la, lb)

#检查target与source是否符合aAbB
def match_guess(target, source, a, b):
    (la, lb) = get_match_ab(target, source)
    return la == a and lb == b

#nums: the number_set list to be checked
#guess: last guess
#a, b: the number of aAbB
#@return: the rest number_sets which matche last guess
def check_and_remove(nums, guess, a, b):
    rest_nums = []
    for num_set in nums:
        if match_guess(num_set, guess, a, b):
            rest_nums.append(num_set)
    return rest_nums

#计算一个选择相对于选择集的“标准差”
def calc_standard_deviation(target, nums):
    #a * 10 + b is used to indicate an "a & b" combination
    ab_map = {}
    #init ab_map
    abs = (0, 1, 2, 3, 4, 10, 11, 12, 13, 20, 21, 22, 30, 31, 40)
    for ab in abs:
        ab_map[ab] = 0
    #let's do the calculation
    for num_set in nums:
        (a, b) = get_match_ab(num_set, target)
        ab_map[a * 10 + b] += 1
    ab_counts = [ab_map[ab] for ab in abs]
    total = sum(ab_counts)
    avg = float(total) / len(abs)
    sd = sum([(abc - avg)**2 for abc in ab_counts])
    return sd

#根据现有集合寻找下一个集合
#采用“最小标准差”作为衡量标准
def next_guess(nums):
    min_sd = 0
    min_set = ()
    touched = False
    for num_set in nums:
        sd = calc_standard_deviation(num_set, nums)
        if not touched or min_sd > sd:
            touched = True
            min_set = num_set
            min_sd = sd
    return min_set

#猜数字的过程
def play():
    nums = init_set()
    guess = (0, 1, 2, 3)
    done = False
    retry = 1
    while not done:
        print retry, u'我猜是：', guess
        retry += 1
        a, b = 4, 4
        while a + b > 4:
            in_str = raw_input(u'请输入这次猜测的结果(xAyB)：'.encode('GBK'))
            try:
                a = int(in_str[0])
                b = int(in_str[2])
            except:
                print u'输入有误，请重新输入'
                continue
            if a + b > 4:
                print u'输入有误，AB数目和大于4了，请重新输入'
        nums = check_and_remove(nums, guess, a, b)
        if len(nums) <= 0:
            break
        elif len(nums) == 1:
            done = True
        else:
            print u' 范围缩小到%d个数字了...' % len(nums)

            #为了效率所做的妥协:第一次返回结果以后直接取剩下的里面的第一个
            #TODO:有时间就来做个全排列证明一下8次以内这种方法可行
            #TODO:说不定八次都直接选取第一个就可以，那还要什么算法...:(
            if retry < 3: 
                guess = nums[0]
            else:
                guess = next_guess(nums)
    #拆数字结束了
    if done: #出错则为False
        print u'搞定! 目标数字是：', nums[0]
    else:
        print u'您输入的结果中某一步有错误，请检查一下'
    print

#来玩玩
while True:
    print
    print '----------------------------'
    print u'猜数字游戏八步以内求解程序'
    print u'按 Ctrl + C 退出'
    print '----------------------------'
    print
    play()