Możemy przedstawić Kostkę Rubika jako sieć w następujący sposób (po rozwiązaniu):

   WWW
   WWW
   WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   YYY
   YYY
   YYY

Każda litera reprezentuje odpowiedni kolor ( Wjest biały, Gzielony itp.)

To Wykazano , że istnieje dokładnie (~ trylionów) różne permutacje, że Kostka Rubika może mieć.$43,252,003,274,489,856,000$$43$

Twoim zadaniem jest pobranie liczby całkowitej od do i odpowiedniej permutacji w sposób pokazany powyżej. Możesz wybrać sposób uporządkowania permutacji, ale musisz użyć algorytmu, aby wygenerować unikalną i poprawną permutację dla każdego możliwego wejścia.$1$$43,252,003,274,489,856,000$

Nieprawidłowe reguły permutacji

_{Zaczerpnięte z tej strony}

Na początek środek każdej powierzchni 3x3 musi pozostać taki sam, ponieważ środkowego kwadratu na Kostce Rubika nie można obrócić. Cały sześcian można obracać, zmieniając miejsce, w którym wydaje się znajdować ściana, ale nie wpływa to na sieć sześcianu.

Jeśli mówimy, że każda permutacja ma parzystość, na podstawie parytetu liczby zamian, aby osiągnąć tę permutację, możemy powiedzieć

• Każdy element narożny ma trzy możliwe orientacje. Może być ustawiony prawidłowo (0), zgodnie z ruchem wskazówek zegara (1) lub przeciwnie do ruchu wskazówek zegara (2). Suma orientacji narożnych zawsze pozostaje podzielna przez 3

• Każdy legalny obrót Kostki Rubika zawsze zmienia parzystą liczbę krawędzi, więc nie może być źle ustawiony tylko jeden element.

• Biorąc pod uwagę permutację wszystkich narożników i krawędzi, ogólna parzystość musi być równa, co oznacza, że ​​każdy legalny ruch zawsze wykonuje równowartość parzystej liczby zamian (ignorowanie orientacji)

Na przykład następujące trzy sieci są nieprawidłowymi danymi wyjściowymi:

   WWW
   WWW
   WWW
GGGWWWBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   YYY
   YYY
   YYY

(Too many whites/not enough reds)

   WRW
   WRW
   WRW
GGGRWRBBBOOO
GGGWRRBBBOOO
YYGRWROOOBBB
   YYY
   GGY
   YYY

(There are two red/green center squares and no white/yellow center squares.
 In all valid permutations, the center squares are all different colours)

   WWW
   WWW
   WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBOYOO
   YYY
   YYY
   YYB

(The yellow/orange/blue corner is rotated into an impossible permutation)

Zasady

• Musisz udowodnić, jak chcesz, że algorytm jest poprawny. Nie musisz wyliczać każdej permutacji, o ile udowodnisz poprawność swojego algorytmu.
• $1$$43,252,003,274,489,856,000$
  • $2^{53}-1$$2^{53}-1$
  • Na przykład, jeśli Twój program Javascript nie powiedzie się dla danych wejściowych wyłącznie z tego powodu, że liczba ta jest poza zakresem, to w porządku. Jeśli jednak algorytm zostałby przeniesiony do języka z liczbami całkowitymi o dowolnej wielkości i nie powiódłby się dla tego wejścia, program nie byłby prawidłowy.$27,946,105,037,114,827,095$
• W odpowiedzi musisz podać jakiś dowód ważności. Dowód ten może udowodnić ważność w dowolnej zaakceptowanej metodzie dowodu, z wyjątkiem wyliczenia wszystkich możliwości.
• Możesz wybrać alternatywną metodę wprowadzania, jeśli chcesz, o ile:
  • Dane wejściowe są ograniczone
  • Każde wejście odpowiada jednemu wyjściu
  • Wyjaśniasz dokładnie format wejściowy i sposób, w jaki odpowiada on każdemu wyjściu
