Dibujar el triángulo de Sierpinski se ha hecho a la muerte . Sin embargo, hay otras cosas interesantes que podemos hacer con él. Si entrecerramos los ojos lo suficiente en el triángulo, podemos ver triángulos invertidos como nodos de un gráfico fractal. ¡Vamos a orientarnos en ese gráfico!

Primero, asignemos un número a cada nodo. El triángulo invertido más grande será el nodo cero, y luego descenderemos capa por capa (ancho primero), asignando números consecutivos en el orden superior-izquierda-derecha:

^{Haga clic para obtener una versión más grande donde los números pequeños son un poco menos borrosos.}

(Por supuesto, este patrón continúa ad infinitum dentro de los triángulos azules). Otra manera de definir la numeración es que el nodo central tiene el índice 0, y los hijos del nodo i(triángulos adyacentes de la próxima a menor escala) tienen índices 3i+1, 3i+2y 3i+3.

¿Cómo nos movemos alrededor de este gráfico? Hay hasta seis pasos naturales que uno puede tomar desde cualquier triángulo dado:

• Siempre se puede mover a través del punto medio de uno de los bordes a uno de los tres hijos del nodo actual. Designaremos estos movimientos como N, SWy SE. Por ejemplo, si estamos actualmente en el nodo 2, éstos llevaría a nodos 7, 8, 9, respectivamente. Otros movimientos a través de los bordes (a descendientes indirectos) no están permitidos.
• También se puede mover a través de una de las tres esquinas, siempre que no toque el borde del triángulo, ni al padre directo ni a uno de los dos antepasados ​​indirectos. Designaremos estos movimientos como S, NEy NW. Por ejemplo, si actualmente estamos en el nodo 31, Sconduciría a 10, NEsería inválido y NWconduciría a 0.

El reto

Dados dos enteros no negativos xy y, encuentre el camino más corto de xa y, utilizando solo los seis movimientos descritos anteriormente. Si hay varias rutas más cortas, envíe cualquiera de ellas.

Tenga en cuenta que su código debería funcionar para algo más que los 5 niveles representados en el diagrama anterior. Puedes suponer eso x, y < 1743392200. Esto garantiza que quepan dentro de un entero con signo de 32 bits. Tenga en cuenta que esto corresponde a 20 niveles del árbol.

Su código debe procesar cualquier entrada válida en menos de 5 segundos . Si bien esto descarta una búsqueda de amplitud de fuerza bruta, debería ser una restricción bastante flexible: mi implementación de referencia maneja la entrada arbitraria para la profundidad 1000 en medio segundo (eso es ~ números de 480 dígitos para los nodos).

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).

El resultado debe ser una lista plana, sin ambigüedades de las cuerdas N, S, NE, NW, SE, SW, utilizando cualquier separador razonable (espacios, saltos de línea, comas, ","...).

Aplican reglas estándar de código de golf .

Casos de prueba

Los primeros casos de prueba se pueden resolver a mano utilizando el diagrama anterior. Los otros aseguran que las respuestas sean lo suficientemente eficientes. Para aquellos, puede haber otras soluciones de la misma longitud que no se enumeran.

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

Rubí, 195 194 190 184 bytes

Original: con disculpas a Ell , ya que este es esencialmente un puerto de su respuesta y muchas gracias a Doorknob por su ayuda en la depuración de esta respuesta. Probablemente haya otro algoritmo para este problema, algo que ver con eso *f[x[0,**however far x matches with y**],y], pero lo guardaré para otro momento.

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]]}

EDITAR: El algoritmo codicioso no funciona h[299792458, 1000000]. He devuelto el recuento de bytes a 195, mientras reparo mi algoritmo una vez más. Se corrigió solo para que el recuento de bytes aumentara a 203. Suspiro

En construcción: este programa utiliza un algoritmo codicioso para encontrar antepasados ​​comunes x[0,j]==y[0,j](nota: puede haber varios antepasados ​​comunes). El algoritmo se basa muy libremente en la búsqueda recursiva de antepasados ​​de Ell . La primera mitad de las instrucciones resultantes son cómo llegar a este ancestro común, y la segunda mitad se basa en y y[j..-1].

Nota: a[n]aquí devuelve una numeración biyectiva de base 3 usando los dígitos en 2,1,0lugar de 1,2,3.

Como ejemplo, repasemos f[59,17]o f[[2,0,2,1],[2,1,1]]. Aquí, j == 1. Para llegar x[0,j], vamos 0o NW. Luego, para llegar y, ir [1,1]oSW 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]}}

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)

