解决把两个数字的和、积分别告诉两个人猜两个数字组合的问题

2015/09/03 32561
# -*- coding: utf-8 -*-

# 原题：一个老师从2到9中取两个数字，给甲说了和，给乙说了积，
# 甲说我不知道，乙说我也不知道，甲说你不知道那我就知道了，
# 乙说你知道了那我也知道了
# 这两个数分别是多少?

# ========================================================
# 为了方便表示，记两个数字的组合为字符串i&j，如2&3这种格式
# 以下是工具函数
# ========================================================
# 通过数字i和j生成组合（注意i&j和j&i其实是一样的）
def genij(i, j):
    return '%d&%d'%(i, j) if i >=j else '%d&%d'%(j, i)

# 获得组合的和
def add_ij(ij):
    v = ij.split('&')
    return int(v[0]) + int(v[1])

# 获得组合的积
def mul_ij(ij):
    v = ij.split('&')
    return int(v[0]) * int(v[1])

# ========================================================
# 以下开始计算
# ========================================================
def find_ijs(begin, end):
    end = end + 1

    # 生成两个begin-end数字所有可能的和、积
    a = {}
    b = {}
    for i in range(begin, end):
        for j in range(begin, end):
            v = genij(i, j)

            if i+j in a:
                a[i+j].add(v) 
            else:
                a[i+j] = set()
                a[i+j].add(v)

            if i*j in b:
                b[i*j].add(v)
            else:
                b[i*j] = set()
                b[i*j].add(v)

    # print u'----------两个%d-%d数字和的可能组合a-------------------\n'%(begin, end), a
    # print u'----------两个%d-%d数字积的可能组合b-------------------\n'%(begin ,end), b

    # 排除和是唯一的组合（如果是唯一，甲第一次就应该知道这两个数字）
    a1 = {k: v for k, v in a.items() if len(v) == 1}
    a1 = reduce(lambda x, y: x | y, [k for k in a1.values()]) 
    # print u'----------甲第一次不知道后可以排除的组合a1-------------------\n',list(a1)

    # 排除积是唯一的组合（如果是唯一，乙第一次就应该知道这两个数字）
    b1 = {k: v for k, v in b.items() if len(v) == 1}
    b1 = reduce(lambda x, y: x | y, [k for k in b1.values()]) 
    # print u'----------乙第一次不知道后可以排除的组合b1-------------------\n',list(b1)

    # 排除a1、b1后剩下的数字组合
    c = set()
    for i in range(begin, end):
        for j in range(begin, end):
            v = genij(i, j)
            if v not in a1 and v not in b1:
                c.add(v)
    # print u'----------甲乙第一次不知道后的可能组合c-------------------\n',list(c)

    # 甲第二次知道了，是因为他能够排除和为m数字中其他非正确答案的组合
    # 那就是说和为m的可能的数字组合除正确答案之外都在不可能的数字组合a1和b1里面
    c1 = []
    for i in c:
        v = add_ij(i)
        test = True
        for j in a[v]:
            if j != i:
                if j in c:  # 相当于 if j not in a1 and j not in b1:
                    test = False
        if test:
            c1.append(i)
    # print u'----------甲第二次知道后的可能组合c1-------------------\n',c1

    # 乙第二次知道了，是因为他能够排除积为n数字中其他非正确答案的组合
    # 他的依据是甲既然知道，那么这个数字组合肯定是c1中的一种
    # 然后他再根据c1做一下排除, 积为n的可能的数字组合除正确答案之外都在不可能的数字组合c1里面
    c2 = []
    for i in c1:
        v = mul_ij(i)
        test = True
        for j in b[v]:
            if j != i:
                if j in c1:
                    test = False
        if test:
            c2.append(i)
    # print u'----------乙第二次知道后答案c2-------------------\n',c2
    return c2

for i in range(3, 20):
    for j in range(2, i):
        print '%d-%d'%(j, i), find_ijs(j, i)
代码片段
