BluePen BluePen
  • Jenkins
  • OS
  • 算法
随笔
分类
标签
归档
关于
留言板
GitHub (opens new window)

Alex

一个好人
  • Jenkins
  • OS
  • 算法
随笔
分类
标签
归档
关于
留言板
GitHub (opens new window)
  • leetcode

  • interview

    • 扁平树结构转换为嵌套json
    • 走格子
    • Dynamic Programming 示例
    • 猜数字游戏
      • 题目描述
      • 解法
      • 总结
    • 数组划分
  • well_known_algo

  • algo
  • interview
Alex
2019-04-24
目录

猜数字游戏

-> 题目描述

有一个猜数字游戏,庄家预先写下一个四位数字(每位数字各不相同),玩家每次随机猜一个数字,庄家告知玩家猜对了几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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

-> 总结

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

编辑此页 (opens new window)
更新于: 2019-04-24 19:27
Dynamic Programming 示例
数组划分

← Dynamic Programming 示例 数组划分→

Copyright © 2019-2022 | yxxy | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式