"""Phát hiện và thu nhỏ phản ví dụ cho hàm kiểm tra trùng ca."""
from itertools import combinations, product


def faulty(a, b):
    return max(a[0], b[0]) <= min(a[1], b[1])


def overlap(a, b):
    return max(a[0], b[0]) < min(a[1], b[1])


def oracle(a, b):
    # Oracle riêng cho các mốc nguyên và khoảng nửa mở.
    return bool(set(range(*a)) & set(range(*b)))


def shrink_failure(a, b):
    intervals = list(combinations(range(max(*a, *b) + 1), 2))
    smaller = (pair for pair in product(intervals, repeat=2)
               if faulty(*pair) != oracle(*pair))
    return min(smaller, key=lambda pair: (sum(sum(interval) for interval in pair), pair))


if __name__ == "__main__":
    original = ((3, 6), (6, 8))
    assert faulty(*original) != oracle(*original)
    smallest = shrink_failure(*original)
    assert smallest == ((0, 1), (1, 2))
    intervals = list(combinations(range(9), 2))
    for a, b in product(intervals, repeat=2):
        assert overlap(a, b) == overlap(b, a)
        assert overlap(a, b) == oracle(a, b)
    print("Phản ví dụ nhỏ:", smallest, "| số cặp đối chiếu:", len(intervals) ** 2)