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:
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+2
i 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
,SW
iSE
. Np jeśli jesteśmy obecnie na węźle2
, to doprowadzi do węzłów7
,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
,NE
iNW
. Np. Jeśli jesteśmy obecnie w węźle31
,S
doprowadziłoby to do10
,NE
byłoby nieprawidłowe iNW
prowadziłoby do0
.
Wyzwanie
Biorąc pod uwagę dwie nieujemne liczby całkowite x
i y
znajdź najkrótszą ścieżkę od x
do 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 gry w golfa .
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
źródło
APL (Dyalog Unicode) ,
144132129118133132130124117 bajtów SBCSBardzo 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
n
definiowania 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ę sposobuP
iQ
definicji. +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ę ws[⊃⍋|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 definicjiI
. -6 bajtów dzięki ngn od zmiany definicji'S' 'NE' 'NW' 'N' 'SW' 'SE'
i od zmiany sposobut
definiowania (nie jest to już osobna zmienna). -7 bajtów dzięki ngn z golfa, jaks
to jest zdefiniowane.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
Od 299792458 do 45687
Objaśnienie kodu
Alternatywne rozwiązanie z wykorzystaniem Dyalog Extended i dfns
Jeśli stosujemy
⎕CY 'dfns'
„Sadic
funkcji 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
P
iQ
definicji. -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 ustalenius[⊃⍋|M-s]
sekcji. +1 bajt do naprawy błędu. -2 bajty dzięki Adámowi z przeredagowania definicjiI
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 sposobut
definiowania (nie jest już osobną zmienną). -7 bajtów dzięki ngn poprzez zmianę sposobus
definiowania.APL (Dyalog Extended) ,
12311510199116117114109 109102 bajtówWypróbuj online!
źródło