"""Original 4x4 preference fixture; source 3x3 example not relabeled."""
from itertools import permutations,product
import json

def validate(left,right):
 if type(left) is not dict or type(right) is not dict or not 1<=len(left)==len(right)<=4 or any(type(x) is not str or not x for x in list(left)+list(right)) or set(left)&set(right):raise ValueError('two disjoint equal groups size1..4')
 for table,others in [(left,set(right)),(right,set(left))]:
  for row in table.values():
   if type(row) is not list or len(row)!=len(others) or any(type(x) is not str for x in row) or set(row)!=others:raise ValueError('complete strict preference permutations, no ties/duplicates')

def deferred(left,right,order=None):
 validate(left,right);free=sorted(left) if order is None else list(order)
 if len(free)!=len(left) or set(free)!=set(left):raise ValueError('proposer order permutation')
 nxt={x:0 for x in left};holds={};trace=[]
 while free:
  who=free.pop(0);target=left[who][nxt[who]];nxt[who]+=1;old=holds.get(target)
  if old is None:holds[target]=who;action='held'
  elif right[target].index(who)<right[target].index(old):holds[target]=who;free.append(old);action='replaces_previous_hold'
  else:free.append(who);action='rejected'
  trace.append({'proposer':who,'receiver':target,'previous_hold':old,'action':action,'holds_after':dict(sorted(holds.items()))})
  assert len(trace)<=len(left)**2
 result={p:r for r,p in holds.items()};assert set(result)==set(left) and set(result.values())==set(right)
 return result,trace

def blocking(left,right,matching):
 validate(left,right)
 if type(matching) is not dict or set(matching)!=set(left) or set(matching.values())!=set(right):raise ValueError('perfect bijection')
 inverse={r:p for p,r in matching.items()};out=[]
 for p in left:
  for r in right:
   if matching[p]!=r and left[p].index(r)<left[p].index(matching[p]) and right[r].index(p)<right[r].index(inverse[r]):out.append([p,r])
 return sorted(out)

def demo():
 left={'A':['Y','X','Z','W'],'B':['X','Z','W','Y'],'C':['Z','W','Y','X'],'D':['W','Y','X','Z']}
 right={'X':['A','C','D','B'],'Y':['B','D','A','C'],'Z':['D','B','C','A'],'W':['C','A','B','D']}
 lm,lt=deferred(left,right);rm,rt=deferred(right,left);rm={p:r for r,p in rm.items()};assert not blocking(left,right,lm) and not blocking(left,right,rm)
 worlds=[]
 for perm in permutations(sorted(right)):
  matching=dict(zip(sorted(left),perm));worlds.append({'matching':matching,'blocking_pairs':blocking(left,right,matching)})
 stable=[r['matching'] for r in worlds if not r['blocking_pairs']];assert lm in stable and rm in stable and lm!=rm
 order_checks=0
 for order in permutations(sorted(left)):
  result,_=deferred(left,right,order);assert result==lm;order_checks+=1
 small_checks=0
 for p0,p1,q0,q1 in product(list(permutations('XY')),list(permutations('XY')),list(permutations('AB')),list(permutations('AB'))):
  l={'A':list(p0),'B':list(p1)};r={'X':list(q0),'Y':list(q1)};m,_=deferred(l,r);other,_=deferred(r,l);other={x:y for y,x in other.items()};assert not blocking(l,r,m) and not blocking(l,r,other);small_checks+=1
 branch_left={'A':['Y','X','Z','W'],'B':['Y','X','Z','W'],'C':['Y','Z','W','X'],'D':['W','Y','X','Z']}
 branch_m,branch_trace=deferred(branch_left,right);assert not blocking(branch_left,right,branch_m) and {'held','replaces_previous_hold','rejected'}<=set(x['action'] for x in branch_trace)
 rejected=[]
 bads=[('incomplete',{'A':['X'],'B':['Y']},{'X':['A','B'],'Y':['B','A']}),('duplicate',{'A':['X','X'],'B':['Y','X']},{'X':['A','B'],'Y':['B','A']}),('unequal',{'A':['X','Y']},{'X':['A'],'Y':['A']}),('unknown',{'A':['Q']},{'X':['A']})]
 for label,l,r in bads:
  try:validate(l,r)
  except ValueError:rejected.append(label)
  else:raise AssertionError('expected rejection')
 return {'original_four_by_four_left_preferences':left,'original_four_by_four_right_preferences':right,'left_proposing':{'matching':lm,'proposal_trace':lt},'right_proposing':{'matching_in_left_to_right_orientation':rm,'proposal_trace':rt},'all24_bijections_and_blocking_pairs':worlds,'stable_matchings':stable,'stable_count':len(stable),'proposer_order24_checks_same_left_result':order_checks,'all16_two_by_two_preference_profiles_both_directions':small_checks,'additional_authored_replacement_and_rejection_witness':{'left_preferences':branch_left,'right_preferences':right,'matching':branch_m,'proposal_trace':branch_trace},'invalid_preferences_rejected':rejected,'scope':'strict complete equal fictional groups, original4x4 not renamed sourceExample1; stability is no jointly preferred blocking pair, not minimum cost, fairness, consent or real allocation; validation is local only'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))