Pomocy, jestem uwięziony w trójkącie Sierpińskiego!

44

Rysowanie trójkąta Sierpińskiego zostały wykonane do śmierci . Są jednak inne ciekawe rzeczy, które możemy z tym zrobić. Jeśli wystarczająco mocno zerkniemy na trójkąt, możemy zobaczyć odwrócone trójkąty jako węzły wykresu fraktalnego. Znajdźmy sposób na obejście tego wykresu!

Najpierw przypiszmy numer do każdego węzła. Największym trójkątem do góry nogami będzie węzeł zero, a następnie przechodzimy w dół warstwa po warstwie (szerokość-pierwsza), przypisując kolejne liczby w kolejności od lewej do prawej:

wprowadź opis zdjęcia tutaj
Kliknij, aby wyświetlić większą wersję, w której małe liczby są nieco mniej rozmyte.

(Oczywiście, wzór ten trwa nieskończoność wewnątrz niebieskiego trójkąty). Innym sposobem zdefiniowania numeracji że węzeł środek ma wskaźnik 0, a dzieci węzła i(obok trójkąty następnej mniejszej skali) mają współczynnik 3i+1, 3i+2i 3i+3.

Jak poruszamy się po tym wykresie? Z dowolnego trójkąta można wykonać do sześciu naturalnych kroków:

  • Zawsze można przejść przez punkt środkowy jednej z krawędzi do jednego z trzech potomków bieżącego węzła. Będziemy wyznaczyć te ruchy jak N, SWi SE. Np jeśli jesteśmy obecnie na węźle 2, to doprowadzi do węzłów 7, 8, 9, odpowiednio. Inne ruchy przez krawędzie (do pośrednich potomków) są niedozwolone.
  • Można również przejść przez jeden z trzech rogów, pod warunkiem, że nie dotyka on krawędzi trójkąta, do bezpośredniego rodzica lub jednego z dwóch pośrednich przodków. Będziemy wyznaczyć te ruchy jak S, NEi NW. Np. Jeśli jesteśmy obecnie w węźle 31, Sdoprowadziłoby to do 10, NEbyłoby nieprawidłowe i NWprowadziłoby do 0.

Wyzwanie

Biorąc pod uwagę dwie nieujemne liczby całkowite xi yznajdź najkrótszą ścieżkę od xdo y, używając tylko sześciu ruchów opisanych powyżej. Jeśli istnieje kilka najkrótszych ścieżek, wypisz dowolną z nich.

Pamiętaj, że Twój kod powinien działać na więcej niż tylko 5 poziomach przedstawionych na powyższym diagramie. Możesz to założyć x, y < 1743392200. Zapewnia to, że mieszczą się one w 32-bitowej liczbie całkowitej ze znakiem. Zauważ, że odpowiada to 20 poziomom drzewa.

Twój kod musi przetworzyć każde prawidłowe dane wejściowe w mniej niż 5 sekund . Chociaż wyklucza to wyszukiwanie z użyciem siły brute force, powinno to być dość luźne ograniczenie - moja referencyjna implementacja obsługuje dowolne wprowadzanie dla głębokości 1000 w pół sekundy (to jest ~ 480 cyfr dla węzłów).

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Wyjście powinno być płaskie, jednoznaczne lista ciągów N, S, NE, NW, SE, SW, wykorzystujące każdą rozsądną separator (obowiązuje, karetki, przecinki, ","...).

Obowiązują standardowe zasady .

Przypadki testowe

Pierwsze kilka przypadków testowych można rozwiązać ręcznie, korzystając z powyższego schematu. Pozostałe zapewniają, że odpowiedzi są wystarczająco skuteczne. Dla tych mogą istnieć inne rozwiązania o tej samej długości, których nie ma na liście.

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
Martin Ender
źródło

Odpowiedzi:

5

Rubinowy, 195 194 190 184 bajtów

Oryginał: Z przeprosinami dla Ella , ponieważ jest to w zasadzie port ich odpowiedzi i wielkie podziękowania dla Doorknob za ich pomoc w debugowaniu tej odpowiedzi. Prawdopodobnie istnieje inny algorytm dla tego problemu - coś z tym wspólnego *f[x[0,**however far x matches with y**],y]- ale zachowam to na inny czas.

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

