1# Throwaway preliminary check (Stage B). Re-implemented properly in Stage C.2def P(n,k):3 adj={}4 def add(a,b):5 adj.setdefault(a,set()).add(b); adj.setdefault(b,set()).add(a)6 for i in range(n):7 add(('u',i),('u',(i+1)%n)); add(('u',i),('v',i)); add(('v',i),('v',(i+k)%n))8 return adj9def closure(adj,S):10 B=set(S); changed=True11 while changed:12 changed=False13 for x in list(B):14 w=[y for y in adj[x] if y not in B]15 if len(w)==1: B.add(w[0]); changed=True16 return B17def forces(adj,S): return len(closure(adj,S))==len(adj)18def u(i,n): return ('u',(i-1)%n) # 1-indexed in Rashidi19def v(i,n): return ('v',(i-1)%n)20def thm21_set(n,k):21 r,s=divmod(n,k)22 if s==0: return None23 return {u(j+i*k,n) for i in range(r) for j in range(1,s+3)}, r*(s+2)24def thm22_set(n,k): return {u(j,n) for j in range(1,2*k+3)}25def alameda_set(n,k): return {v(j,n) for j in range(1,2*k+1)}|{u(k,n),u(k+1,n)}26for k in (2,3,5):27 print("k=",k)28 for n in range(2*k+1, 41 if k==5 else 25):29 adj=P(n,k)30 t=thm21_set(n,k)31 a=None32 if t:33 A,b=t; a=(len(A),forces(adj,A))34 print(f" n={n:2d} thm2.1:{a} thm2.2(2k+2):{forces(adj,thm22_set(n,k))} alameda-type({2*k+2}):{forces(adj,alameda_set(n,k))}")35