import random, itertools, sys, json
from collections import defaultdict
# tiles of the leg-1 tiling: unit square (i,j) split by its odd diagonal into 2 triangles
def cell_tris(i,j):
    c=[(i,j),(i+1,j),(i+1,j+1),(i,j+1)]
    odd=[v for v in c if (v[0]+v[1])%2]  # the two 45-degree corners
    ev=[v for v in c if (v[0]+v[1])%2==0]
    return [ (odd[0],odd[1],ev[0]), (odd[0],odd[1],ev[1]) ]  # right angle at ev
def tile_key(t): return tuple(sorted(t))
def angle_units(t,v):  # in 45-degree units
    return 2 if (v[0]+v[1])%2==0 else 1
ALL={}
def tiles_at(v):
    out=[]
    for i in (v[0]-1,v[0]):
        for j in (v[1]-1,v[1]):
            for t in cell_tris(i,j):
                if v in t: out.append(tile_key(t))
    return out
def boundary(room):
    cnt=defaultdict(int)
    for t in room:
        for a,b in ((t[0],t[1]),(t[1],t[2]),(t[0],t[2])):
            cnt[tuple(sorted((a,b)))]+=1
    return [e for e,c in cnt.items() if c==1]
def polygon(room):
    be=boundary(room)
    adj=defaultdict(list)
    for a,b in be: adj[a].append(b); adj[b].append(a)
    if any(len(x)!=2 for x in adj.values()): return None
    start=be[0][0]; poly=[start]; prev=None; cur=start
    while True:
        n=[x for x in adj[cur] if x!=prev]
        nxt=n[0] if prev is not None else adj[cur][0]
        if nxt==start: break
        poly.append(nxt); prev,cur=cur,nxt
        if len(poly)>len(adj): return None
    if len(poly)!=len(adj): return None
    # drop collinear
    def col(a,b,c): return (b[0]-a[0])*(c[1]-a[1])-(b[1]-a[1])*(c[0]-a[0])==0
    return poly
def score(room,S,D):
    ang=defaultdict(int)
    for t in room:
        for v in t: ang[v]+=angle_units(t,v)
    bad=0
    for v,a in ang.items():
        if v in (S,D): bad+= 0 if a==8 else 5
        elif a==8: bad+=1
        elif a==4: bad+=1
    poly=polygon(room)
    if poly is None: bad+=3
    return bad, poly
def connected(room):
    room=list(room); 
    if not room: return False
    seen={room[0]}; st=[room[0]]; rs=set(room)
    while st:
        t=st.pop()
        for a,b in ((t[0],t[1]),(t[1],t[2]),(t[0],t[2])):
            for u in rs:
                if u not in seen and a in u and b in u: seen.add(u); st.append(u)
    return len(seen)==len(rs)
def neighbors_tiles(room):
    out=set()
    for t in room:
        for v in t:
            for u in tiles_at(v):
                if u not in room: 
                    # share an edge
                    if len(set(u)&set(t))==2: out.add(u)
    return out
def search(S,D,seed,iters=20000):
    random.seed(seed)
    core=set(tiles_at(S))|set(tiles_at(D))
    room=set(core)
    # connect with a straight-ish strip
    while not connected(room):
        nb=list(neighbors_tiles(room)); 
        # prefer tiles toward the midpoint
        mx,my=(S[0]+D[0])/2,(S[1]+D[1])/2
        nb.sort(key=lambda t:sum((v[0]-mx)**2+(v[1]-my)**2 for v in t)+random.random())
        room.add(nb[0])
    best=None; cur=room; cs,_=score(cur,S,D)
    T=1.0
    for it in range(iters):
        new=set(cur)
        if random.random()<0.5:
            nb=list(neighbors_tiles(new)); new.add(random.choice(nb))
        else:
            c=[t for t in new if t not in core]
            if not c: continue
            new.discard(random.choice(c))
            if not connected(new): continue
        s,p=score(new,S,D)
        s2=s*10+len(new)*0.02
        if s2<=cs*10+len(cur)*0.02 or random.random()<T*0.02:
            cur,cs=new,s
        if s==0 and p:
            if best is None or len(p)<len(best[1]): best=(sorted(new),p); print('found',len(p),'sides',len(new),'tiles',flush=True)
        T*=0.9997
    return best
if __name__=='__main__':
    S=(1,0); D=tuple(map(int,sys.argv[1:3])); seed=int(sys.argv[3])
    b=search(S,D,seed,int(sys.argv[4]) if len(sys.argv)>4 else 20000)
    if b: json.dump({'S':S,'D':D,'tiles':b[0],'poly':b[1]},open(f'room_{D[0]}_{D[1]}_{seed}.json','w'))