GolfScript, 39/83 bajtów
# Optimized for size:
{.4rand.p.2/+>`{?1420344440`=}+$..$>}do
# Optimized for speed:
6,(7++:t;~{.(1=.@7=9=+4\-rand+..2/+@.@>:s^[3s=0s=2s=4s=1s=]+s|.)9<\t>|}do.$>30764`*
Szybkość a rozmiar
Wersja zoptymalizowana pod względem wielkości losowo wybiera obroty zgodnie z ruchem wskazówek zegara, aż do uzyskania pożądanej permutacji. Jest to wystarczające, ponieważ obrót w kierunku przeciwnym do ruchu wskazówek zegara jest równoważny trzem kolejnym obrotom tego samego kwadratu zgodnie z ruchem wskazówek zegara.
Wersja zoptymalizowana pod kątem prędkości robi to samo, z wyjątkiem następujących czynności:
Jeśli liczba 1 znajduje się w lewym górnym rogu, nie obraca już lewego górnego kwadratu.
Jeśli liczba 9 znajduje się w prawym dolnym rogu, nie obraca już prawego dolnego kwadratu.
Kroki do zamiany pozycji 7 i 8 są zakodowane na stałe, więc są dwie pozycje, które pozwalają na przerwanie pętli.
Oprócz zmiany algorytmu, wersja zoptymalizowana pod kątem prędkości osiąga obrót w prosty sposób, podczas gdy wersja o zoptymalizowanym rozmiarze korzysta z wbudowanego sortowania GolfScript przez mapowanie. Określa również stan końcowy (dla porównania) zamiast sortować stan w każdej iteracji.
Wersja zoptymalizowana pod kątem prędkości wymaga mniej iteracji, a każda iteracja jest znacznie szybsza sama w sobie.
Benchmarki
Użyłem następującego kodu do randomizacji pozycji liczb i wykonania testów, odkomentowując wiersz odpowiadający testowanej wersji:
[{[
0:c;10,1>{;2 32?rand}$
#{c):c;.4rand.2/+>`{?1420344440`=}+$..$>}do
#6,(7++:t;{.(1=.@7=9=+4\-rand+..2/+@.@>:s^[3s=0s=2s=4s=1s=]+s|.)9<\t>|}do.$>30764`*
],c+}\~*]
$.0='Min: '\+puts .-1='Max: '\+puts ..{+}*\,/'Avg: '\+puts .,2/='Med: '\+
Dane wyjściowe pokazują minimalną i maksymalną liczbę kroków, które wykonano, aby uporządkować liczby, średnią i medianę wszystkich przebiegów, a także czas, jaki upłynął w sekundach:
$ TIME='\n%e s' time golfscript rotation-test-size.gs <<< 100
Min: 4652
Max: 2187030
Avg: 346668
Med: 216888
21500.10 s
$
$ TIME='\n%e s' time golfscript rotation-test-speed.gs <<< 1000
Min: 26
Max: 23963
Avg: 3036
Med: 2150
202.62 s
Na moim komputerze (Intel Core i7-3770) średni czas wykonania wersji zoptymalizowanej pod względem wielkości wynosił 3,58 minuty. Średni czas wykonania wersji zoptymalizowanej pod kątem prędkości wynosił 0,20 sekundy. Dlatego wersja zoptymalizowana pod kątem prędkości jest około 1075 razy szybsza.
Wersja zoptymalizowana pod kątem prędkości zapewnia 114 razy mniej obrotów. Wykonywanie każdego obrotu jest 9,4 razy wolniejsze, co wynika głównie ze sposobu aktualizacji stanu.
I / O
Wyjście składa się z liczb 3-bitowych. MSB jest ustawiony na obroty przeciwnie do ruchu wskazówek zegara, środkowy bit jest ustawiony na dolne kwadraty, a LSB jest ustawiony na prawe kwadraty. Zatem 0 (4) jest lewym górnym kwadratem, 1 (5) prawym górnym, 2 (6) lewym dolnym i 3 (7) prawym dolnym.
Wersja o zoptymalizowanej prędkości drukuje wszystkie obroty w jednym wierszu. Wersja zoptymalizowana pod względem wielkości drukuje jeden obrót na linię, a następnie końcową pozycję liczb.
W przypadku wersji zoptymalizowanej pod kątem prędkości dane wejściowe muszą dać tablicę zawierającą liczby od 1 do 9, gdy zostaną ocenione. W przypadku wersji zoptymalizowanej pod względem wielkości wejściowym musi być ciąg bez końcowej nowej linii; nie podlega ocenie.
Przykładowe przebiegi:
$ echo -n '253169748' | golfscript rotation-size.gs
3
0
123456789
$ golfscript rotation-speed.gs <<< '[5 4 7 1 2 9 3 8 6]'
2210300121312212222212211121122211122221211111122211211222112230764
Kod zoptymalizowany pod kątem rozmiaru
{ #
. # Duplicate the state.
4rand # Push a randomly chosen integers between 0 and 3.
.p # Print that integer.
.2/+ # Add 1 to it if it is grater than one. Possible results: 0, 1, 3, 4
>` # Slice the state at the above index.
{ # Push a code block doing the following:
? # Get the index of the element of the iteration in the sliced state.
1420344440` # Push the string "14020344440".
= # Retrieve the element at the position of the computed index.
}+ # Concatenate the code block with the sliced state.
$ # Sort the state according to the above code block. See below.
..$> # Push two copies of the state, sort the second and compare the arrays.
}do # If the state is not sorted, repeat the loop.
Aktualizacja stanu odbywa się w następujący sposób:
Obrót 2 daje liczbę całkowitą 3 po dodaniu 1. Jeśli stan to „123456789”, przecięcie stanu daje „456789”.
Tuż przed wykonaniem „$” najwyższe elementy stosu to:
[ 1 2 3 4 5 6 7 8 9 ] { [ 4 5 6 7 8 9 ] ? "1420344440" = }
„$” Wykonuje blok raz dla każdego elementu tablicy, który ma zostać posortowany, po naciśnięciu samego elementu.
Indeks 1 w „[4 5 6 7 8 9]” wynosi -1 (brak), więc ostatni element „1420344440” jest wypychany. Daje to 48, kod ASCII odpowiadający znakowi 0. W przypadku 2 i 3 48 jest również wypychane.
Liczby całkowite wypchnięte dla 4, 5, 6, 7, 8 i 9 to 49, 52, 50, 48, 51 i 52.
Po posortowaniu pierwszym elementem stanu będzie jeden z elementów dających 48; ostatnia będzie jedną z tych, które dają 52. Wbudowany rodzaj jest ogólnie niestabilny, ale empirycznie zweryfikowałem, że jest stabilny w tym konkretnym przypadku.
Wynik to „[1 2 3 7 4 6 8 5 9]”, co odpowiada obrotowi lewego dolnego kwadratu w prawo.
Kod zoptymalizowany pod kątem prędkości
6,(7++:t; # Save [ 1 2 3 4 5 7 ] in variable “t” and discard it.
~ # Interpret the input string.
{ #
:s # Duplicate the current state.
(1= # Unshift the first element and push 1 if it is equal to 1 and 0 otherwise.
.@ # Duplicate the boolean and rotate the unshifted array on top of it.
7=9= # Push 1 if the eighth element of “s” is equal to 9 and 0 otherwise.
+4\- # Add the booleans and subtract their sum from 4.
rand # Push a randomly chosen integers between 0 and the result from above.
+. # Add this integer to the first boolean and duplicate it for the output.
.2/+ # Add 1 to the result if it is grater than one. Possible results: 0, 1, 3, 4
@. # Rotate the state on top of the stack and duplicate it.
@>:s # Slice the state at the integer from above and save the result in “s”.
^ # Compute the symmetric difference of state and sliced state.
[ # Apply a clockwise rotation to the sliced array:
3s= # The fourth element becomes the first.
0s= # The first element becomes the second.
2s= # The third element remains the same.
4s= # The fifth element becomes the fourth.
1s= # The second element becomes the fifth.
] # Collect the results into an array.
+ # Concatenate with array of elements preceding the slice.
s| # Perform set union to add the remaining elements of “s”.
. # Duplicate the updated state.
)9< # Pop the last element; push 0 if it is equal to 9 and 1 otherwise.
\t # Swap the popped state on top and push [ 1 2 3 4 5 7 ].
> # Push 0 if the state begins with [ 1 2 3 4 5 6 ] and 1 otherwise.
| # Take the logical OR of the booleans.
}do # If the resulting boolean is 1, repeat the loop.
.$ # Duplicate the state and sort it.
>30764`* # If the state was not sorted, 7 and 8 are swapped, so push "30764".
Zauważ, że obroty 3, 0, 7, 6 i 4 zamieniają elementy w pozycjach 7 i 8, nie zmieniając pozycji pozostałych siedmiu elementów.
...and return as output a sequence of moves representing the moves you must take to return the board back to its originalCzy to oznacza „powrót do1 2 3\n4 5 6\n7 8 9”? Nie jestem pewien, jak to przeczytać.