"""Original exact simplex projection via sorted threshold versus all-support oracle."""
from fractions import Fraction as F
from itertools import combinations,product
import json

def validate(y):
 if not isinstance(y,list) or not 1<=len(y)<=4 or any(type(v) not in [int,F] or abs(v)>10 or F(v).denominator>10000 for v in y):raise ValueError('1..4 bounded exact rationals;float/bool rejected')
 return list(map(F,y))
def project(y):
 y=validate(y);u=sorted(y,reverse=True);trace=[];rho=0;total=F(0)
 for j,v in enumerate(u,1):
  total+=v;theta=(total-1)/j;positive=v-theta>0;trace.append({'j':j,'u_j':str(v),'theta_candidate':str(theta),'positive':positive})
  if positive:rho=j
 theta=(sum(u[:rho])-1)/rho;x=[max(F(0),v-theta) for v in y];assert sum(x)==1
 for v,z in zip(y,x):assert (z==v-theta and z>0) or (z==0 and v<=theta)
 return x,theta,trace
def supports(y):
 candidates=[]
 for count in range(1,len(y)+1):
  for active in combinations(range(len(y)),count):
   theta=(sum(y[i] for i in active)-1)/count;x=[y[i]-theta if i in active else F(0) for i in range(len(y))]
   if all(x[i]>0 for i in active) and all(y[i]<=theta for i in range(len(y)) if i not in active):candidates.append(x)
 assert len(candidates)==1;return candidates[0]
def objective(x,y):return sum((a-b)**2 for a,b in zip(x,y))/2
def demo():
 y=[F(1,5),F(-3,10),F(17,10)];x,t,trace=project(y);assert x==[0,0,1] and objective(x,y)==F(31,100)
 clip=[max(F(0),v) for v in y];clip=[v/sum(clip) for v in clip];assert clip==[F(2,19),0,F(17,19)] and objective(clip,y)>objective(x,y)
 count=0
 for row in product([-1,F(-1,2),0,F(1,2),1],repeat=3):
  v=list(map(F,row));got,theta,steps=project(v);assert got==supports(v);assert project([q+2 for q in v])[0]==got;count+=1
 negatives=project([-1,-2,-3])[0];zero=project([0,0,0])[0];assert negatives==[1,0,0] and zero==[F(1,3)]*3
 rejects=[]
 for label,v in [('empty',[]),('bool',[True]),('float',[.2]),('too_many',[0]*5),('value_budget',[11]),('denominator_budget',[F(1,10001)])]:
  try:project(v)
  except ValueError:rejects.append(label)
  else:raise AssertionError(label)
 return {'y':list(map(str,y)),'x':list(map(str,x)),'theta':str(t),'sorted_threshold_trace':trace,'objective_half_squared':str(objective(x,y)),'wrong_clip_normalize':list(map(str,clip)),'wrong_objective':str(objective(clip,y)),'all125_grid_support_oracles_and_shift':count,'all_negative':list(map(str,negatives)),'all_zero':list(map(str,zero)),'invalid_cases_rejected':rejects,'scope':'Euclidean simplex projection, not softmax/probability calibration. Exact local rational subset max4; own KKT and support enumeration, no optimizer/model/librarybenchmark.'}
if __name__=='__main__':print(json.dumps(demo(),indent=2))