Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
5 added 8 characters in body
source | link

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
source | link

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
source | link

Python 2, 208 205205 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, 208 205 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, 208 205 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
source | link
1
source | link