"""Original bounded numeric DTW and independent enumeration of every monotone path."""
from itertools import product
from fractions import Fraction as F
import json

def validate(x,y):
 if any(type(a) is not list or not 1<=len(a)<=4 or any(type(v) not in [int,F] or abs(v)>10 for v in a) for a in [x,y]):raise ValueError('nonempty1..4 exact values abs<=10')

def dtw(x,y):
 validate(x,y);n=len(x);m=len(y);c=[[abs(F(a)-F(b)) for b in y] for a in x];d=[[F(0)]*m for _ in x];parents={}
 for i in range(n):
  for j in range(m):
   if i==j==0:d[i][j]=c[i][j];continue
   options=[(d[a][b],priority,a,b) for priority,(a,b) in enumerate([(i-1,j-1),(i-1,j),(i,j-1)]) if a>=0 and b>=0];v,_,a,b=min(options);d[i][j]=v+c[i][j];parents[i,j]=(a,b)
 cur=(n-1,m-1);path=[cur]
 while cur!=(0,0):cur=parents[cur];path.append(cur)
 path.reverse();validate_path(path,n,m);assert sum(c[i][j] for i,j in path)==d[-1][-1]
 return c,d,path

def validate_path(path,n,m):
 if not path or path[0]!=(0,0) or path[-1]!=(n-1,m-1) or any(not(0<=i<n and 0<=j<m) for i,j in path) or any((b[0]-a[0],b[1]-a[1]) not in [(1,0),(0,1),(1,1)] for a,b in zip(path,path[1:])):raise ValueError('valid boundary, monotone one-step closed-span path required')

def every_path(n,m):
 out=[]
 def walk(i,j,sofar):
  if (i,j)==(n-1,m-1):out.append(sofar);return
  for a,b in [(i+1,j),(i,j+1),(i+1,j+1)]:
   if a<n and b<m:walk(a,b,sofar+[(a,b)])
 walk(0,0,[(0,0)]);return out

def exact_oracle(x,y):return min(sum(abs(F(x[i])-F(y[j])) for i,j in p) for p in every_path(len(x),len(y)))

def demo():
 x=[0,0,1,2];y=[0,1,2,2];c,d,path=dtw(x,y);paths=every_path(4,4);assert len(paths)==63 and d[-1][-1]==exact_oracle(x,y)==0 and sum(abs(a-b) for a,b in zip(x,y))==2
 words=[list(w) for n in range(1,5) for w in product([0,1],repeat=n)];count=0
 for a,b in product(words,repeat=2):
  cc,dd,pp=dtw(a,b);assert dd[-1][-1]==exact_oracle(a,b);count+=1
 extra_x=[0,1,2];extra_y=[0,1,1,2];ec,ed,ep=dtw(extra_x,extra_y);assert ed[-1][-1]==exact_oracle(extra_x,extra_y)==0
 rejected=[]
 for label,fn in [('empty',lambda:dtw([],y)),('bool',lambda:dtw([True],y)),('NaN',lambda:dtw([float('nan')],y)),('Inf',lambda:dtw([float('inf')],y)),('over_budget',lambda:dtw([0]*5,y)),('invalid_step',lambda:validate_path([(0,0),(2,2)],3,3)),('wrong_endpoint',lambda:validate_path([(0,0)],2,2))]:
  try:fn()
  except ValueError:rejected.append(label)
  else:raise AssertionError('expected rejection')
 encode=lambda mat:[[str(v) for v in row] for row in mat]
 return {'X':x,'Y':y,'local_abs_cost':encode(c),'accumulated_cost':encode(d),'path':path,'path_cost':'0','pointwise_L1_cost':2,'all63_paths_costs':[str(sum(c[i][j] for i,j in p)) for p in paths],'all_binary_sequence_pair_oracles':count,'unequal_lengths':{'X':extra_x,'Y':extra_y,'path':ep,'cost':str(ed[-1][-1])},'tie_policy':'diagonal then up then left among equal predecessor cost','invalid_cases_rejected':rejected,'scope':'own tiny exact numeric sequences and raw cost; zero DTW is not sequence equality, probability, universal metric, audio/text quality or alignment-model execution; no SciPy/Numba/librosa/model/Opera claim'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))