"""Original bounded best-single-swap k-medoids; exact absolute distances."""
from fractions import Fraction as F
from itertools import combinations
import json

def validate(points,k,initial):
 if type(points) is not list or not 1<=len(points)<=8 or any(type(r) is not tuple or len(r)!=2 or type(r[0]) is not str or not r[0] or type(r[1]) not in [int,F] or abs(r[1])>100 for r in points) or len({r[0] for r in points})!=len(points) or type(k) is not int or not 1<=k<=len(points) or type(initial) is not tuple or len(initial)!=k or len(set(initial))!=k or not set(initial)<=set(x[0] for x in points):raise ValueError('bounded unique-ID exact points, valid k/initial medoid IDs')

def objective(points,medoids):
 values=dict(points);assignment=[];total=F(0)
 for ident,v in points:
  best=min(medoids,key=lambda m:(abs(F(v)-values[m]),m));cost=abs(F(v)-values[best]);total+=cost;assignment.append({'point':ident,'medoid':best,'distance':str(cost)})
 return total,assignment

def pam(points,k,initial):
 validate(points,k,initial);medoids=tuple(sorted(initial));rows=[]
 for iteration in range(32):
  current,assignment=objective(points,medoids);trials=[]
  for removed in medoids:
   for candidate in sorted(set(dict(points))-set(medoids)):
    changed=tuple(sorted((set(medoids)-{removed})|{candidate}));value,_=objective(points,changed);trials.append({'remove':removed,'add':candidate,'medoids':changed,'cost':str(value)})
  best=min(trials,key=lambda r:(F(r['cost']),r['medoids'])) if trials else None
  improve=best is not None and F(best['cost'])<current;rows.append({'iteration':iteration,'medoids':medoids,'cost':str(current),'assignment':assignment,'all_single_swaps':trials,'chosen_improving_swap':best if improve else None})
  if not improve:return medoids,rows
  medoids=tuple(best['medoids'])
 raise ValueError('local bounded iteration cap exceeded')

def independent_cost(points,medoids):
 total=F(0);values=dict(points)
 for ident,x in points:
  distances=[F(abs(x-values[mid])) for mid in medoids];total+=sorted(distances)[0]
 return total

def validate_custom_distances(d):
 if type(d) is not list or not d or any(type(r) is not list or len(r)!=len(d) for r in d) or any(type(v) not in [int,F] or v<0 for r in d for v in r) or any(d[i][i]!=0 or d[i][j]!=d[j][i] for i in range(len(d)) for j in range(len(d))):raise ValueError('symmetric nonnegative finite exact distance matrix with zero diagonal')

def demo():
 points=[(str(i),v) for i,v in enumerate([0,1,2,8,9,10,11,30])];medoids,rows=pam(points,2,('0','2'));assert [r['cost'] for r in rows]==['59','27','26'] and [r['medoids'] for r in rows]==[('0','2'),('0','5'),('1','5')]
 worlds=[{'medoids':ids,'cost':str(independent_cost(points,ids))} for ids in combinations(sorted(dict(points)),2)];assert len(worlds)==28 and min(F(x['cost']) for x in worlds)==F(rows[-1]['cost'])
 extras=[]
 for pts,k,initial in [([('a',0),('b',0),('c',2)],1,('a',)),([('a',0),('b',2)],2,('a','b')),([('a',-1),('b',1)],1,('b',))]:
  result,trace=pam(pts,k,initial);assert independent_cost(pts,result)==F(trace[-1]['cost']);extras.append({'points':pts,'k':k,'result':result,'trace':trace})
 mean=F(sum([0,1,2,100]),4);assert mean not in [0,1,2,100]
 rejected=[]
 for label,fn in [('k_zero',lambda:pam(points,0,())),('k_too_large',lambda:pam(points,9,tuple(str(i) for i in range(9)))),('duplicate_id',lambda:pam([('a',0),('a',1)],1,('a',))),('nonfinite',lambda:pam([('a',float('nan'))],1,('a',))),('negative_distance',lambda:validate_custom_distances([[0,-1],[-1,0]])),('asymmetric_distance',lambda:validate_custom_distances([[0,1],[2,0]]))]:
  try:fn()
  except ValueError:rejected.append(label)
  else:raise AssertionError('expected rejection')
 return {'authored_points':points,'initial_medoids':['0','2'],'best_single_swap_trace':rows,'final_medoid_ids':medoids,'all28_pair_oracle':worlds,'global_minimum_only_for_this_enumerated_fixture':True,'duplicate_values_ties_no_improvement_cases':extras,'mean_not_observed_medoid_counterexample':{'values':[0,1,2,100],'mean':str(mean),'mean_is_observed':False},'invalid_cases_rejected':rejected,'scope':'original bounded PAM best-swap phase with fixed initial medoids, not BUILD/library/benchmark/outlier-proof or all-data global-optimum guarantee; distance matrix negative tests validate only, custom-distance PAM not executed'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))