Una función, que ftoma un par de números de nodo y devuelve la ruta más corta como una lista de cadenas.

Explicación

Comenzamos empleando un esquema de direccionamiento diferente para los triángulos; La dirección de cada triángulo es una cadena, definida como sigue:

• La dirección del triángulo central es la cadena vacía.

• Se forman las direcciones de norte, sur-oeste, y los niños del sudeste de cada triángulo añadiendo 0, 1y 2, respectivamente, a la dirección del triángulo.

Esencialmente, la dirección de cada triángulo codifica la ruta (más corta) desde el triángulo central hasta él. Lo primero que hace nuestro programa es traducir los números de triángulo de entrada a las direcciones correspondientes.

^{Haz click en la imagen para una versión más grande.}

Los posibles movimientos en cada triángulo se determinan fácilmente a partir de la dirección:

• Para mover hacia el norte, sur-oeste, y los niños del sudeste, simplemente anexados 0, 1y 2, respectivamente, a la dirección.

• Para mover hacia el sur, noreste, y los ancestros del Noroeste, nos encontramos con el último (más a la derecha) de ocurrencia 0, 1y 2, respectivamente, y recortar la dirección hacia la izquierda de la misma. Si no hay 0, 1o 2en la dirección, entonces el antepasado correspondiente no existe. Por ejemplo, para pasar al ancestro noroeste de 112(es decir, su padre), encontramos la última aparición de 2in 112, que es el último carácter, y recortamos la dirección a la izquierda, dándonos 11; para pasar al antepasado del noreste, encontramos la última aparición de 1in 112, que es el segundo carácter, y recortamos la dirección a la izquierda, dándonos 1; sin embargo, 112no tiene ancestro sur, ya que no hay0 en su direccion.

Tenga en cuenta algunas cosas sobre un par de direcciones xy y:

• Si xes una subcadena inicial de y, entonces yes un descendiente de xy, por lo tanto, el camino más corto desde xhasta ysimplemente sigue el elemento secundario correspondiente de cada triángulo entre xy y; en otras palabras, podemos sustituir cada uno 0, 1y 2en y[len(x):]con N, SWy SE, respectivamente.

• De lo contrario, deje iser el índice de la primera falta de coincidencia entre xy y. No hay un camino de xa yque no pasa a través de x[:i](que es el mismo que y[:i]), es decir, el primer ancestro común de xy y. Por lo tanto, cualquier camino de xa ydebe llegar a x[:i], o uno de sus antepasados, llamemos a este triángulo z, y luego continuemos y. Para llegar de xa z, seguimos a los antepasados ​​como se describió anteriormente. La ruta más corta de za yviene dada por la viñeta anterior.

Si xes una subcadena inicial de y, entonces la ruta más corta desde xa yviene dada fácilmente por el primer punto de viñeta anterior. De lo contrario, nos permiten jser el más pequeño de los índices de los últimos sucesos de 0, 1y 2en x. Si jes mayor que, o igual a, el índice de la primera falta de coincidencia entre xy y, i, simplemente se añade el movimiento correspondiente ( S, NEo NW, respectivamente) a la ruta, el asiento xa la izquierda de j, y continuar. Las cosas se ponen más difíciles si jes menor i, ya que entonces podríamos llegar ymás rápido ascendiendo x[:j]directamente al ancestro común y descendiendo todo el camino hastay, o podríamos llegar a un antepasado común diferente xy ymás cercano al yascender a un antepasado diferente xa la derecha de i, y llegar desde allí a ymás rápido. Por ejemplo, para llegar de 1222a 1, el camino más corto es ascender primero al triángulo central (cuya dirección es la cadena vacía), y luego descender a 1, es decir, el primer movimiento nos lleva a la izquierda del punto de desajuste. sin embargo, para ir de 1222a 12, el camino más corto es ascender a 122, y luego a 12, es decir, el primer movimiento nos mantiene a la derecha del punto de desajuste.

Entonces, ¿cómo encontramos el camino más corto? El programa "oficial" utiliza un enfoque de fuerza bruta, intentando todos los movimientos posibles a cualquiera de los antepasados ​​siempre xque no sea una subcadena inicial y. ¡No es tan malo como parece! Resuelve todos los casos de prueba, combinados, en un segundo o dos.

