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? $43,252,003,274,489,856,000$

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. $8!$ $40,320$ $3^7$ $2,187$
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. $\frac{12!}{2}$ $239,500,800$ $12!$ $2^{11}$ $2,048$

Podsumowując, mamy następującą formułę:

8! \times 3^{7} \times \frac{12!}{2} \times 2^{11} = 43, 252, 003, 274, 489, 856, 000

$8!×3^7×\frac{12!}{2}×2^{11} = 43,252,003,274,489,856,000$

^{Ź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:

\frac{8! \times 3^{7} \times 24!^{2}}{24^{7}} = 7, 401, 196, 841, 564, 901, 869, 874, 093, 974, 498, 574, 336, 000, 000, 000

$\frac{8!×3^7×24!^2}{24^7} = 7,401,196,841,564,901,869,874,093,974,498,574,336,000,000,000$

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 : $N$ $N$ $N$ $N$ $N$

1: Formuła Chrisa Hardwicka:

\frac{(24 \times 2^{10} \times 12!)^{N (\mod 2)} \times (7! \times 3^{6}) \times (24!)^{⌊ \frac{1}{4} \times (N^{2} - 2 \times N) ⌋}}{(4!)^{6 \times ⌊ \frac{1}{4} \times (N - 2)^{2} ⌋}}

$\frac{(24×2^{10}×12!)^{N\pmod2}×(7!×3^6)×(24!)^{\lfloor{\frac{1}{4}×(N^2-2×N)}\rfloor}}{(4!)^{6×\lfloor{\frac{1}{4}×(N-2)^2}\rfloor}}$

Wypróbuj na WolframAlpha.

2: Formuła trig Christophera Mowli:

8! \times 3^{7} \times {(\frac{24!}{(4!)^{6}})}^{\frac{1}{4} \times ((N - 1) \times (N - 3) + \cos^{2} (\frac{N \times π}{2}))} \times (24!)^{\frac{1}{2} \times (N - 2 - \sin^{2} (\frac{N \times π}{2}))} \times (12! \times 2^{10})^{\sin^{2} (\frac{N \times π}{2})} \times \frac{1}{24^{\cos^{2} (\frac{N \times π}{2})}}

$8!×3^7×\left(\frac{24!}{(4!)^6}\right)^{\frac{1}{4}×((N-1)×(N-3)+\cos^2(\frac{N×\pi}{2}))}×(24!)^{\frac{1}{2}×(N-2-\sin^2(\frac{N×\pi}{2}))}×(12!×2^{10})^{\sin^2(\frac{N×\pi}{2})}×\frac{1}{24^{\cos^2(\frac{N×\pi}{2})}}$

Wypróbuj na WolframAlpha.

3: Liczby pierwsze Christophera Mowli Wzór:

{2)}^{\frac{1}{2)} \times (2) \times N. \times (N. + 7) - 17 - 11 \times (- 1)^{N.})} \times {3)}^{N. \times (N. + 1) + 2)} \times 5^{\frac{1}{2)} \times (2) \times N. \times (N. - 2)) + 1 + (- 1)^{N.})} \times 7^{\frac{1}{8} \times (6 \times N. \times (N. - 2)) + 3) + 5 \times (- 1)^{N.})} \times 11^{\frac{1}{4} \times (2) \times N. \times (N. - 2)) - 1 + (- 1)^{N.})} \times 96577^{\frac{1}{8} \times (2) \times N. \times (N. - 2)) - 3) + 3) \times (- 1)^{N.})}

$2^{\frac{1}{2}×(2×N×(N+7)-17-11×(-1)^N)}×3^{N×(N+1)+2}×5^{\frac{1}{2}×(2×N×(N-2)+1+(-1)^N)}×7^{\frac{1}{8}×(6×N×(N-2)+3+5×(-1)^N)}×11^{\frac{1}{4}×(2×N×(N-2)-1+(-1)^N)}×96577^{\frac{1}{8}×(2×N×(N-2)-3+3×(-1)^N)}$