EDYCJA: Chciwy algorytm nie działa h[299792458, 1000000]. Zwróciłem liczbę bajtów do 195, a raz jeszcze naprawiam algorytm. Naprawiono to, aby liczba bajtów wzrosła do 203. Westchnienie

W budowie: ten program wykorzystuje chciwy algorytm do znajdowania wspólnych przodków x[0,j]==y[0,j](uwaga: może istnieć kilka wspólnych przodków). Algorytm bazuje na bardzo luźno Ell „s rekurencyjnego wyszukiwania przodków. Pierwsza połowa powstałych instrukcji dotyczy tego, jak dotrzeć do tego wspólnego przodka, a druga połowa opiera się na y y[j..-1].

Uwaga: w a[n]tym przypadku zwraca podstawową numerację bijective 3 za pomocą cyfr 2,1,0zamiast 1,2,3.

Jako przykład, przejdźmy przez f[59,17]lub f[[2,0,2,1],[2,1,1]]. Tutaj j == 1. Aby się dostać x[0,j], idziemy 0lub NW. Następnie, aby dostać się do y, idź [1,1]lubSW 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]}}
Sherlock9
źródło
45

Python 2, 208 205 200 bajtów

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)

Funkcja fpobierająca parę numerów węzłów i zwracająca najkrótszą ścieżkę jako listę ciągów.

Wyjaśnienie

Zaczynamy od zastosowania innego schematu adresowania trójkątów; adres każdego trójkąta jest ciągiem, zdefiniowanym następująco:

  • Adres centralnego trójkąta to pusty ciąg.

  • Adresy północnej, południowo-zachodniej i południowo-wschodniej dzieci każdego trójkąta są utworzone dołączanie 0, 1i 2, odpowiednio, na adres trójkąta.

Zasadniczo adres każdego trójkąta koduje (najkrótszą) ścieżkę od trójkąta centralnego do niego. Pierwszą rzeczą, którą robi nasz program, jest tłumaczenie liczb wejściowych trójkątów na odpowiednie adresy.

Rycina 1

Kliknij obraz, aby powiększyć wersję.

Możliwe ruchy w każdym trójkącie można łatwo ustalić na podstawie adresu:

  • Aby przenieść się na północ, w południowo-zachodniej i południowo-wschodniej dzieci, po prostu append 0, 1i 2, odpowiednio, na adres.

  • Aby przenieść się na południe, północ-wschód, północ-zachód i przodkowie, znajdziemy ostatni (z prawej strony) wystąpienie 0, 1i 2odpowiednio przyciąć i adres, na lewo od niego. Jeśli tam nie ma 0, 1lub 2adres, a następnie odpowiedni przodek nie istnieje. Na przykład, aby przejść do północno-zachodniego przodka 112(tj. Jego rodzica), znajdujemy ostatnie wystąpienie 2in 112, który jest ostatnim znakiem, i przycinamy adres po jego lewej stronie, podając nam 11; aby przejść do przodka północno-wschodniego, znajdujemy ostatnie wystąpienie 1in 112, czyli drugiej postaci, i przycinamy adres po lewej stronie, podając nam 1; jednak 112nie ma południowego przodka, ponieważ nie ma0 w jego adresie.

Zwróć uwagę na kilka rzeczy na temat pary adresów xi y:

  • Jeśli xjest początkowym podciągiem y, to yjest potomkiem x, a zatem najkrótsza ścieżka od xdo ypo prostu podąża za odpowiednim dzieckiem każdego trójkąta między xi y; Innymi słowy, możemy zastąpić każdy 0, 1i 2w y[len(x):]z N, SWi SE, odpowiednio.

  • W przeciwnym razie niech ibędzie indeksem pierwszego niedopasowania między xi y. Nie ma drogi od xcelu y, który nie przechodzi przez x[:i](który jest taki sam jak y[:i]), czyli pierwszy wspólny przodek xi y. Dlatego każda ścieżka od xdo ymusi dotrzeć do x[:i]jednego z jego przodków, nazwijmy ten trójkąt z, a następnie kontynuujmy y. Przyjazd od xcelu z, kierujemy przodków, jak opisano powyżej. Najkrótszą ścieżkę od zdo ypodaje poprzedni punktor.