Pero, de nuevo, podemos hacerlo mucho mejor: si hay más de un antepasado directamente accesible a la izquierda del punto de desajuste, solo necesitamos probar el más a la derecha, y si hay más de un antepasado directamente accesible al a la derecha del punto de desajuste, solo necesitamos probar el extremo izquierdo. Esto produce un algoritmo de tiempo lineal, wrt la longitud de x(es decir, la profundidad del triángulo fuente, o un tiempo proporcional al logaritmo del número del triángulo fuente), que amplía los casos de prueba aún más grandes. El siguiente programa implementa este algoritmo, al menos en esencia, debido al golf, su complejidad es, de hecho, peor que lineal, pero aún así es muy rápida.

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

Tenga en cuenta que, a diferencia de la versión más corta, esta versión está escrita específicamente para no usar la recursividad en la conversión de los valores de entrada a sus direcciones correspondientes, de modo que pueda manejar valores muy grandes sin desbordar la pila.

Resultados

El siguiente fragmento se puede utilizar para ejecutar las pruebas, para cualquier versión, y generar los resultados:

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   )

Versión de golf

         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

Versión eficiente

         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

APL (Dyalog Unicode) , 144 132 129 118 133 132 130 124 117 bytes ^SBCS

Muchas gracias a Ven y ngn por su ayuda para jugar al golf en The APL Orchard , un excelente lugar para aprender el idioma APL. ⎕IO←0. Sugerencias de golf bienvenidas.

Editar: -12 bytes gracias a Ven y ngn cambiando la forma en que nse define y cambiando de indexación 1 a indexación 0. -3 debido a la corrección de un error donde no todo se cambió a 0-indexación. -11 bytes debido al cambio de cómo Py Qse definen. +15 bytes debido a la solución de un problema en el que mi algoritmo era incorrecto, gracias a ngn por ayudarme a calcular la s[⊃⍋|M-s]sección. -2 bytes de reorganizar el método de encontrar la ruta de retroceso y +1 byte para la corrección de errores. -2 bytes gracias a Adám por reorganizar la definición de I. -6 bytes gracias a ngn por reorganizar la definición 'S' 'NE' 'NW' 'N' 'SW' 'SE'y por reorganizar cómo tse define (ya no es una variable separada). -7 bytes gracias a ngn de golf cómo sse define.

{M←⊃⍸≠⌿↑1+P Q←⍵{(⍵/3)⊤⍺-+/3*⍳⍵}¨⌊3⍟1+⍵×2⋄(∪¨↓6 2⍴'SSNENWNNSWSE')[P[I],3+Q↓⍨⊃⌽I←⍬{M≥≢⍵:⍺⋄(⍺∘,∇↑∘⍵)s[⊃⍋|M-s←⌽⊢.⊢⌸⍵]}P]}

Pruébalo en línea!

Una explicación del error en el algoritmo.

El problema básico es que pensé que el camino más corto fue directamente a través del antepasado común y, de hecho, no podía pasar por un antepasado del antepasado común. Esto es incorrecto como lo demostrarán los siguientes ejemplos.

De 66 a 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.

Desde 299792458 hasta 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.

Explicación del código.

                       ⍝ ⍵ 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*⍳⍵    ⍝ 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

Solución alternativa usando Dyalog Extended y dfns

Si usamos ⎕CY 'dfns'la adicfunción, implementa nuestra numeración biyectiva base-n (que fue la inspiración para la versión que uso) para muchos menos bytes. Cambiar a Dyalog Extended también ahorra una gran cantidad de bytes y aquí estamos. Muchas gracias a Adám por su ayuda en el golf. Sugerencias de golf bienvenidas!

Edición: -8 bytes debido a cambios en cómo Py Qse definen. -14 bytes debido al cambio a Dyalog Extended. -2 debido al uso de un programa completo para eliminar los corchetes dfn {}. +17 bytes debido a la solución de un problema en el que mi algoritmo era incorrecto, gracias a ngn por ayudarme a calcular la s[⊃⍋|M-s]sección. +1 byte a la corrección de errores. -2 bytes gracias a Adám por reorganizar la definición I y -1 byte por recordar poner mis campos de golf en ambas soluciones . -3 bytes gracias a ngn reorganizando la generación de las direcciones cardinales, +1 byte al corregir un buggy de golf, y -3 bytes gracias a ngn reorganizando cómo tse define (ya no es una variable separada). -7 bytes gracias a ngn reorganizando cómo sse define.

APL (Dyalog 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]

Pruébalo en línea!