Wprowadzenie:
Kostka Rubika 3x3x3 ma możliwych , co stanowi około 43 kwintillionów . Być może słyszałeś już o tej liczbie, ale jak to się faktycznie liczy?
Kostka Rubika 3x3x3 ma sześć stron, każda z dziewięcioma naklejkami. Jednak patrząc na (zewnętrzne) elementy zamiast naklejek, mamy sześć elementów środkowych; osiem narożników; i dwanaście kawałków krawędzi. Ponieważ centrów nie można przenieść, możemy zignorować je w obliczeniach. Jeśli chodzi o rogi i krawędzie:
- Jest(40 ) sposobów na ustawienie ośmiu rogów. Każdy narożnik ma trzy możliwe orientacje, chociaż tylko siedem (z ośmiu) można ustawić niezależnie; orientacja ósmego / końcowego rogu zależy od poprzednich siedmiu, biorąc pod uwagę ( ) możliwości.
- Istnieją ( ) sposobów na ułożenie dwunastu krawędzi. Połówka zponieważ krawędzie muszą zawsze znajdować się w równej permutacji dokładnie wtedy, gdy są narożniki. Jedenaście krawędzi można odwracać niezależnie, z odwróceniem krawędzi dwunastej / końcowej w zależności od poprzedzającej jedenastki, biorąc pod uwagę ( ) możliwości.
Podsumowując, mamy następującą formułę:
Źródło: Wikipedia - Permutacje kostki Rubika
Chociaż może to już wyglądać dość skomplikowane, wciąż jest dość proste jak na kostkę 3x3x3. W przypadku nawet kostek formuła jest nieco inna; oto wzór na kostkę 4x4x4 na przykład:
To jest około 7,40 quattuordecillion w krótkiej skali .
A w przypadku większych kostek NxNxN (tj. Aktualny rekord świata 33x33x33) formuła zostanie nieco rozszerzona. Aby jednak nie wprowadzać tego wprowadzenia zbyt długo, umieściłem tutaj te linki, gdzie wyjaśniono permutacje kostki 4x4x4 i innych kostek NxNxN o innych rozmiarach z uzyskaną formułą:
Być może już się zastanawiasz: czy istnieje ogólna formuła oparta na dla dowolnej kostki x x ? Z pewnością jest. Oto trzy zupełnie różne algorytmy, z których wszystkie dają dokładnie takie same wyniki w oparciu o :
1: Formuła Chrisa Hardwicka:
2: Formuła trig Christophera Mowli:
3: Liczby pierwsze Christophera Mowli Wzór:
gdzie to .
Źródło: Cubers-reddit - Matematyczne formuły liczenia liczby pozycji, liczby Boga itp.
Wyzwanie:
Wybierz i zaimplementuj jedną z tych trzech formuł (lub własną pochodną), która podając liczbę całkowitą wejściową w zakresie , daje prawidłowy wynik.
Zasady konkursu:
- Możesz użyć innej formuły oprócz tych trzech, ale pamiętaj, że te trzy okazały się poprawne. Jeśli używasz innej formuły, dodaj link, skąd ją masz (lub jeśli sam ją wymyślisz, dodaj dogłębne wyjaśnienie). I sprawdzę, czy wszystkie liczby całkowite w zakresie są prawidłowe. Być może inspirację można znaleźć w Oeis dla tej sekwencji: A075152 .
- Jeśli twój język automatycznie generuje wyniki naukowe (tj. zamiast liczby po formule 4x4x4), jest to dozwolone. Ale proszę dodać dodatkowy kod do swojej odpowiedzi, aby przekonwertować to zaokrąglenie naukowe na dokładny wynik, aby można było zweryfikować wyniki, ponieważ błędy zaokrąglania wynikające z precyzji zmiennoprzecinkowej podczas wykonywania formuły w kodzie są niedozwolone - rzeczywisty wynik powinien być dokładny.
- Twój program / funkcja powinna być poprawna co najmniej dla danych wejściowych z zakresu (chociaż, ponieważ już daje ogromną liczbę, każdy większy prawdopodobnie będzie również działał, jeśli będziesz w stanie to wyprowadzić jeden poprawnie).
- Nie można zapętlać wszystkich możliwych kombinacji z licznikiem, ponieważ nigdy nie dałoby to niczego w rozsądnym czasie. Tylko wdrożenie formuły (jednej z trzech podanych, pochodnej jednej z nich lub zupełnie nowej formuły) lub innej metody, która da prawidłowe wyniki w rozsądnym czasie (oczywiście bez twardego kodowania) ) jest dozwolone. Myślałem o dodaniu ograniczonego czasu, aby to wymusić, ale osobiście jestem przeciwny ograniczonemu czasowi w połączeniu z golfem , więc nie zrobię tego. Mimo to upewnij się, że Twój program udziela odpowiedzi, a jeśli z jakiegoś powodu jest zbyt wolny dla TIO, dodaj kilka zrzutów ekranu z danymi wyjściowymi z komputera lokalnego w celu weryfikacji.
Główne zasady:
- To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.
Nie pozwól, aby języki gry w golfa zniechęcały Cię do publikowania odpowiedzi w językach niekodujących golfa. Spróbuj znaleźć możliwie najkrótszą odpowiedź na „dowolny” język programowania. - Do odpowiedzi mają zastosowanie standardowe reguły z domyślnymi regułami We / Wy , więc możesz używać STDIN / STDOUT, funkcji / metody z odpowiednimi parametrami i typem zwracanych, pełnych programów. Twoja decyzja.
- Domyślne luki są zabronione.
- Jeśli to możliwe, dodaj link z testem kodu (tj. TIO ).
- Zalecane jest również dodanie wyjaśnienia do odpowiedzi.
Przypadki testowe:
Oto przypadki testowe dla w zakresie (możesz użyć powyższych linków WolframAlpha dla większych przypadków testowych):
n=2
3674160
n=3
43252003274489856000
n=4
7401196841564901869874093974498574336000000000
n=5
282870942277741856536180333107150328293127731985672134721536000000000000000
n=6
157152858401024063281013959519483771508510790313968742344694684829502629887168573442107637760000000000000000000000000
n=7
19500551183731307835329126754019748794904992692043434567152132912323232706135469180065278712755853360682328551719137311299993600000000000000000000000000000000000
n=8
35173780923109452777509592367006557398539936328978098352427605879843998663990903628634874024098344287402504043608416113016679717941937308041012307368528117622006727311360000000000000000000000000000000000000000000000000
n=9
14170392390542612915246393916889970752732946384514830589276833655387444667609821068034079045039617216635075219765012566330942990302517903971787699783519265329288048603083134861573075573092224082416866010882486829056000000000000000000000000000000000000000000000000000000000000000
n=10
82983598512782362708769381780036344745129162094677382883567691311764021348095163778336143207042993152056079271030423741110902768732457008486832096777758106509177169197894747758859723340177608764906985646389382047319811227549112086753524742719830990076805422479380054016000000000000000000000000000000000000000000000000000000000000000000000000000000000
UWAGA: Ponieważ jest to wyzwanie dla golfa , sprowadza się ono do: wdrożenia jednej z tych trzech formuł (lub pochodnej / własnej metody, która nadal daje prawidłowe wyniki) tak krótko, jak to możliwe.
floor