Dessiner le triangle de Sierpinski a été fait à mort . Nous pouvons cependant faire d’autres choses intéressantes. Si nous plions les yeux au triangle, nous pouvons voir les triangles à l'envers comme des nœuds d'un graphe fractal. Trouvons notre chemin autour de ce graphique!

Premièrement, assignons un numéro à chaque nœud. Le triangle inversé le plus grand sera le nœud zéro, puis nous descendons couche par couche (largeur d'abord) en attribuant des nombres consécutifs dans l'ordre haut-gauche-droite:

^{Cliquez pour une version plus grande où les petits nombres sont un peu moins flous.}

(Bien sûr, ce modèle continue à l' infini dans les triangles bleus.) Une autre façon de définir la numérotation est que le noeud central a l' index 0, et les enfants de noeud i(triangles adjacents de la prochaine plus petite échelle) ont des indices 3i+1, 3i+2et 3i+3.

Comment pouvons-nous nous déplacer dans ce graphique? Il y a jusqu'à six étapes naturelles que l'on peut entreprendre dans n'importe quel triangle:

• On peut toujours passer par le milieu d'une des arêtes à l'un des trois enfants du nœud actuel. Nous désignerons ces mouvements comme N, SWet SE. Par exemple , si nous sommes actuellement sur le nœud 2, ces conduirait à des noeuds 7, 8, 9respectivement. Les autres mouvements à travers les bords (vers les descendants indirects) sont interdits.
• On peut aussi se déplacer dans l’un des trois coins, à condition qu’il ne touche pas le bord du triangle, jusqu’au parent direct ou à l’un des deux ancêtres indirects. Nous désignerons ces mouvements comme S, NEet NW. Par exemple, si nous sommes actuellement sur un nœud 31, Sconduirait à 10, NEserait invalide et NWconduirait à 0.

Le défi

Etant donné deux entiers non négatifs xet y, trouvez le chemin le plus court allant de xà y, en utilisant uniquement les six mouvements décrits ci-dessus. S'il existe plusieurs chemins les plus courts, indiquez l'un d'entre eux.

Notez que votre code devrait fonctionner pour plus que les 5 niveaux décrits dans le diagramme ci-dessus. Vous pouvez supposer que x, y < 1743392200. Cela garantit qu'ils tiennent dans un entier signé 32 bits. Notez que cela correspond à 20 niveaux de l’arbre.

Votre code doit traiter toute entrée valide en moins de 5 secondes . Bien que cela exclue une recherche en force brute avec une largeur d'abord, cela devrait être une contrainte assez vague - mon implémentation de référence gère les entrées arbitraires pour la profondeur 1000 en une demi-seconde (c'est-à-dire des nombres à 480 chiffres pour les nœuds).

Vous pouvez écrire un programme ou une fonction en prenant l’entrée via STDIN (ou l’alternative la plus proche), un argument de ligne de commande ou une argumentation de fonction et en générant le résultat via STDOUT (ou l’alternative la plus proche), une valeur de retour de fonction ou un paramètre de fonction (out).

La sortie doit être une liste plate, sans ambiguïté des cordes N, S, NE, NW, SE, SW, à l' aide de tout séparateur raisonnable (espaces, virgules, retoursLigne, ","...).

Les règles standard de code-golf s'appliquent.

Cas de test

Les premiers cas de test peuvent être élaborés à la main en utilisant le diagramme ci-dessus. Les autres veillent à ce que les réponses soient suffisamment efficaces. Pour ceux-là, il peut y avoir d'autres solutions de même longueur qui ne sont pas listées.

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

Ruby, 195 194 190 184 octets

Original: Toutes mes excuses à Ell , car il s’agit là d’une réponse essentielle et un grand merci à Doorknob pour son aide dans le débogage de cette réponse. Il y a probablement un autre algorithme pour ce problème - quelque chose à voir avec *f[x[0,**however far x matches with y**],y]- mais je le garderai pour une autre fois.

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: L'algorithme glouton ne fonctionne pas pour h[299792458, 1000000]. J'ai renvoyé le nombre d'octets à 195, alors que je répare encore mon algorithme. Correction seulement pour que le nombre d'octets augmente jusqu'à 203. Sigh

En construction: Ce programme utilise un algorithme glouton pour trouver des ancêtres communs x[0,j]==y[0,j](remarque: il peut y avoir plusieurs ancêtres communs). L'algorithme est très vaguement basé sur la recherche récursive d'ancêtres de Ell . La première moitié des instructions qui en résultent explique comment accéder à cet ancêtre commun, et la seconde moitié est basée sur y y[j..-1].

Remarque: a[n]retourne ici une numération bijective de base 3 utilisant les chiffres 2,1,0au lieu de 1,2,3.

Par exemple, parcourons f[59,17]ou f[[2,0,2,1],[2,1,1]]. Ici, j == 1. Pour y aller x[0,j], on y va 0ou NW. Ensuite, pour aller à y, aller [1,1]ouSW 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 octets

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)