• Możesz zmienić znaki używane przy użyciu 6 różnych znaków ASCII, między 33 ( !) a 126 ( ~), zamiastWGRBOY
• Możesz generować dane w dowolny sposób, pod warunkiem, że tworzy wyraźną reprezentację sześcianu, w którym można wyświetlić wszystkie 6 ścian, w tym dowolną prawidłową siatkę sześcianu, pojedynczy ciąg liniowy lub rendering 3D. Jeśli nie masz pewności co do określonego formatu, nie wahaj się zapytać w komentarzach.

To jest golfowy kod, więc wygrywa najkrótszy kod w bajtach w każdym języku.

Przykładowe prawidłowe dane wyjściowe

   YYY
   YYY
   YYY
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   WWW
   WWW
   WWW

(The `W` and `Y` faces have been swapped)

   ZZZ
   +++
   +}}
+[[}77ZZ7bbb
bb[}[[7}}+Z7
bb[}++[}}+Z7
   7bb
   [7Z
   [7Z

(To start with, the colours have been mapped W -> +, G -> b, R -> [, B -> }, O -> Z and Y -> 7.
 Then, the moves L, R, U and F' have been applied, in that order.
 Notice that each centre square is different, and corresponds to the same colour as in the mapping)

Węgiel drzewny , 334 297 bajtów

Ｎθ≔׳﹪θ²¹⁸⁷ε≧⁺﹪±Σ⍘峦³ε≧÷²¹⁸⁷θ≔⁴⁰³²⁰δ≔﹪θδζ≧÷δθ≔⊗﹪θ²⁰⁴⁸η≧⁺﹪Σ⍘粦²η≧÷²⁰⁴⁸θＦ⪪”B"↷:μêKＯ″ＫW#})”³«Ｊ⌕α§ι⁰Ｉ§ι¹§ι²»≔⁰ω≔⪪”A‽}y≔Ｗ⊞≦≦⧴!O×➙⟧ï!Ｙ9⁺`↙1δQ1ξzＴ”⁶υ≔⪪”{➙∧⊙ηr⸿ξd⊕÷M→¡$≧”³δＦ²«Ｆδ«≔§υ⎇⁼Ｌυ⊗ιωζδ≧÷Ｌυζ≧⁺⌕υδω≔Φυ¬⁼λδυＦＬκ«Ｊ⌕α§δ⊗⁺λεＩ§δ⊕⊗⁺λε§κλ»≧÷Ｌκε»≔⪪”A‽}R›Ｋ<≡^μ≡⟦σＤ⎚+πη±t¿e∧Ｌ⸿~↑�w”⁴υ≔⪪”{➙∧⊙ηr⸿ξe'→↑Þ³№¹”²δ≔θζ≔ηε

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

Ｎθ

Wprowadź liczbę całkowitą do zmiennej q.

≔׳﹪θ²¹⁸⁷ε≧⁺﹪±Σ⍘峦³ε≧÷²¹⁸⁷θ

Podziel qprzez 3⁷, pozostawiając resztę e. Następnie, biorąc pod uwagę eliczbę w podstawie 3, edodaj cyfrę, aby jej cyfry (w podstawie 3) sumowały się do wielokrotności 3. Pozwala eto zdefiniować obroty narożników.

≔⁴⁰³²⁰δ≔﹪θδζ≧÷δθ

Podziel qprzez 8 !, pozostawiając resztę z. (8! Jest tymczasowo przechowywane w dcelu zapisania bajtu.) Pozwala zto zdefiniować pozycje narożników.

≔⊗﹪θ²⁰⁴⁸η≧⁺﹪Σ⍘粦²η≧÷²⁰⁴⁸θ

Podziel qprzez 2¹¹, pozostawiając resztę h. Następnie, biorąc pod uwagę hliczbę w bazie 2, hdodaj cyfrę, aby jej cyfry (w bazie 2) sumowały się do wielokrotności 2. Pozwala hto zdefiniować odwrócenie krawędzi.

Ｆ⪪”B"↷:μêKＯ″ＫW#})”³

Pętla nad ciągiem reprezentującym centra.

«Ｊ⌕α§ι⁰Ｉ§ι¹§ι²»

Przejdź do pozycji każdego centrum i wydrukuj ją.

≔⁰ω

Śledź parytet pozycji narożnych w zmiennej w.

≔⪪”A‽}y≔Ｗ⊞≦≦⧴!O×➙⟧ï!Ｙ9⁺`↙1δQ1ξzＴ”⁶υ

Utwórz tablicę pozycji narożnych.

≔⪪”{➙∧⊙ηr⸿ξd⊕÷M→¡$≧”³δ

Utwórz zestaw kolorów narożnych.

Ｆ²«

Pętla dwukrotnie, raz dla narożników, raz dla krawędzi, zwanych dalej „kostkami”.

Ｆδ«

Pętla nad zestawem kolorów kostki.

≔§υ⎇⁼Ｌυ⊗ιωζδ≧÷Ｌυζ≧⁺⌕υδω≔Φυ¬⁼λδυ

Wyodrębnij następną pozycję kostki z, aktualizując parzystość w w. Użyj tej parzystości dla krawędzi przedostatniej. Zapewnia to, że suma parzystości krawędzi i narożników jest równa.

ＦＬκ«Ｊ⌕α§δ⊗⁺λεＩ§δ⊕⊗⁺λε§κλ»

Wydrukuj sześcian w tej pozycji, dostosowany do następnego obrotu lub odwróć odpowiednio.

≧÷Ｌκε»

Usuń obrót lub przerzuć z e.

≔⪪”A‽}R›Ｋ<≡^μ≡⟦σＤ⎚+πη±t¿e∧Ｌ⸿~↑�w”⁴υ

Utwórz tablicę pozycji krawędzi. Zostanie to użyte po raz drugi przez pętlę.

≔⪪”{➙∧⊙ηr⸿ξe'→↑Þ³№¹”²δ

Utwórz tablicę kolorów krawędzi.

≔θζ≔ηε

Zastąpienie zmiennych narożnych zi ez odpowiednich zmiennych krawędzi qi htak, że krawędzie są przesuwane i przerzuconych podczas drugiego przebiegu pętli.

Rubinowy , 570 408 bajtów

->g,h{z=[]
c=a="\x19)!$'%\x177\x1F495.)@7g~yp"
20.times{|i|z<<a[k=g%r=12+i/12*8-i];a[k]="";g/=r}
19.times{|i|z[0..i].map{|j|j>z[i+1]&&c=!c}}
c||(z[19],z[18]=z[18,2])
h+=h+("%b"%(h%2048)).sum%2
j=0
b="023451"
20.times{|i|b<<("%0*o"%[r=2+i/12,z[i].ord-20]*2)[h%r+i/19*j%3,r];j-=r/3*h;h/=r}
s=(t="...
"*3)+(?.*12+$/)*3+t
54.times{|i|s["<QTWZo;MP[ngD@RS^k=GVUpaJ8XYdsAFE?CN7LK9IHl_`jh]reftbc"[i].ord-55]=b[i]}
s}