gdzie to . $96577$ $(13×17×19×23)$

Wypróbuj na WolframAlpha.

^{Ź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. $N$ $[2,100]$

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. $1.401...×10^{45}$
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). $[2,100]$ $N=100$ $N$
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,10]$

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.

code-golf math number combinatorics rubiks-cube Kevin Cruijssen
źródło

2

Robienie tego w x86-64 będzie fajnym wyzwaniem. Będę musiał stworzyć własnego biginta (prawdopodobnie tylko 256-bitowy lub 512-bitowy int) i zrobić z niego golfa.

moonheart08

1

@ moonheart08 Pamiętaj, że przy N = 100 wynik zajmuje około 128 Kb (16 KB): https://www.wolframalpha.com/input/?i=for+n+%3D+100,+N%5BLog%5B2, + ((24 * 2% 5E10 * 12!)% 5EMod% 5Bn, + 2% 5D + 7! 3% 5E6 + 24!% 5E Podłoga% 5B (n% 5E2 + - + 2 + n)% 2F4% 5D)% 2F4!% 5E (6 + Floor% 5B (n + - + 2)% 5E2% 2F4% 5D)% 5D, 3% 5D

Solomon Ucko

4

Zauważ, że formuła „trig” Mowli używa po prostu i do zaciemnienia s.

\sin^{2}

$\sin^2$

\cos^{2}

$\cos^2$ floor

attinat

4

@attinat, myślę, że bardziej użyteczna perspektywa mówi, że zarówno trygon, jak i podłogi zaciemniają

N mod 2

$N \bmod 2$

Peter Taylor

2

@ChristopherMowla Nie traktuj swoich komentarzy osobiście. Dziwi mnie, że udało ci się znaleźć te formuły i przede wszystkim dokonać tak dokładnych prognoz, a twoje formuły były jedną z inspiracji tego wyzwania. Jest to jednak golf golfowy, więc czytelność, wydajność, ostrzeżenia, najlepsze praktyki, znaczenie historyczne, a czasem po prostu zdrowy rozsądek są wyrzucane za burtę, jeśli można zaoszczędzić jeden bajt na odpowiedzi. ;) attinat i PeterTaylor po prostu zasugerowali taki golf w oparciu o twoje formuły, ponieważ N mod 2 jest nieco krótszy w użyciu w językach programowania niż trig.

Kevin Cruijssen

12

Wolfram Language (Mathematica) , 59 bajtów

f@n_:=(s=24^6)(24!/s)^(m=n-2)f@m
f@2=7!3^6
f@3=4!12!2^10f@2

Ilość permutacji na kostce Rubika NxNxN

Wprowadzenie:

Wyzwanie:

Zasady konkursu:

Główne zasady:

Przypadki testowe:

Odpowiedzi:

Wolfram Language (Mathematica) , 59 bajtów

kod maszynowy x86, 119 bajtów

05AB1E , 38 bajtów

Julia 1.0 , 83 76 bajtów

Python 2 , 72 bajty

Wolfram Language (Mathematica) , 67 bajtów

JavaScript (Node.js) , 81 bajtów

JavaScript (Node.js) , 102 98 96 bajtów

JavaScript (Node.js) , 77 75 73 bajtów

Rakieta , 151 141 bajtów

Python 2 , 122 bajty

Galaretka , 39 38 bajtów

CJam (47 bajtów)

Galaretka , 43 bajty

Ikona , 125 110 bajtów

C (gcc) -lgmp, 279 bajtów

Perl 6 , 85 bajtów

Haskell , 86 85 74 bajtów

Python 2 , 92 bajty

Łuska , 51 48 44 bajtów

C ++, 187 185 180 176 195 (wystąpił błąd) 193 175 bajtów (z pomocą kota na suficie)

TI-BASIC, 63 62 bajtów , (niekonkurencyjny)