Python 2, <del>208</del> <del>205</del> 200 bytes === <!-- language: lang-py --> 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) A function, `f`, taking a pair of node numbers, and returning the shortest path as a list of strings. Explanation --- We start by employing a different addressing scheme for the triangles; the address of each triangle is a string, defined as follows: - The address of the central triangle is the empty string. - The addresses of the north, south-west, and south-east children of each triangle are formed appending `0`, `1`, and `2`, respectively, to the address of the triangle. Essentially, the address of each triangle encodes the (shortest) path from the central triangle to it. The first thing our program does is translating the input triangle numbers to the corresponding addresses. [![Figure 1][1]][1] <sup>Click the image for a larger version.</sup> The possible moves at each triangle are easily determined from the address: - To move to the north, south-west, and south-east children, we simply append `0`, `1`, and `2`, respectively, to the address. - To move to the south, north-east, and north-west ancestors, we find the last (rightmost) occurrence of `0`, `1`, and `2`, respectively, and trim the address to the left of it. If there is no `0`, `1`, or `2` in the address, then the corresponding ancestor doesn't exist. For example, to move to the north-west ancestor of `112` (i.e., its parent), we find the last occurrence of `2` in `112`, which is the last character, and trim the address to the left of it, giving us `11`; to move to the north-east ancestor, we find the last occurrence of `1` in `112`, which is the second character, and trim the address to the left of it, giving us `1`; however, `112` has no south ancestor, since there is no `0` in its address. Note a few things about a pair of addresses, `x` and `y`: - If `x` is an initial substring of `y`, then `y` is a descendant of `x`, and therefore the shortest path from `x` to `y` simply follows the corresponding child of each triangle between `x` and `y`; in other words, we can replace each `0`, `1`, and `2` in `y[len(x):]` with `N`, `SW`, and `SE`, respectively. - Otherwise, let `i` be the index of the first mismatch between `x` and `y`. There is no path from `x` to `y` that doesn't pass through `x[:i]` (which is the same as `y[:i]`), i.e., the first common ancestor of `x` and `y`. Hence, any path from `x` to `y` must arrive at `x[:i]`, or one of its ancestors, let's call this triangle `z`, and then continue to `y`. To arrive from `x` to `z`, we follow the ancestors as described above. The shortest path from `z` to `y` is given by the previous bullet point. If `x` is an initial substring of `y`, then the shortest path from `x` to `y` is easily given by the first bullet point above. Otherwise, we let `j` be the smallest of the indices of the last occurrences of `0`, `1`, and `2` in `x`. If `j` is greater than, or equal to, the index of the first mismatch between `x` and `y`, `i`, we simply add the corresponding move (`S`, `NE`, or `NW`, respectively) to the path, trim `x` to the left of `j`, and continue. Things get trickier if `j` is less than `i`, since then we might get to `y` fastest by ascending to the common ancestor `x[:j]` directly and descending all the way to `y`, or we might be able to get to a different common ancestor of `x` and `y` that's closer to `y` by ascending to a different ancestor of `x` to the right of `i`, and get from there to `y` faster. For example, to get from `1222` to `1`, the shortest path is to first ascend to the central triangle (whose address is the empty string), and then descend to `1`, i.e., the first move takes us to the left of the point of mismatch. however, to get from `1222` to `12`, the shortest path is to ascend to `122`, and then to `12`, i.e., the first move keeps us to the right of the point of mismatch. So, how do we find the shortest path? The "official" program uses a brute-force-ish approach, trying all possible moves to any of the ancestors whenever `x` is not an initial substring of `y`. It's not as bad as it sounds! It solves all the test cases, combined, within a second or two. 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. __Python 2, <del>271</del> <del>266</del> 261 bytes__ <!-- language: lang-py --> 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 Note that, unlike the shorter version, this version is written specifically not to use recursion in the conversion of the input values to their corresponding addresses, so that it can handle very large values without overflowing the stack. Results --- The following snippet can be used to run the tests, for either version, and generate the results: <!-- language: lang-py --> def test(x, y, length): path = f(x, y) print "%10d %10d => %2d: %s" % (x, y, len(path), " ".join(path)) assert len(path) == length # x y Length test( 0, 40, 4 ) test( 66, 67, 5 ) test( 30, 2, 2 ) test( 93, 2, 2 ) test( 120, 61, 8 ) test( 1493682877, 0, 4 ) test( 0, 368460408, 18 ) test( 1371432130, 1242824, 17 ) test( 520174, 1675046339, 23 ) test( 312602548, 940907702, 19 ) test( 1238153746, 1371016873, 22 ) test( 547211529, 1386725128, 23 ) test( 1162261466, 1743392199, 38 ) __Golfed Version__ 0 40 => 4: N N N N 66 67 => 5: S SW N N N 30 2 => 2: NE SW 93 2 => 2: NE SW 120 61 => 8: NW NW NW NW N SE SW N 1493682877 0 => 4: S S NW NW 0 368460408 => 18: SW SW N N SW SW SE SW SW N SE N N SW SW N SE SE 1371432130 1242824 => 17: NW NW NE NW N SE SW SW SW SE SE SW N N N N SW 520174 1675046339 => 23: NE NE NE NE SE SE SW SW N SE N SW N SW SE N N N N SE SE SW SW 312602548 940907702 => 19: NE NW S SW N N SW SE SE SE SW SE N N SW SE SE SE SW 1238153746 1371016873 => 22: NE NE NE SE N N SW N N SW N SE SE SW N SW N N SE N SE N 547211529 1386725128 => 23: S S S S NW N N SE N SW N SE SW SE SW N SE SE N SE SW SW N 1162261466 1743392199 => 38: NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE __Efficient Version__ 0 40 => 4: N N N N 66 67 => 5: S SW N N N 30 2 => 2: NW NW 93 2 => 2: NE SW 120 61 => 8: NW NW NW NW N SE SW N 1493682877 0 => 4: NE S NW NW 0 368460408 => 18: SW SW N N SW SW SE SW SW N SE N N SW SW N SE SE 1371432130 1242824 => 17: NW NW NE NW N SE SW SW SW SE SE SW N N N N SW 520174 1675046339 => 23: NE NW NE NE SE SE SW SW N SE N SW N SW SE N N N N SE SE SW SW 312602548 940907702 => 19: NE NW S SW N N SW SE SE SE SW SE N N SW SE SE SE SW 1238153746 1371016873 => 22: NE NE NE SE N N SW N N SW N SE SE SW N SW N N SE N SE N 547211529 1386725128 => 23: S S S S NW N N SE N SW N SE SW SE SW N SE SE N SE SW SW N 1162261466 1743392199 => 38: NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE [1]: https://i.stack.imgur.com/kZA3x.png