Drawing the Sierpinski triangle has been done to death. 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:
(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
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
SE. E.g. if we're currently on node
2, these would lead to nodes
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
NW. E.g. if we're currently on node
Swould lead to
NEwould be invalid and
NWwould lead to
Given two non-negative integers
y, find the shortest path from
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
SW, using any reasonable separator (spaces, linefeeds, commas,
Standard code-golf rules apply.
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