Jeśli xjest początkowym podciągiem y, to najkrótszą ścieżkę od xdo yłatwo podaje pierwszy punkt powyżej. W przeciwnym razie, niech nam jbyć najmniejszym ze wskaźników z ostatnich wystąpień 0, 1i 2w x. Jeśli jjest większy niż lub równy, indeks pierwszego niedopasowania xi y, ipo prostu dodajemy odpowiedni ruch ( S, NE, lub NW, odpowiednio) do ścieżki, wykończenia xz lewej strony ji kontynuować. Sprawa staje się trudniejsza, jeśli jjest mniejsza niż i, ponieważ odtąd możemy yprzyspieszyć, wstępując bezpośrednio do wspólnego przodka x[:j]i schodząc aż doy, lub może uda nam się dotrzeć do innego wspólnego przodka, xa yto jest bliższe y, wstępując do innego przodka xpo prawej stronie ii stamtąd yszybciej. Na przykład, aby dostać się od 1222do 1, najkrótszą ścieżką jest najpierw wejście do centralnego trójkąta (którego adresem jest pusty ciąg), a następnie zejście do 1, tj. Pierwszy ruch prowadzi nas na lewo od punktu niedopasowania. jednakże, aby dostać się od 1222do 12, najkrótszą ścieżką jest wejście do 122, a następnie do 12, tj. pierwszy ruch utrzymuje nas na prawo od punktu niedopasowania.

Jak więc znaleźć najkrótszą ścieżkę? „Oficjalny” program wykorzystuje podejście brutalnej siły, próbując wszystkich możliwych ruchów do któregokolwiek z przodków, ilekroć xnie jest to początkowy substrat y. Nie jest tak źle, jak się wydaje! Rozwiązuje wszystkie połączone przypadki testowe w ciągu sekundy lub dwóch.

Ale znowu możemy zrobić znacznie lepiej: jeśli na lewo od punktu niedopasowania znajduje się więcej niż jeden przodek osiągalny bezpośrednio, wystarczy przetestować tylko jednego skrajnie prawego, a jeśli jest więcej niż jeden przodek osiągalny bezpośrednio tuż po punkcie niedopasowania musimy przetestować tylko skrajnie lewy. Daje to liniowy algorytm czasu, zapisujący długość x(tj. Głębokość trójkąta źródłowego lub czas proporcjonalny do logarytmu liczby trójkąta źródłowego), który przybliża nawet znacznie większe przypadki testowe. Poniższy program implementuje ten algorytm, przynajmniej w istocie - ze względu na grę w golfa jego złożoność jest w rzeczywistości gorsza niż liniowa, ale nadal jest bardzo szybka.

Python 2, 271 266 261 bajtów

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

Zauważ, że w przeciwieństwie do krótszej wersji, ta wersja została napisana specjalnie po to, aby nie używać rekurencji w konwersji wartości wejściowych na odpowiadające im adresy, dzięki czemu może obsługiwać bardzo duże wartości bez przepełnienia stosu.

Wyniki

Poniższego fragmentu kodu można użyć do uruchomienia testów dla dowolnej wersji i wygenerowania wyników:

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   )

Wersja golfowa

         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

Wydajna wersja

         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
Łokieć
źródło
6
Cholera, to było szybkie. Nie mogę powiedzieć, jak cieszę się z tego za każdym razem, gdy każę ci odpowiedzieć na jedno z moich wyzwań. :)
Martin Ender,
2
@ MartinBüttner Dzięki, to wielki komplement! FWIW, bardzo lubię rozwiązywać twoje wyzwania. Mógłbym, ale może nie, zacząłem pracować nad tym, gdy był jeszcze w piaskownicy ... :)
Ell
2
Schemat adresowania jest genialny. To jest niesamowite.
BrainSteel,
1
@BrainSteel pierwszą rzeczą, która mi się przydarzyła, było wypróbowanie tego schematu adresowania, ale zobaczenie, jak cała koncepcja została opracowana, zaimplementowana i napisana w niecałą godzinę, jest niesamowite. +1
Level River St
1
@Zymus Nie jestem pewien, czy śledzę, ale jeśli masz na myśli zdjęcie, to nie powinno pasować do OP - to inny schemat adresowania, jak opisano w poście.
Ell
3

