萌ICP备20220458号

使用 Python 解决 1A2B 问题

2021年8月28日 4852点热度 2人点赞 0条评论
import random
from typing import Callable, Optional

def validate(answer: str, guess: str):
    """
    使用指定的答案,验证一个猜测。

    :returns:
        一个二元组,
        第一个元素是猜测中位置正确的字符数量,即 A 的数量;
        第二个元素是猜测中位置不正确,但存在于答案中的字符数量,即 B 的数量。
    """

    a = sum(1 for a, g in zip(answer, guess) if a == g)
    b = sum(1 for g in guess if g in answer)
    return a, b - a

def solve(
    answers: list[str],
    get_validation: Callable[[str], tuple[int, int]],
    on_progress: Callable[[int], None] = lambda _: None
) -> Optional[str]:
    """
    求解一个 1A2B 问题。

    :param answers: 要求解的范围,即所有可能的答案。
    :param get_validation:
        用于获取对指定猜测的验证的函数。
        该函数接受一个参数,表示指定的猜测,
        并返回一个二元组,表示对该猜测的验证结果。
        有关返回的详细信息,请参阅 ``validate``。
    :param on_progress:
        在求解进度更新时调用的函数。
        该函数接受一个参数,表示剩余的可能答案数量。

    :returns: 如果输入无误,则为求解的答案;否则为 ``None``。
    """

    on_progress(len(answers))

    if len(answers) < 2:
        # 答案已被确定。
        return answers[0] if answers else None

    # 从所有可能的答案中随机选择一个作为猜测。
    guess = random.choice(answers)
    validation = get_validation(guess)

    # 递归求解。
    return solve(
        # 使用每一个可能的答案验证之前确认的猜测,
        # 如果验证结果与之前确认的结果相同,
        # 即该答案符合之前确认的验证结果,
        # 则说明该答案有可能为正确答案。
        # 所有仍有可能的答案将进入下一轮求解。
        [
            it for it in answers
            if validate(it, guess) == validation
        ],
        get_validation,
        on_progress
    )

def get_validation_interactive(guess: str):
    """交互式验证答案。"""
    print('Guess:', guess)
    return tuple(map(int, input('Validation: ').split()))

# 四位数答案的范围在 [1023, 9877),且没有重复数字。
# 集合中的元素不能重复,
# 故如果字符串转为集合后长度不变,则说明没有重复。
all_4_digits = [
    it for it in map(str, range(1023, 9877))
    if len(set(it)) == len(it)
]

if __name__ == '__main__':
    print('@funnysyc: e.g. "Validation: 1 2" for 1A2B')

    # 在所有可能的四位数答案中求解。
    answer = solve(
        all_4_digits,
        get_validation_interactive,
        lambda size: print(size, 'answer(s) left')
    )

    print('Answer:', answer or 'does not exist')

funnysyc

啥都不会。

文章评论