5 added 8 characters in body

But then, again, we can do much better: If there is more than one directly reachable ancestor to the left of the point of mismatch, we only need to test the rightmost one, and if there is more than one directly reachable ancestor to the right of the point of mismatch, we only need to test the leftmost one. This yields a linear time algorithm, w.r.t. the length of x (i.e., the depth of the source triangle, or a time proportional to the logarithm of the source triangle number), which zooms through even much larger test cases. The following program implements this algorithm, at least in essence—due to golfing, its complexity is, in fact, quadraticworse than linear, but it's still very fast.

But then, again, we can do much better: If there is more than one directly reachable ancestor to the left of the point of mismatch, we only need to test the rightmost one, and if there is more than one directly reachable ancestor to the right of the point of mismatch, we only need to test the leftmost one. This yields a linear time algorithm, w.r.t. the length of x (i.e., the depth of the source triangle, or a time proportional to the logarithm of the source triangle number), which zooms through even much larger test cases. The following program implements this algorithm, at least in essence—due to golfing, its complexity is, in fact, quadratic, but it's still very fast.

But then, again, we can do much better: If there is more than one directly reachable ancestor to the left of the point of mismatch, we only need to test the rightmost one, and if there is more than one directly reachable ancestor to the right of the point of mismatch, we only need to test the leftmost one. This yields a linear time algorithm, w.r.t. the length of x (i.e., the depth of the source triangle, or a time proportional to the logarithm of the source triangle number), which zooms through even much larger test cases. The following program implements this algorithm, at least in essence—due to golfing, its complexity is, in fact, worse than linear, but it's still very fast.

4 edited body

But then, again, we can do much better: If there is more than one directly reachable ancestor to the left of the point of mismatch, we only need to test the rightmost one, and if there is more than one directly reachable ancestor to the right of the point of mismatch, we only need to test the leftmost one. This yields a linear time algorithm, w.r.t. the length of x (i.e., the depth of the source triangle, or a time proportional to the logarithm of the source triangle number), which zooms through even much larger test cases. The following program implements this algorithm, at least in essence—due to glofinggolfing, its complexity is, in fact, quadratic, but it's still very fast.

But then, again, we can do much better: If there is more than one directly reachable ancestor to the left of the point of mismatch, we only need to test the rightmost one, and if there is more than one directly reachable ancestor to the right of the point of mismatch, we only need to test the leftmost one. This yields a linear time algorithm, w.r.t. the length of x (i.e., the depth of the source triangle, or a time proportional to the logarithm of the source triangle number), which zooms through even much larger test cases. The following program implements this algorithm, at least in essence—due to glofing, its complexity is, in fact, quadratic, but it's still very fast.

But then, again, we can do much better: If there is more than one directly reachable ancestor to the left of the point of mismatch, we only need to test the rightmost one, and if there is more than one directly reachable ancestor to the right of the point of mismatch, we only need to test the leftmost one. This yields a linear time algorithm, w.r.t. the length of x (i.e., the depth of the source triangle, or a time proportional to the logarithm of the source triangle number), which zooms through even much larger test cases. The following program implements this algorithm, at least in essence—due to golfing, its complexity is, in fact, quadratic, but it's still very fast.

3 deleted 10 characters in body

# Python 2, 208205205 200 bytes

A=lambda n:n and A(~-n/3)+[~+[-n%3]or[]
f=lambda x,y:f(A(x),A(y))if x<[]else["SSNEW"[2-mx<[]else["SSNEW"[m::3]for m in
y[len(x):]]if x==y[:len(x)]else min([["NNSWE"[2-m[["NNSWE"[m::3]]+f(x[:~x[::-1].index(m)],y)for
m in set(x)],key=len)


Python 2, 271 266266 261 bytes

def f(x,y):
exec"g=f;f=[]\nwhile y:f=[~f=[-y%3]+f;y=~-y/3\ny=x;"*2;G=["SSNEW"[2-n3\ny=x;"*2;G=["SSNEW"[n::3]for
n in g];P=G+f;p=[];s=0
while f[s:]:
i=len(f)+~max(map(f[::-1].index,f[s:]));m=["NNSWE"[2-f[i];m=["NNSWE"[f[i]::3]]
if f[:i]==g[:i]:P=min(p+m+G[i:],P,key=len);s=i+1
else:p+=m;f=f[:i]
return P


# Python 2, 208205 bytes

A=lambda n:n and A(~-n/3)+[~-n%3]or[]
f=lambda x,y:f(A(x),A(y))if x<[]else["SSNEW"[2-m::3]for m in
y[len(x):]]if x==y[:len(x)]else min([["NNSWE"[2-m::3]]+f(x[:~x[::-1].index(m)],y)for
m in set(x)],key=len)


Python 2, 271 266 bytes

def f(x,y):
exec"g=f;f=[]\nwhile y:f=[~-y%3]+f;y=~-y/3\ny=x;"*2;G=["SSNEW"[2-n::3]for
n in g];P=G+f;p=[];s=0
while f[s:]:
i=len(f)+~max(map(f[::-1].index,f[s:]));m=["NNSWE"[2-f[i]::3]]
if f[:i]==g[:i]:P=min(p+m+G[i:],P,key=len);s=i+1
else:p+=m;f=f[:i]
return P


# Python 2, 208205 200 bytes

A=lambda n:n and A(~-n/3)+[-n%3]or[]
f=lambda x,y:f(A(x),A(y))if x<[]else["SSNEW"[m::3]for m in
y[len(x):]]if x==y[:len(x)]else min([["NNSWE"[m::3]]+f(x[:~x[::-1].index(m)],y)for
m in set(x)],key=len)


Python 2, 271 266 261 bytes

def f(x,y):
exec"g=f;f=[]\nwhile y:f=[-y%3]+f;y=~-y/3\ny=x;"*2;G=["SSNEW"[n::3]for
n in g];P=G+f;p=[];s=0
while f[s:]:
i=len(f)+~max(map(f[::-1].index,f[s:]));m=["NNSWE"[f[i]::3]]
if f[:i]==g[:i]:P=min(p+m+G[i:],P,key=len);s=i+1
else:p+=m;f=f[:i]
return P

2 added 224 characters in body
1