Une fonction, fprenant une paire de numéros de nœuds et renvoyant le chemin le plus court sous forme de liste de chaînes.

Explication

Nous commençons par utiliser un schéma d'adressage différent pour les triangles; l'adresse de chaque triangle est une chaîne, définie comme suit:

• L'adresse du triangle central est la chaîne vide.

• Les adresses du nord, au sud-ouest, et les enfants sud-est de chaque triangle sont formés annexant 0, 1et 2, respectivement, à l'adresse du triangle.

Pour l’essentiel, l’adresse de chaque triangle code le chemin le plus court allant du triangle central jusqu’à celui-ci. La première chose que notre programme fait est de traduire les numéros de triangle en entrée en adresses correspondantes.

^{Cliquez sur l'image pour l'agrandir.}

Les mouvements possibles à chaque triangle sont facilement déterminés à partir de l'adresse:

• Pour passer au nord, au sud-ouest, et les enfants du sud-est, nous accoler 0, 1et 2, respectivement, à l'adresse.

• Pour passer au sud, au nord-est, et les ancêtres du nord-ouest, on trouve le dernier ( le plus à droite) de l' apparition 0, 1et 2, respectivement, et couper l'adresse à la gauche de celui - ci. S'il n'y a pas 0, 1ou 2dans l'adresse, l'ancêtre correspondant n'existe pas. Par exemple, pour aller à l'ancêtre nord-ouest de 112(c'est-à-dire son parent), nous trouvons la dernière occurrence de 2in 112, qui est le dernier caractère, et coupons l'adresse à sa gauche, ce qui nous donne 11; pour passer à l'ancêtre nord-est, nous trouvons la dernière occurrence de 1in 112, qui est le deuxième caractère, et coupons l'adresse à sa gauche, ce qui nous donne 1; cependant, 112n’a pas d’ancêtre au sud, puisqu’il n’ya pas de0 dans son adresse.

Notez quelques points concernant une paire d'adresses xet y:

• Si xest une sous - chaîne initiale y, puis yest un descendant de x, et donc le chemin le plus court de xla ysuit simplement l'enfant correspondant de chaque triangle entre xet y; autrement dit, on peut remplacer chaque 0, 1et 2en y[len(x):]avec N, SWet SE, respectivement.

• Sinon, laissez il’indice du premier décalage entre xet y. Il n'y a pas de chemin de xà yqui ne passe pas x[:i](ce qui est la même chose y[:i]), c'est-à-dire le premier ancêtre commun de xet y. Par conséquent, tout chemin de xà ydoit arriver à x[:i], ou à l'un de ses ancêtres, appelons ce triangle zet continuons ensuite y. Pour arriver de xà z, nous suivons les ancêtres comme décrit ci-dessus. Le chemin le plus court de zà yest donné par la puce précédente.

Si xest une sous-chaîne initiale de y, alors le chemin le plus court de xà yest facilement donné par le premier point ci-dessus. Sinon, nous laissons jle plus petit des indices des dernières occurrences 0, 1et 2dans x. Si jest supérieur ou égal à l'indice du premier décalage entre xet y, inous ajoutons simplement le mouvement correspondant ( S, NEou NW, respectivement) sur le chemin, l' assiette xà la gauche j, et continuer. Les choses deviennent plus compliquées si elles jsont inférieures à i, car nous pourrions arriver au yplus rapide en montant x[:j]directement à l'ancêtre commun et en descendant jusqu'au bout.y, ou nous pourrions peut-être arriver à un ancêtre commun différent de xet yc’est plus proche yen remontant à un ancêtre différent de xà droite de i, et aller de là à yplus vite. Par exemple, pour aller de 1222à 1, le chemin le plus court est d’abord d’ascendre vers le triangle central (dont l’adresse est la chaîne vide), puis de descendre vers 1, c’est- à -dire que le premier mouvement nous mène à la gauche du point de discordance. cependant, pour aller de 1222à 12, le chemin le plus court consiste à monter 122, puis à 12, c'est- à -dire que le premier mouvement nous maintient à la droite du point de discordance.

Alors, comment trouver le chemin le plus court? Le programme "officiel" utilise une approche brutale, en essayant tous les mouvements possibles vers l'un des ancêtres chaque fois que ce xn'est pas une sous-chaîne initiale de y. Ce n'est pas aussi mauvais que ça en a l'air! Il résout tous les cas tests, combinés, en une ou deux secondes.

Mais là encore, nous pouvons faire beaucoup mieux: s’il ya plus d’un ancêtre directement joignable à gauche du point d’incompatibilité, il ne reste plus qu’à tester le plus à droite, et s’il ya plus d’un ancêtre directement joignable au à droite du point de mismatch, nous avons seulement besoin de tester le plus à gauche. Cela donne un algorithme temporel linéaire, par rapport à la longueur de x(c'est-à-dire la profondeur du triangle source ou un temps proportionnel au logarithme du numéro du triangle source), qui effectue un zoom sur des cas de test encore plus volumineux. Le programme suivant implémente cet algorithme, du moins par essence. En raison du golf, sa complexité est en fait pire que linéaire, mais il reste très rapide.

Python 2, 271 266 261 octets

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

Notez que, contrairement à la version plus courte, cette version est écrite spécifiquement pour ne pas utiliser la récursion dans la conversion des valeurs en entrée en leurs adresses correspondantes, afin de pouvoir gérer des valeurs très grandes sans déborder de la pile.

Résultats

L'extrait suivant peut être utilisé pour exécuter les tests, pour l'une ou l'autre version, et générer les résultats:

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   )

Version Golfée

         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

Version efficace

         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 118 133 132 130 124 117 octets ^SBCS

Merci beaucoup à Ven et à Ngn pour leur aide à jouer au golf dans The APL Orchard , un endroit formidable pour apprendre le langage APL. ⎕IO←0. Les suggestions de golf sont les bienvenues.

Édition: -12 octets grâce à Ven et ngn en changeant la ndéfinition et en passant de 1 à 2 index. -3 en raison de la correction d'un bogue où tout n'était pas passé à l'indexation 0. -11 octets dus au changement de comment Pet Qsont définis. +15 octets en raison de la résolution d'un problème d'algorithme incorrect, merci beaucoup à ngn pour son aide dans le calcul de la s[⊃⍋|M-s]section. -2 octets pour réorganiser la méthode de recherche du chemin de retour et +1 octet pour la correction des bogues. -2 octets, grâce à Adám, qui a modifié la définition de I. -6 octets grâce à ngn pour avoir réorganisé la définition de 'S' 'NE' 'NW' 'N' 'SW' 'SE'et en réorganisé comment t(la variable n'est plus une variable séparée). -7 octets grâce à ngn de la façon dont le golf sest défini.

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

