12 个球找假球

from itertools import product
from functools import lru_cache

def clockwise(v):
    for a, b in zip(v, v[1:]):
        if a != b:
            return (b - a) % 3 == 1          # 首次变化是 0→1、1→2 或 2→0
    return None                               # 000/111/222 剔除

codes = [v for v in product(range(3), repeat=3) if clockwise(v)]
print(len(codes), codes)
# 12 [(0, 0, 1), (0, 1, 0), (0, 1, 1), (0, 1, 2), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2), (2, 0, 0), (2, 0, 1), (2, 0, 2), (2, 2, 0)]
for i in range(3):
    left  = [k + 1 for k, c in enumerate(codes) if c[i] == 0]
    right = [k + 1 for k, c in enumerate(codes) if c[i] == 2]
    print(f"第 {i+1} 次: {left} vs {right}")
# 第 1 次: [1, 2, 3, 4] vs [9, 10, 11, 12]
# 第 2 次: [1, 9, 10, 11] vs [6, 7, 8, 12]
# 第 3 次: [2, 6, 9, 12] vs [4, 5, 8, 11]

def weigh(fake, heavy):
    out = []
    for i in range(3):
        d = codes[fake][i]
        side = 0 if d == 0 else (2 if d == 2 else None)
        if side is None: out.append(1)            # 假球不在秤上：平
        elif (side == 0) == heavy: out.append(0)  # 左沉
        else: out.append(2)                       # 右沉
    return tuple(out)

def decode(r):
    for k, c in enumerate(codes):
        if c == r: return k, "重"
        if tuple(2 - x for x in c) == r: return k, "轻"
all_ok = all(decode(weigh(k, h)) == (k, "重" if h else "轻") for k in range(12) for h in (True, False))
print(all_ok)                                          # True

@lru_cache(None)
def ok(u, h, l, g, n, need_dir=True):
    """u 颗轻重都可能、h 颗只可能偏重、l 颗只可能偏轻；g=手里有无标准球；还剩 n 次。"""
    if need_dir and 2 * u + h + l <= 1: return True
    if not need_dir and u + h + l <= 1: return True
    if n == 0: return False
    for u1, u2, h1, h2, l1, l2 in product(range(u + 1), range(u + 1), range(h + 1),
                                          range(h + 1), range(l + 1), range(l + 1)):
        if u1 + u2 > u or h1 + h2 > h or l1 + l2 > l: continue
        L, R = u1 + h1 + l1, u2 + h2 + l2
        if L == R == 0 or (L != R and not g): continue        # 两边个数不等时用标准球补
        rest = (u - u1 - u2, h - h1 - h2, l - l1 - l2)
        tip = [(0, u1 + h1, u2 + l2), (0, u2 + h2, u1 + l1)]   # 左沉 / 右沉
        cases = tip + [rest]
        total = u + h + l
        if all(ok(*c, g or (sum(c) < total), n - 1, need_dir) for c in cases):
            return True
    return False

print(ok(12, 0, 0, False, 3), ok(13, 0, 0, False, 3))   # True False
print(ok(13, 0, 0, False, 3, need_dir=False))           # True   13 球只找球、不判轻重
print(ok(13, 0, 0, True, 3), ok(14, 0, 0, True, 3))     # True False  带一个标准球
for n in (2, 3):
    print(n, max(N for N in range(1, 20) if ok(N, 0, 0, False, n)), (3**n - 3) // 2)
# 2 3 3
# 3 12 12
print(ok(39, 0, 0, False, 4), ok(40, 0, 0, False, 4))   # True False  跑约 10 秒