"""An exact, standard-library verifier for the 66-tile Chaos Tiles construction. Run this file with Python 3.10 or later. Rows give shape, handedness, parent, parent edge and child edge. Edge indices start at zero. Tile numbers start at one. """ from dataclasses import dataclass from functools import cache, cmp_to_key from itertools import combinations ROWS = [['V+', 0, 0, 0], ['K-', 1, 0, 3], ['V-', 1, 1, 2], ['V+', 2, 0, 1], ['K+', 3, 4, 0], ['V+', 2, 1, 4], ['V+', 1, 2, 0], ['K-', 1, 3, 4], ['V-', 7, 3, 0], ['V-', 7, 2, 2], ['K-', 4, 3, 0], ['K+', 6, 2, 0], ['K+', 6, 1, 3], ['K-', 5, 3, 1], ['V-', 6, 0, 1], ['V-', 9, 3, 1], ['K+', 2, 2, 2], ['V+', 15, 4, 4], ['V-', 5, 4, 1], ['K-', 10, 0, 1], ['V+', 16, 4, 2], ['V-', 19, 3, 4], ['V-', 17, 4, 0], ['K-', 16, 2, 2], ['K+', 9, 2, 1], ['V-', 16, 3, 0], ['K+', 24, 0, 2], ['V-', 27, 0, 0], ['K+', 13, 0, 3], ['K+', 13, 1, 1], ['K+', 12, 2, 4], ['V+', 30, 3, 3], ['V+', 26, 3, 0], ['K-', 26, 4, 2], ['V-', 21, 0, 2], ['K+', 24, 4, 0], ['V+', 25, 3, 4], ['V+', 36, 3, 2], ['V-', 37, 2, 3], ['V-', 28, 3, 0], ['K+', 38, 3, 1], ['K-', 38, 4, 2], ['V+', 28, 4, 2], ['V+', 18, 2, 1], ['V+', 44, 2, 2], ['V+', 23, 3, 4], ['K+', 35, 0, 2], ['K+', 42, 4, 2], ['K+', 23, 4, 4], ['K+', 48, 3, 4], ['V+', 32, 0, 1], ['K-', 35, 1, 2], ['V-', 14, 4, 3], ['V+', 43, 4, 1], ['V+', 51, 4, 2], ['K+', 50, 2, 3], ['K+', 51, 3, 2], ['K+', 56, 1, 4], ['V+', 39, 4, 0], ['K-', 57, 4, 3], ['V-', 54, 3, 3], ['V-', 61, 0, 0], ['V-', 19, 4, 4], ['K+', 48, 4, 4], ['K-', 44, 3, 3], ['K+', 64, 3, 3]] ANGLE = {'V': (4, 8, 3, 7, 5), 'K': (2, 10, 3, 5, 7)} ZERO = (0,) * 6 POLY_ZERO = (0, 0, 0) FULL = (1 << 18) - 1 def add(a,b): return tuple(x+y for x,y in zip(a,b)) def sub(a,b): return tuple(x-y for x,y in zip(a,b)) # A point is in Z[z], where z=exp(i*pi/9) and z^6=z^3-1. def times_z(a): return (-a[5],a[0],a[1],a[2]+a[5],a[3],a[4]) UNITS=[(1,0,0,0,0,0)] for _ in range(17): UNITS.append(times_z(UNITS[-1])) assert times_z(UNITS[-1])==UNITS[0] # Each real polynomial stores its coefficients in 1, s, s^2, # where s=2*cos(pi/9) is the root in (1,2) of s^3-3s-1. def times_s(p): return (p[2],p[0]+3*p[2],p[1]) def trig_table(a,b): values=[a,b] for _ in range(16): values.append(sub(times_s(values[-1]),values[-2])) return values COS=trig_table((2,0,0),(0,1,0)) # Twice the cosine SIN=trig_table(POLY_ZERO,(1,0,0)) # Sine divided by sin(pi/9) @cache def sign(p): if p==POLY_ZERO:return 0 a,b,c=p low,high,den=1,2,1 while True: b0,b1=sorted((b*low*den,b*high*den)) c0,c1=sorted((c*low*low,c*high*high)) if a*den*den+b0+c0>0:return 1 if a*den*den+b1+c1<0:return -1 mid=low+high den*=2 if mid**3-3*mid*den*den-den**3<0:low,high=mid,2*high else:low,high=2*low,mid @cache def projection(z,angle,imaginary): table=SIN if imaginary else COS return tuple(sum(v*table[(j-angle)%18][h] for j,v in enumerate(z)) for h in range(3)) @dataclass class Tile: name:str handed:int turn:int points:list directions:list masks:list edges:list box:tuple def construct(name,handed,turn,origin): points=[]; directions=[]; masks=[] point,angle=origin,turn for j,interior in enumerate(ANGLE[name]): if j:angle=(angle+handed*(9-interior))%18 points.append(point);directions.append(angle);point=add(point,UNITS[angle]) assert point==origin for j,interior in enumerate(ANGLE[name]): start=directions[j] if handed==1 else directions[j-1]+9 masks.append(sum(1<<((start+k)%18) for k in range(interior))) edges=[frozenset((points[i],points[(i+1)%5])) for i in range(5)] box=[] for imag in (False,True): coords=sorted((projection(v,0,imag) for v in points),key=cmp_to_key(lambda a,b:sign(sub(a,b)))) box.extend([coords[0],coords[-1]]) return Tile(name,handed,turn,points,directions,masks,edges,tuple(box)) def attach(parent,u,name,handed,v): initial=construct(name,handed,0,ZERO) same=parent.handed==handed turn=(parent.directions[u]+(9 if same else 0)-initial.directions[v])%18 turning=construct(name,handed,turn,ZERO) target=parent.points[(u+int(same))%5] return construct(name,handed,turn,sub(target,turning.points[v])) def has_small_gap(mask): left=((mask<<1)&FULL)|(mask>>17);right=(mask>>1)|((mask&1)<<17) return bool((~mask)&left&right&FULL) def direction_sign(tile,e,point): return sign(projection(sub(point,tile.points[e]),tile.directions[e],True)) def strictly_on_edge(tile,e,point): diff=sub(point,tile.points[e]);direction=tile.directions[e] if sign(projection(diff,direction,True)):return False distance=projection(diff,direction,False) return sign(distance)>0 and sign(sub(distance,(2,0,0)))<0 def interior(tile,point): if point in tile.points:return False if any(strictly_on_edge(tile,j,point) for j in range(5)):return False height=projection(point,0,True);winding=0 for j in range(5): low=sign(sub(projection(tile.points[j],0,True),height)) high=sign(sub(projection(tile.points[(j+1)%5],0,True),height)) side=direction_sign(tile,j,point) if low<=00:winding+=1 if high<=00 or sign(sub(b.box[i],a.box[i+1]))>0 for i in (0,2)):return True if any(interior(a,p) for p in b.points) or any(interior(b,p) for p in a.points):return False for i,j in ((i,j) for i in range(5) for j in range(5)): if a.points[i]==b.points[j] and a.masks[i]&b.masks[j]:return False if strictly_on_edge(a,i,b.points[j]) or strictly_on_edge(b,j,a.points[i]):return False if direction_sign(a,i,b.points[j])*direction_sign(a,i,b.points[(j+1)%5])<0: if direction_sign(b,j,a.points[i])*direction_sign(b,j,a.points[(i+1)%5])<0:return False return True def signature(a,b): matched=[] for i,e in enumerate(a.edges): for j,f in enumerate(b.edges): if e==f: labels=tuple(sorted((a.name+str(i),b.name+str(j)))) matched.append(('/'.join(labels))+('s' if a.handed==b.handed else 'o')) return tuple(sorted(matched)) def masks_ok(tiles): seen={} for t in tiles: for p,m in zip(t.points,t.masks): if seen.get(p,0)&m:return False seen[p]=seen.get(p,0)|m return all(not has_small_gap(m) for m in seen.values()) def catalog(): valid={} for A,B in [('V','V'),('V','K'),('K','K')]: a=construct(A,1,0,ZERO) for i in range(5): for j in range(5): for handed in (1,-1): b=attach(a,i,B,handed,j) if compatible(a,b) and masks_ok([a,b]): valid[signature(a,b)]=(a,b) return valid def check(): all_duos=catalog() assert len(all_duos)==97 tiles=[];witness={};pairs=0 for idx,(shape,parent,u,v) in enumerate(ROWS,1): name=shape[0];handed=1 if shape[1]=='+' else -1 if idx==1: assert parent==0 tile=construct(name,handed,0,ZERO) else: assert 1<=parent