Wypróbuj online!

Oryginalna wersja z tablicami magicznych liczb zamiast magicznych ciągów

->g,h{z=[]
a=[05,025,015,020,023,021,03,043,013,040,045,041,   032,025,054,043,0123,0152,0145,0134]
#PERMUTE
20.times{|i|r=12+i/12*8-i;z<<a.delete_at(g%r);g/=r}
c=1
19.times{|i|z[0..i].map{|j|j>z[i+1]&&c=!c}}
c||(z[19],z[18]=z[18],z[19])
#ROTATE
h+=h+(h%2048).to_s(2).sum%2
j=0
b="023451"
20.times{|i|r=2+i/12;b<<("%0*o"%[r,z[i]]*2)[h%r+i/19*j%3,r];j-=r/3*h;h/=r}
#DISPLAY
s=(t="...
"*3)+(?.*12+$/)*3+t
54.times{|i|s[
[5,26,29,32,35,56,
4,22,25,36,55,48, 
13,9,27,28,39,52,
6,16,31,30,57,42,
19,1,33,34,45,60,
10,15,14,8,12,23,0,21,20,2,18,17,
53,40,41,51,49,38,59,46,47,61,43,44][i]]=b[i]}
s}

Wypróbuj online!

Anonimowa funkcja, która w obecnej formie przyjmuje dane wejściowe z dwóch liczb całkowitych, co wydaje się być dozwolone: ​​„możesz wybrać alternatywną metodę wprowadzania”. Pierwszy to permutacja w zakresie od 0 do, 12!*8!/2 - 1a drugi to orientacja elementów w zakresie od 0 do 2**11 * 3*7 - 1. Dane wyjściowe w stanie rozwiązanym to następujący ciąg:

000
000
000
222333444555
222333444555
222333444555
111
111
111

Dalsza gra w golfa

Można zapisać około 10 znaków, dostosowując format wyjściowy do następującego kształtu. Ale zmniejszyłoby to czytelność, więc nie będę tego robić w tej chwili

      #########
      #########
      #########
#########
#########
#########

Wyjaśnienie

Permutacja

Wewnętrznie stan rozwiązany jest reprezentowany przez szereg liczb ósemkowych w tablicy a. Dane wejściowe gsą dzielone przez liczby 12..1z modułem używanym do wybierania i usuwania krawędzi z ai umieszczania jej z. Po wykonaniu tej czynności pozostaną tylko narożniki a, więc gzostaną podzielone przez liczby 8..1z modułem użytym do usunięcia narożnika ai umieszczenia go z.

Ponieważ nie ma wystarczających informacji, aby określić kolejność dwóch ostatnich rogów, wartość gzostanie podzielona na zero do czasu ich osiągnięcia, więc zawsze będą one dodawane zw tamtej kolejności. Następnie sprawdzane jest, czy całkowita permutacja jest parzysta czy nieparzysta, aw razie potrzeby dwa ostatnie rogi są zamieniane, aby permutacja była parzysta.

Orientacja

Istnieją różne sposoby decydowania o tym, czy narożnik lub krawędź ma prawidłową orientację, jeśli nie znajduje się w rozwiązanym położeniu. Na potrzeby tej odpowiedzi narożnik jest uważany za ustawiony w prawidłowej orientacji, jeśli pokazuje 0lub 1na górnej lub dolnej powierzchni. Dlatego obrócenie górnej lub dolnej powierzchni nie zmienia orientacji narożnika. Obracanie pozostałych ścian zmienia orientację, ale w taki sposób, że ogólna suma parzystości pozostaje niezmieniona. Krawędzie są traktowane w prawidłowej orientacji, jeśli pokazują a 2lub 4do przodu / tyłu lub a 3lub 5w lewo / w prawo. Oznacza to, że obrót góry lub dołu o ćwierć obrotu powoduje odwrócenie czterech krawędzi, ale obrót pozostałych ścian pozostawia niezmieniony stan odwrócenia.

Dane wejściowe zawierają wyraźne informacje dla wszystkich oprócz pierwszej krawędzi i ostatniego rogu. 11 najmniej znaczących bitów h%2048jest sumowanych, a moduł służy do określania orientacji pierwszej krawędzi. hmnoży się przez 2, dodając go do siebie, a wartość orientacji pierwszej krawędzi jest dodawana jako najmniej znaczący bit. Orientację ostatniego rogu uzyskuje się poprzez stopniowe odejmowanie orientacji innych narożników j. Dla ostatniego rogu (gdzie i/19= 1) wartość j%3jest dodawana h(która zostanie zmniejszona do zera), a to określa orientację ostatniego rogu.

Ciąg bjest wstępnie zainicjowany z tekstem na środku twarzy. hdzieli się przez 2dwanaście razy, a następnie przez 3osiem razy, przy czym do określenia orientacji elementów stosuje się moduły. W każdym przypadku podana liczba zjest konwertowana na ciąg z odpowiednią liczbą cyfr (2 lub 3), a następnie ciąg jest duplikowany. Pozwala to na prawidłowy obrót cyfr ustalony przez moduł, który można wyodrębnić z łańcucha przez indeksowanie i dołączyć dob

Pokaz

Na koniec surowe naklejki są kopiowane bdo formatu bardziej czytelnego dla człowieka sprzy użyciu magicznych liczb w tabeli indeksów.