题目描述

有一个猜数字游戏，庄家预先写下一个四位数字（每位数字各不相同），玩家每次随机猜一个数字，庄家告知玩家猜对了几A几B（A代表数字和位置都相同，B代表包含该数字但位置不同，比如如果庄家写的是3514，玩家猜的是3165，庄家会回答1A2B），玩家继续猜，直到猜中为止。如果超过5轮没猜中，则玩家输，否则玩家赢。请为玩家设计一个猜数字的算法，确保玩家能够大概率胜。
例如：庄家写下9876，玩家第一次猜0123，庄家回复0A0B；玩家继续猜4567，庄家回复0A2B；依次下去，直到玩家猜中9876为止。
提示：可以用排除法，根据庄家的反馈排除部分数字。

解法

点击查看

# coding=utf-8

import random
import itertools

def generate_random_data(n=4):
    data_set = list(range(0, 10))
    return tuple(random.sample(data_set, n))

def check_guess_result(guess, target):
    include_nums = 0
    match_nums = 0
    for i in range(len(guess)):
        if guess[i] == target[i]:
            match_nums += 1
        else:
            if guess[i] in target:
                include_nums += 1

    return "{}A{}B".format(match_nums, include_nums)


def ai_guess(n, limit):
    target = generate_random_data(n) 
    print('target is: '+ str(target))
    all_candidates = list(itertools.permutations(range(0, 10), n))  
    count = 1
    guess = tuple(range(0, n))  
    success_res = "{0}A0B".format(n)
    while True:
        check_res = check_guess_result(guess, target) 
        print(count, guess, check_res, len(all_candidates))
        if check_res == success_res:
            if(count <= limit):
                print("you win!")
            else:
                print("you lost")
            break
        all_candidates = list(
            filter(lambda x: check_guess_result(x, guess) == check_res, all_candidates)
        )
        guess = all_candidates.pop()
        count += 1


if __name__ == '__main__':
    ai_guess(4, 5)

总结

阿里二面的题目，给了一天时间，查了下还是某年 ACM的一道题。
思路在题目中已经给出了，就是排除法。
4位数的排列组合一共有 5040种可能，算法能做的就是根据返回的信息，将不符合条件的数字过滤掉，然后从可能的结果中随机选，直到选中。