"""Tìm một tập vô nghiệm tối tiểu theo bao hàm trên ví dụ nhỏ."""
from itertools import product


CAC_CA = ("t2", "t4", "t6")
CAC_LICH = tuple(product(CAC_CA, repeat=2))
QUY_TAC = {
    "G1": lambda a, b: a == "t2",  # Lớp A phải học thứ Hai.
    "G2": lambda a, b: b == "t2",  # Lớp B phải học thứ Hai.
    "G3": lambda a, b: a != b,     # Hai lớp dùng chung một phòng.
    "G4": lambda a, b: a != "t6",  # A không học thứ Sáu.
}


def tim_lich(gia_dinh):
    return next((lich for lich in CAC_LICH
                 if all(QUY_TAC[key](*lich) for key in gia_dinh)), None)


def tap_xung_dot(gia_dinh):
    hien_tai = list(gia_dinh)
    if tim_lich(hien_tai) is not None:
        return None
    for key in list(hien_tai):
        thu = [rule for rule in hien_tai if rule != key]
        if tim_lich(thu) is None:
            hien_tai = thu
    return hien_tai


if __name__ == "__main__":
    core = tap_xung_dot(QUY_TAC)
    print("Nhóm gây vô nghiệm:", core)
    assert core == ["G1", "G2", "G3"]
    for key in core:
        chung = tim_lich([rule for rule in core if rule != key])
        print(f"Nới {key}, lịch làm chứng (A, B):", chung)
        assert chung is not None
    assert tap_xung_dot(["G1", "G3", "G4"]) is None