Essayez-le en ligne!

Une explication du bug dans l'algorithme

Le problème fondamental est que je pensais que le chemin le plus court passait directement par l'ancêtre commun et ne pouvait en fait pas passer par un ancêtre de cet ancêtre commun. Ceci est incorrect comme le montrent les exemples suivants.

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

De 299792458 à 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.

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

Solution alternative utilisant Dyalog Extended et dfns

Si nous utilisons ⎕CY 'dfns'de » adicla fonction, il met en œuvre notre base n numeration bijective (qui a été l'inspiration pour l'utilisation de la version I) pour les octets beaucoup moins. Le passage à Dyalog Extended permet également d’économiser un grand nombre d’octets. Merci beaucoup à Adám pour son aide dans le golf. Suggestions de golf bienvenues!

Edit: -8 octets en raison de la modification de comment Pet Qsont définis. -14 octets en raison du passage à Dyalog Extended. -2 en raison de l’utilisation d’un programme complet pour supprimer les supports DFN {}. +17 octets en raison de la résolution d'un problème d'algorithme incorrect, merci beaucoup à ngn pour son aide dans le calcul de la s[⊃⍋|M-s]section. +1 octet pour la correction de bugs. -2 octets grâce à Adám d'avoir modifié la définition I et -1 octet de se souvenir de mettre mes golfs dans les deux solutions . -3 octets grâce à ngn en réorganisant la génération des directions cardinales, +1 octet pour corriger un golf buggy, et -3 octets grâce à ngn en réorganisant le mode de tdéfinition (il ne s'agit plus d'une variable séparée). -7 octets grâce à ngn en réorganisant la sdéfinition.

APL (Dyalog Extended) , 123 115 101 99 116 117 114 109 102 octets

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

Essayez-le en ligne!