論理クイズソルバー

marubatu.py

"""
論理クイズ(https://kuizy.net/user/Noir_KUS)のソルバー
"""

from typing import Callable, Sequence


class State:
    """
    マルバツ全10問に対する答えの、ひとつの組み合わせ表現するimmutableなオブジェクト.

    内部表現は長さ11のlistで、index 1〜10 がそれぞれの問題の解(True or False)となっている。
    index 0 は、固定でFalseが入る. (indexを問題番号と一致させ分かりやすくするためのpadding)
    """

    def __init__(self, bits: Sequence[bool]):
        self._nbits = len(bits)
        self._bits_buffer = [False] + list(bits)

    def __getitem__(self, item):
        return self._bits_buffer[item]

    @staticmethod
    def _bits_to_int(bits: Sequence[bool]) -> int:
        """
        boolリストを、10 bit の整数値に変換する。
        """
        return sum(x * 2**i for i, x in enumerate(reversed(bits)))

    @staticmethod
    def _int_to_bits(bits_num: int, nbits: int) -> Sequence[bool]:
        """
        整数値を2進数変換し、長さnbitsのboolリストで返す。
        """
        bits_itr = (bool((bits_num >> i) & 0b1) for i in range(nbits))
        return list(reversed(list(bits_itr)))

    @classmethod
    def iter_asc(cls, from_: Sequence[bool], to: Sequence[bool]):
        """
        from から to まで解をイテレートする
        """
        nbits = max(len(from_), len(to))
        bounds = sorted([cls._bits_to_int(from_), cls._bits_to_int(to)])
        for x in range(bounds[0], bounds[1]+1):
            yield State(bits=cls._int_to_bits(x, nbits=nbits))

    def __repr__(self):
        return repr([int(x) for x in self._bits_buffer[1:]])


def solve(problem: Sequence[Callable[[State], bool]]):
    """
    指定された問題に対して適合するstateをイテレートする。

    problemはstateに対してTrue/Falseを返す関数のリストであり、
    この関数solveはproblemに含まれるすべての関数がTrueを返すような解をすべて求める。

    :param problem: stateを受け取り、True/Falseのいずれかを返す関数のリスト
    """

    # [False, False, ...] から [True, True, ...] まで探索
    start_bits = [False] * 10
    end_bits = [True] * 10

    for state in State.iter_asc(from_=start_bits, to=end_bits):
        if all(p(state) for p in problem):
            yield state


def exists_renzoku_n(n: int) -> Callable[[Sequence[bool]], bool]:
    def _(x) -> bool:
        k = 0
        for a, b in zip(x[:-1], x[1:]):
            if a == b:
                k += 1
                if k >= n - 1:
                    return True
            else:
                k = 0
        return False

    return _


def problem1() -> Sequence[Callable[[State], bool]]:
    """
    問題1の定義.
    https://kuizy.net/quiz/3273
    """

    return [
        # 1. これは1問目である
        lambda x: x[1] == True,

        # 2. この問題と8問目の答えは同じである
        lambda x: x[2] == (x[2] == x[8]),

        # 3. 3〜9問目において、答えが×の問題よりも答えが○の問題の方が多い
        lambda x: x[3] == (sum(x[3:10]) > 3),

        # 4. 4〜10問目において、答えが○の問題が2回以上連続することはない
        lambda x: x[4] == (exists_renzoku_n(2)(x[4:10])),

        # 5. 問題番号が奇数であるもののうち答えが○の問題は2問、答えが×の問題は3問ある
        lambda x: x[5] == (x[1]+x[3]+x[5]+x[7]+x[9] == 2),

        # 6. 全10問のうち答えが○の問題は4問、答えが×の問題は6問ある
        lambda x: x[6] == (sum(x[1:]) == 4),

        # 7. 8〜10問目において、答えが○の問題はない
        lambda x: x[7] == (sum(x[8:]) == 0),

        # 8. この問題と2問目の答えは同じではない
        lambda x: x[8] == (x[8] != x[2]),

        # 9. この問題の答えは○でありうる
        # 10. 全10問の答えは問題文のみから一意に定まる

        # 上記1〜8の条件で探索すると、ここまでの条件では問9-10の答えを確定できず、
        # ◯-◯、◯-×、×-◯、×-× のすべての組み合わせがあり得ることが分かる。
        # ここで、
        #   問9の問題文から「答えは◯であり得る」ので、問9は◯
        #   問10の問題文から「答えが一意に定まらない」ので、問10は×
        # となり、したがって上記候補のうち問9-10が ◯-× であるものが解である。
        lambda x: x[9] == True,
        lambda x: x[10] == False,
    ]


def problem3() -> Sequence[Callable[[State], bool]]:
    """
    問題3の定義.
    https://kuizy.net/quiz/3389
    """

    return [
        # 1. これは10問目である
        lambda x: x[1] == False,

        # 2. この問題を除く9問のうち、答えが×の問題は答えが○の問題より多い
        lambda x: x[2] == (x[1]+sum(x[3:]) <= 4),

        # 3. 8問目の答えは○である
        lambda x: x[3] == (x[8] == 1),

        # 4. ここから最後の問題までの7問のうち、答えが○の問題は答えが×の問題より多い
        lambda x: x[4] == (sum(x[4:]) > len(x[4:])/2),

        # 5. この問題と6問目の答えは同じである
        lambda x: x[5] == (x[5] == x[6]),

        # 6. このクイズには、答えが○の問題と答えが×の問題がそれぞれ5問ずつある
        lambda x: x[6] == (sum(x[1:]) == 5),

        # 7. 奇数番号の問題のうち、答えが×の問題は4問ある
        lambda x: x[7] == (x[1] + x[3] + x[5] + x[7] + x[9] == 1),

        # 8. このクイズでは、同じ答えの問題が3問以上連続している
        lambda x: x[8] == (exists_renzoku_n(3)(x[1:])),

        # 9. この問題の前後にある2問の答えは同じである
        lambda x: x[9] == (x[8] == x[10]),

        # 10. 全ての問題の答えは、これより上にある全ての問題文からただ1つに決まる

        # 上記1〜9の条件で解を探索すると、可能な解は2通り存在することが分かる。
        # このことから、問10の「これより上にある全ての問題文からただ1つに決まる」は偽であることが分かるので、
        # その条件を加えることで解を1つに絞り込むことができる。
        lambda x: x[10] == False,

    ]


def main() -> int:

    print("problem 1:")
    for ans in solve(problem1()):
        print(ans)

    print("problem 3:")
    for ans in solve(problem1()):
        print(ans)

    return 0


if __name__ == '__main__':
    main()