import itertools, numpy as np
META={'name':'braid_garside_classification','domain':'algebraic braid presentations','description':'B4 positive braid words with removable left Delta powers; classify parity of sigma1 usage.'}
N=4
SIMPLES=list(itertools.permutations(range(N)))
IDENT=tuple(range(N)); DELTA=tuple(reversed(range(N)))

def compose(p,q): return tuple(p[q[i]] for i in range(N))
def inverse(p):
 z=[0]*N
 for i,v in enumerate(p): z[v]=i
 return tuple(z)
def swap(g):
 p=list(range(N)); p[g-1],p[g]=p[g],p[g-1]; return tuple(p)
def invcount(p): return sum(p[i]>p[j] for i in range(N) for j in range(i+1,N))
def divides(a,b): return invcount(a)+invcount(compose(inverse(a),b))==invcount(b)
def factors(word):
 fs=[]
 for g in word:
  fs.append(swap(g)); i=len(fs)-2
  while i>=0:
   x,y=fs[i],fs[i+1]; comp=compose(inverse(x),DELTA)
   cs=[c for c in SIMPLES if divides(c,comp) and divides(c,y)]
   a=max(cs,key=invcount)
   if a==IDENT: break
   fs[i]=compose(x,a); fs[i+1]=compose(inverse(a),y)
   if fs[i+1]==IDENT: fs.pop(i+1)
   i-=1
 return fs
def factor_id(p): return sum(v*(N+1)**i for i,v in enumerate(p))
def samples(seed,n):
 rng=np.random.RandomState(seed); out=[]
 for _ in range(n):
  base=rng.randint(1,N,size=rng.randint(10,25)).tolist(); k=int(rng.randint(0,4))
  word=DELTA_WORD*k+base; y=sum(g==1 for g in base)%2
  out.append((word,base,y,k))
 return out
DELTA_WORD=[3,2,1,3,2,3]
def get_dataset(seed,n_train=400,n_test=400):
 tr=samples(seed,n_train); te=samples(seed+5000,n_test)
 def raw(es):
  a=np.zeros((len(es),N-1),np.float32)
  for i,(w,b,y,k) in enumerate(es):
   for g in w:a[i,g-1]+=1
   a[i]/=len(w)
  return a
 return {'xtr':raw(tr),'ytr':np.array([e[2] for e in tr]),'xte':raw(te),'yte':np.array([e[2] for e in te]),'task':'classification','metric':'err','out_dim':2}