Skip to content

Instantly share code, notes, and snippets.

@kokumura
Last active Jan 29, 2020
Embed
What would you like to do?
論理クイズソルバー
"""
論理クイズ(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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment