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 ( W
jest biały, G
zielony itp.)
To Wykazano , że istnieje dokładnie (~ trylionów) różne permutacje, że Kostka Rubika może mieć.
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.
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.
- 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.
- 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)
źródło
Odpowiedzi:
Węgiel drzewny ,
334297 bajtówWypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:
Wprowadź liczbę całkowitą do zmiennej
q
.Podziel
q
przez 3⁷, pozostawiając resztęe
. Następnie, biorąc pod uwagęe
liczbę w podstawie 3,e
dodaj cyfrę, aby jej cyfry (w podstawie 3) sumowały się do wielokrotności 3. Pozwalae
to zdefiniować obroty narożników.Podziel
q
przez 8 !, pozostawiając resztęz
. (8! Jest tymczasowo przechowywane wd
celu zapisania bajtu.) Pozwalaz
to zdefiniować pozycje narożników.Podziel
q
przez 2¹¹, pozostawiając resztęh
. Następnie, biorąc pod uwagęh
liczbę w bazie 2,h
dodaj cyfrę, aby jej cyfry (w bazie 2) sumowały się do wielokrotności 2. Pozwalah
to zdefiniować odwrócenie krawędzi.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
.Utwórz tablicę pozycji narożnych.
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ść ww
. 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
.Utwórz tablicę pozycji krawędzi. Zostanie to użyte po raz drugi przez pętlę.
Utwórz tablicę kolorów krawędzi.
Zastąpienie zmiennych narożnych
z
ie
z odpowiednich zmiennych krawędziq
ih
tak, że krawędzie są przesuwane i przerzuconych podczas drugiego przebiegu pętli.źródło
Rubinowy ,
570408 bajtówWypróbuj online!
Oryginalna wersja z tablicami magicznych liczb zamiast magicznych ciągów
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 - 1
a drugi to orientacja elementów w zakresie od 0 do2**11 * 3*7 - 1
. Dane wyjściowe w stanie rozwiązanym to następujący ciąg: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ścioweg
są dzielone przez liczby12..1
z modułem używanym do wybierania i usuwania krawędzi za
i umieszczania jejz
. Po wykonaniu tej czynności pozostaną tylko narożnikia
, więcg
zostaną podzielone przez liczby8..1
z modułem użytym do usunięcia narożnikaa
i umieszczenia goz
.Ponieważ nie ma wystarczających informacji, aby określić kolejność dwóch ostatnich rogów, wartość
g
zostanie podzielona na zero do czasu ich osiągnięcia, więc zawsze będą one dodawanez
w 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
0
lub1
na 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ą a2
lub4
do przodu / tyłu lub a3
lub5
w 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%2048
jest sumowanych, a moduł służy do określania orientacji pierwszej krawędzi.h
mnoż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ówj
. Dla ostatniego rogu (gdziei/19
=1
) wartośćj%3
jest dodawanah
(która zostanie zmniejszona do zera), a to określa orientację ostatniego rogu.Ciąg
b
jest wstępnie zainicjowany z tekstem na środku twarzy.h
dzieli się przez2
dwanaście razy, a następnie przez3
osiem razy, przy czym do określenia orientacji elementów stosuje się moduły. W każdym przypadku podana liczbaz
jest 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
b
do formatu bardziej czytelnego dla człowiekas
przy użyciu magicznych liczb w tabeli indeksów.źródło