APL (Dyalog Unicode) , 144 132 129 118 133 132 130 124 117 bajtów SBCS

Bardzo dziękuję Ven i ngn za ich pomoc w graniu w The APL Orchard , doskonałym miejscu do nauki języka APL. ⎕IO←0. Sugestie dotyczące gry w golfa mile widziane.

Edycja: -12 bajtów dzięki Ven i ngn, zmieniając sposób ndefiniowania i przechodząc od indeksowania 1 do indeksowania 0. -3 z powodu naprawienia błędu, w którym nie wszystko zostało przełączone na indeksowanie 0. -11 bajtów ze względu na zmianę sposobu Pi Qdefinicji. +15 bajtów z powodu rozwiązania problemu polegającego na tym, że mój algorytm był niepoprawny i wielu dzięki ngn za pomoc w zorientowaniu się w s[⊃⍋|M-s]sekcji. -2 bajty od przestawienia metody znajdowania ścieżki cofania i +1 bajt na naprawę błędu. -2 bajty dzięki Adámowi z przeredagowania definicji I. -6 bajtów dzięki ngn od zmiany definicji 'S' 'NE' 'NW' 'N' 'SW' 'SE'i od zmiany sposobu tdefiniowania (nie jest to już osobna zmienna). -7 bajtów dzięki ngn z golfa, jak sto jest zdefiniowane.

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

Wypróbuj online!

Wyjaśnienie błędu w algorytmie

Podstawowy problem polega na tym, że pomyślałem, że najkrótsza ścieżka prowadziła bezpośrednio przez wspólnego przodka i nie mogłam w rzeczywistości przejść przez przodka wspólnego przodka. Jest to niepoprawne, co pokażą poniższe przykłady.

Od 66 do 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.

Od 299792458 do 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.

Objaśnienie kodu

                         should be an array of 2 integers, x y
SierpinskiPath←{⎕IO0   0-indexing
         P Q←{...}¨⍵   First, the bijective base-3 numeration of x and y
    P Q←{
        n←⌊31+⍵×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
        ts[⊃⍋|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

    BacktrackP[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

Alternatywne rozwiązanie z wykorzystaniem Dyalog Extended i dfns

Jeśli stosujemy ⎕CY 'dfns'„S adicfunkcji realizuje naszą bijective baza-n numeracji (co zainspirowało I do stosowania wersję) znacznie mniej bajtów. Przejście na Dyalog Extended pozwala także zaoszczędzić sporo bajtów, więc oto jesteśmy. Wielkie podziękowania dla Adama za jego pomoc w grze w golfa. Zapraszamy do gry w golfa!

Edycja: -8 bajtów ze względu na zmianę sposobu Pi Qdefinicji. -14 bajtów z powodu przejścia na Dyalog Extended. -2 z powodu użycia pełnego programu do usunięcia nawiasów dfn {}. +17 bajtów z powodu rozwiązania problemu polegającego na tym, że mój algorytm był niepoprawny i wielu dzięki ngn za pomoc w ustaleniu s[⊃⍋|M-s]sekcji. +1 bajt do naprawy błędu. -2 bajty dzięki Adámowi z przeredagowania definicji I i -1 bajtowi z pamiętania o umieszczeniu moich golfów w obu rozwiązaniach . -3 bajty dzięki ngn przez przestawienie generowania głównych kierunków, +1 bajt od korekty błędnego golfa, i -3 bajty dzięki ngn przez przestawienie sposobu tdefiniowania (nie jest już osobną zmienną). -7 bajtów dzięki ngn poprzez zmianę sposobu sdefiniowania.

APL (Dyalog Extended) , 123 115 101 99 116 117 114 109 109 102 bajtów

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

Wypróbuj online!

Sherlock9
źródło
Dla 66 i 1 nie jest to najkrótsza droga przez 0.
Christian Sievers
@ChristianSievers Masz całkowitą rację i nie jestem pewien, jak to naprawić. Dzięki, że dałeś mi znać.
Sherlock9