[Question]
  [
Drawing the Sierpinski triangle [has been](https://codegolf.stackexchange.com/q/38516/8478) [done to](https://codegolf.stackexchange.com/q/6281/8478) [death](https://codegolf.stackexchange.com/q/62859/8478). There's other interesting things we can do with it though. If we squint hard enough at the triangle, we can view upside-down triangles as nodes of a fractal graph. Let's find our way around that graph!
First, let's assign a number to each node. The largest upside-down triangle will be node zero, and then we just go down layer by layer (breadth-first), assigning consecutive numbers in the order top-left-right:
[![enter image description here](https://i.stack.imgur.com/SSNng.png)](https://i.stack.imgur.com/SSNng.png)  
Click for larger version where the small numbers are a bit less blurry.
(Of course, this pattern continues ad infinitum inside the blue triangles.) Another way to define the numbering is that the centre node has index `0`, and the children of node `i` (adjacent triangles of the next-smaller scale) have indices `3i+1`, `3i+2`, and `3i+3`.
How do we move around this graph? There are up to six natural steps one can take from any given triangle:
* One can always move through the midpoint of one of the edges to one of the three children of the current node. We'll designate these moves as `N`, `SW` and `SE`. E.g. if we're currently on node `2`, these would lead to nodes `7`, `8`, `9`, respectively. Other moves through the edges (to indirect descendants) are disallowed.
* One can also move through one of the three corners, provided it doesn't touch the edge of the triangle, to either the direct parent or one of two indirect ancestors. We'll designate these moves as `S`, `NE` and `NW`. E.g. if we're currently on node `31`, `S` would lead to `10`, `NE` would be invalid and `NW` would lead to `0`.
## The Challenge
Given two non-negative integers `x` and `y`, find the shortest path from `x` to `y`, using only the six moves described above. If there are several shortest paths, output any one of them. 
Note that your code should work for more than just the 5 levels depicted in the above diagram. You may assume that `x, y < 1743392200`. This ensures that they fit inside a 32-bit signed integer. Note that this corresponds to 20 levels of the tree.
Your code must process any valid input in **less than 5 seconds**. While this rules out a brute force breadth-first search, it should be a fairly loose constraint — my reference implementation handles arbitrary input for depth 1000 in half a second (that's ~480-digit numbers for the nodes).
You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.
The output should be a flat, unambiguous list of the strings `N`, `S`, `NE`, `NW`, `SE`, `SW`, using any reasonable separator (spaces, linefeeds, commas, `","`...).
Standard [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") rules apply.
## Test Cases
The first few test cases can be worked out by hand using the diagram above. The others ensure that answers are sufficiently efficient. For those, there may be other solutions of the same length that are not listed.
```
0 40                    => N N N N
66 67                   => S SW N N N
30 2                    => NW NW -or- NE SW
93 2                    => NE SW
120 61                  => NW NW NW NW N SE SW N
1493682877 0            => S S NW NW
0 368460408             => SW SW N N SW SW SE SW SW N SE N N SW SW N SE SE
1371432130 1242824      => NW NW NE NW N SE SW SW SW SE SE SW N N N N SW
520174 1675046339       => 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     => NE NW S SW N N SW SE SE SE SW SE N N SW SE SE SE SW
1238153746 1371016873   => NE NE NE SE N N SW N N SW N SE SE SW N SW N N SE N SE N
547211529 1386725128    => S S S NE NW N N SE N SW N SE SW SE SW N SE SE N SE SW SW N
1162261466 1743392199   => 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
```
  
[Answer]
# 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)
```
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](https://i.stack.imgur.com/kZA3x.png)](https://i.stack.imgur.com/kZA3x.png)
Click the image for a larger version.
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 golfing, its complexity is, in fact, worse than linear, but it's still very fast.
**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
```
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:
```
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
```
[Answer]
# Ruby, ~~195~~ ~~194~~ ~~190~~ 184 bytes
**Original:** With apologies to [Ell](https://codegolf.stackexchange.com/users/31403/ell), as this is essentially a port of their answer and with many thanks to [Doorknob](https://codegolf.stackexchange.com/users/3808/doorknob) for their help in debugging this answer. There's probably another algorithm for this problem - something to do with `*f[x[0,**however far x matches with y**],y]` - but I will save that for another time.
```
a=->n{n<1?[]:a[~-n/3]+[-n%3]}
f=->x,y{j=x.size
(Array===x)?x==y[0,j]?y[j..-1].map{|m|%w[SE SW N][m]}:x.uniq.map{|m|[%w[NW NE S][m],*f[x[0,x.rindex(m)],y]]}.min_by(&:size):f[a[x],a[y]]}
```
**EDIT:** ~~The greedy algorithm doesn't work for `h[299792458, 1000000]`. I have returned the byte count to 195, while I repair my algorithm once more.~~ Fixed it only for the byte count to rise to 203. *Sigh*
**Under construction:** This program uses a greedy algorithm to find common ancestors `x[0,j]==y[0,j]` (note: there may be several common ancestors). The algorithm is based very loosely on [Ell](https://codegolf.stackexchange.com/users/31403/ell)'s recursive ancestor search. The first half of the resulting instructions are how to get to this common ancestor, and the second half is getting to y based on `y[j..-1]`.
Note: `a[n]` here returns a base-3 [bijective numeration](http://en.wikipedia.org/wiki/Bijective_numeration) using the digits `2,1,0` instead of `1,2,3`.
As an example, let's run through `f[59,17]` or `f[[2,0,2,1],[2,1,1]]`. Here, `j == 1`. To get to `x[0,j]`, we go `0` or `NW`. Then, to get to `y`, go `[1,1]` or `SW SW`
```
a=->n{n<1?[]:a[~-n/3]+[-n%3]}
h=->m,n{x=a[m];y=a[n];c=[];j=x.size
(j=x.uniq.map{|m|k=x.rindex(m);x[0..k]==y[0..k]?j:k}.min
c<<%w[NW NE S][x[j]];x=x[0,j])until x==y[0,j]
c+y[j..-1].map{|m|%w[SE SW N][m]}}
```
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), ~~144~~ ~~132~~ ~~129~~ ~~118~~ ~~133~~ ~~132~~ ~~130~~ ~~124~~ 117 [bytes](https://codegolf.meta.stackexchange.com/a/9429/43319 "When can APL characters be counted as 1 byte each?")[SBCS](https://github.com/abrudz/SBCS ".dyalog files using a single byte character set")
Thank you very much to Ven and ngn for their help in golfing this in [The APL Orchard](https://chat.stackexchange.com/rooms/52405/the-apl-orchard), a great place to learn the APL language. `⎕IO←0`. Golfing suggestions welcome.
**Edit:** -12 bytes thanks to Ven and ngn by changing how `n` is defined and switching from 1-indexing to 0-indexing. -3 due to fixing a bug where not everything was switched to 0-indexing. -11 bytes due to changing how `P` and `Q` are defined. +15 bytes due to fixing a problem where my algorithm was incorrect with many thanks to ngn for help with figuring the `s[⊃⍋|M-s]` section. -2 bytes from rearranging the method of finding the backtracking path and +1 byte to bug fixing. -2 bytes thanks to Adám from rearranging the definition of `I`. -6 bytes thanks to ngn from rearranging the definition of `'S' 'NE' 'NW' 'N' 'SW' 'SE'` and from rearranging how `t` is defined (it is no longer a separate variable). -7 bytes thanks to ngn from golfing how `s` is defined.
```
{M←⊃⍸≠⌿↑1+P Q←⍵{(⍵/3)⊤⍺-+/3*⍳⍵}¨⌊3⍟1+⍵×2⋄(∪¨↓6 2⍴'SSNENWNNSWSE')[P[I],3+Q↓⍨⊃⌽I←⍬{M≥≢⍵:⍺⋄(⍺∘,∇↑∘⍵)s[⊃⍋|M-s←⌽⊢.⊢⌸⍵]}P]}
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///qG@qp/@jtgkG/6t9gdSjruZHvTsedS541LP/UdtEQ@0AhUCQcO/Wag0goW@s@ahryaPeXbra@sZaj3o3A8VqD6141NNl/Kh3vqE2kHt4utGj7haNRx2rgOJtk80UjB71blEPDvZz9Qv38wsOD3ZV14wOiPaM1THWBho9@VHvCpClPXs9wfasATqjc@mjzkVAo6yAFoHNAlIdM3QedbQDnQRkAaU0i6PBTu2u8dUtBmns2fuoa5EeED/q2QGUj60NiK39nwY2sg/ix67mQ@uNQQb0TQ0OcgaSIR6ewf/TFIwsLc0tjUxMLRQMDQwMuJAFQDwDBB/IMzNTMIRQpigqTUzNLMyBIoaGZkZGZoYmIHXmJsbGlkaGlpYA "APL (Dyalog Unicode) – Try It Online")
### An explanation of the bug in the algorithm
The basic problem is that I went thought the shortest path went directly through the common ancestor, and could not, in fact, go through an ancestor of the common ancestor. This is incorrect as the following examples will demonstrate.
**From 66 to 5**
```
66 → 0 2 2 2 → 0 2 2 2
5  → 0 1     → 0 1
      ↑ common ancestor
The two ancestors of 0 2 2 2 are:
0 2 2
(empty)
(empty) has the shorter path back to 0 1 as it only needs two forward moves,
while 0 2 2 requires two more backtracks and one more forward move.
```
**From 299792458 to 45687**
```
299792458 → 0 2 1 1 0 1 1 2 1 1 1 2 1 0 2 2 2 0
45687     → 0 2 1 1 0 1 1 1 2 2
                         ↑ common ancestor
The three ancestors of 299792458 are:
0 2 1 1 0 1 1 2 1 1 1 2 1 0 2 2 2
0 2 1 1 0 1 1 2 1 1 1 2            ← choose this one
0 2 1 1 0 1 1 2 1 1 1 2 1 0 2 2
And the three ancestors of 0 2 1 1 0 1 1 2 1 1 1 2 are:
0 2 1 1
0 2 1 1 0 1 1 2 1 1
0 2 1 1 0 1 1 2 1 1 1
0 2 1 1 0 1 1 1 2 2    ← 45687 for reference
             ↑ common ancestor
While it seems like `0 2 1 1` is the shorter path,
it actually results in a path that is 8 steps long
(2 backtracks, 6 forward steps to 45687).
Meanwhile, `0 2 1 1 0 1 1 2 1 1` is at an equal distance
to the common ancestor and has the following ancestors:
0 2 1 1
0 2 1 1 0 1 1 2 1
0 2 1 1 0 1 1
0 2 1 1 0 1 1 1 2 2    ← 45687 for reference
             ↑ common ancestor
Clearly, this is the superior path, as with three backtracks, we have reached
the point of the common ancestor. With 3 backtracks and 3 forward moves,
we have a path that is 6 steps long.
```
## Explanation of the code
```
                       ⍝ ⍵ should be an array of 2 integers, x y
SierpinskiPath←{⎕IO←0  ⍝ 0-indexing
        ⍝ P Q←{...}¨⍵  ⍝ First, the bijective base-3 numeration of x and y
    P Q←{
        n←⌊3⍟1+⍵×2  ⍝ The number of digits in the numeration
        z←+/3*⍳n    ⍝ The number of numerations with ≤ n digits
        (n/3)⊤⍵-z   ⍝ And a simple decode ⊤ (base conversion) of ⍵-z
    }¨⍵             ⍝ gets us our numerations, our paths
    A←↑1+P Q      ⍝ We turn (1+P Q) into an 2-by-longest-path-length array 
                  ⍝ ↑ pads with 0s and our alphabet also uses 0s
                  ⍝ So we add 1 first to avoid erroneous common ancestor matches
    Common←⊃⍸≠⌿A  ⍝ We find the length of the common ancestor, Common
        ⍝ I←⍬{...}P  ⍝ Now we get the shortest backtracking path from P
    I←⍬{
        Common=≢⍵:⍺       ⍝ If P is shorter than Common, return our backtrack path
        s←⌽⊢.⊢⌸⍵          ⍝ Get the indices of the most recent N SW SE
        t←s[⊃⍋|Common-s]  ⍝ and keep the index that is closest to Common
                          ⍝ and favoring the ancestors to the right of
                          ⍝ Common in a tiebreaker (which is why we reverse ⊢.⊢⌸⍵)
        (⍺,t)∇t↑⍵         ⍝ Then repeat this with each new index to backtrack
    }P                    ⍝ and the path left to backtrack through
    Backtrack←P[I]   ⍝ We get our backtrack directions
    Forward←(⊃⌽I)↓Q  ⍝ and our forward moves to Q
                     ⍝ starting from the appropriate ancestor
    (∪¨↓6 2⍴'SSNENWNNSWSE')[Backtrack,Forward]    ⍝ 'S' 'NE' 'NW' 'N' 'SW' 'SE'
}                    ⍝ and return those directions
```
## Alternative solution using Dyalog Extended and dfns
If we use `⎕CY 'dfns'`'s `adic` function, it implements our bijective base-n numeration (which was the inspiration for the version I use) for far fewer bytes. Switching to Dyalog Extended also saves quite a number of bytes and so here we are. Many thanks to Adám for his help in golfing this. Golfing suggestions welcome!
**Edit:** -8 bytes due to changing how `P` and `Q` are defined. -14 bytes due to switching to Dyalog Extended. -2 due to using a full program to remove the dfn brackets `{}`. +17 bytes due to fixing a problem where my algorithm was incorrect with many thanks to ngn for help with figuring the `s[⊃⍋|M-s]` section. +1 byte to bug fixing. -2 bytes thanks to Adám from rearranging the definition of `I` ~~and -1 byte from remembering to put my golfs in both solutions~~. -3 bytes thanks to ngn by rearranging the generation of the cardinal directions, +1 byte from correcting a buggy golf, and -3 bytes thanks to ngn by rearranging how `t` is defined (it is no longer a separate variable). -7 bytes thanks to ngn by rearranging how `s` is defined.
### [APL (Dyalog Extended)](https://github.com/abrudz/dyalog-apl-extended), ~~123~~ ~~115~~ ~~101~~ ~~99~~ ~~116~~ ~~117~~ ~~114~~ ~~109~~ 102 bytes
```
M←⊃⍸≠⌿↑1+P Q←(⍳3)∘⌂adic¨⎕⋄(∪¨↓6 2⍴'SSNENWNNSWSE')[P[I],3+Q↓⍨⊃⌽I←⍬{M≥≢⍵:⍺⋄(⍺∘,∇↑∘⍵){⍵[⊃⍋|M-⍵]}⌽⊢.⊢⌸⍵}P]
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT9dNrShJzUtJTfn/qG@qp/@jtgkGXI862gv@@wKZj7qaH/XueNS54FHP/kdtEw21AxQCgcIaj3o3G2s@6pjxqKcpMSUz@dAKoN5H3S0ajzpWAdltk80UjB71blEPDvZz9Qv38wsOD3ZV14wOiPaM1THWBpow@VHvCpDZPXs9Qbb0rqn2fdS59FHnoke9W60e9e4CmwWkOmboAN0CtBlkV@9WzWogEQ12VHeNry6QE1sLNONR1yI9IH7UswMoUhsQ@x@o578CGBRwGVlamlsamZhaKBgaGBhwYQojxAwU4KJwMTMzBUNkjikWE0xMzSzM4eKGhmZGRmaGJiCd5ibGxpZGhpaWAA "APL (Dyalog Extended) – Try It Online")
]