W niektórych starych telefonach Nokia istniała odmiana piętnastu układanek o nazwie Rotation. W tej odmianie zamiast przesuwać jedną płytkę na raz, obróciłeś cztery płytki na raz w jednym kierunku.

W tej grze zaczynasz od takiej planszy:

4 9 2
3 5 7
8 1 6

A obracając lewy dolny blok dwa razy w prawo i lewy górny blok raz w prawo, uzyskasz:

4 9 2
8 3 7
1 5 6

4 9 2
1 8 7
3 5 6

1 4 2
8 9 7
3 5 6

a 1płytka będzie w lewym górnym rogu, gdzie powinna być. W końcu po kilku kolejnych ruchach uzyskasz:

1 2 3
4 5 6
7 8 9

która jest „oryginalną” konfiguracją.

Twoim zadaniem jest zbudowanie programu, który pobierze jako dane wejściowe siatkę 3x3 liczb od 1 do 9 (w dowolnym wybranym przez Ciebie formacie) i zwróci jako wynik sekwencję ruchów reprezentujących ruchy, które musisz wykonać, aby przywrócić planszę do pierwotnego stanu konfiguracja (ponownie, w dowolnym wybranym formacie). Legalne ruchy są zdefiniowane jako przesunięcie bloku [góra / dół] - [lewo / prawo] z 4 płytek [zgodnie z ruchem wskazówek zegara / przeciwnie do ruchu wskazówek zegara].

Twój program musi być w stanie rozwiązać wszystkie możliwe siatki 3x3 (wszystkie kombinacje są rozwiązywalne).

Najkrótszy kod do tego celu wygrywa.

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:

1. Jeśli liczba 1 znajduje się w lewym górnym rogu, nie obraca już lewego górnego kwadratu.

2. Jeśli liczba 9 znajduje się w prawym dolnym rogu, nie obraca już prawego dolnego kwadratu.

3. 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.

Python z Numpy - 158

from numpy import*
A=input()
while any(A.flat>range(1,10)):i,j,k=random.randint(0,2,3);A[i:i+2,j:j+2]=rot90(A[i:i+2,j:j+2],1+2*k);print"tb"[i]+"lr"[j]+"wc"[k]

Dane wejściowe muszą mieć następujący format:

array([[1,2,5],[4,3,6],[7,8,9]])

Każda linia wyjściowa jest ruchem kodowanym w ciągach takich jak trwlub blci należy ją czytać w następujący sposób:

• t: Top
• b: Dolny
• l: lewo
• r: dobrze
• c: zgodnie z ruchem wskazówek zegara
• w: przeciwnie do ruchu wskazówek zegara (widdershins)

Ten program wykonuje losowe ruchy, aż do osiągnięcia docelowej konfiguracji. Przy przybliżonym założeniu, że każdy ruch ma niezależne prawdopodobieństwo 1/9! aby trafić w konfigurację docelową¹, liczba obrotów przed rozwiązaniem rozkłada się wykładniczo ze średnią (tj. średnią liczbą ruchów) 9! ≈ 3,6 · 10⁵. Jest to zgodne z krótkim eksperymentem (20 przebiegów).

^{¹ 9! będący całkowitą liczbą konfiguracji.}

C ++ najmniej ruchów rozwiązanie - najpierw szerokość (1847 znaków)

Po dłuższej refleksji myślę, że zrobiłem to znacznie wydajniej i rozsądniej. To rozwiązanie, choć z pewnością nie wygrywa w golfa, jest jak dotąd jedynym, które spróbuje znaleźć najmniejszą liczbę obrotów, które rozwiążą planszę. Jak dotąd rozwiązuje każdą losową planszę, którą rzuciłem na nią w dziewięciu lub mniej ruchach. Działa również znacznie lepiej niż mój ostatni i, mam nadzieję, odpowiada na poniższe uwagi Dennisa.

W porównaniu z poprzednim rozwiązaniem największą zmianą było przeniesienie kluczowej historii ze stanu tablicy (BS) do nowej klasy, która przechowuje historię na określonej głębokości (DKH). Za każdym razem, gdy aplikacja wykonuje ruch, sprawdza historię na tej głębokości i wszystkich głębokościach, aby sprawdzić, czy kiedykolwiek została oceniona, jeśli tak, to nie zostanie ponownie dodana do kolejki. Wydaje się, że znacznie zmniejsza to miejsce w kolejce (poprzez usunięcie całej tej historii z samego stanu płyty), a zatem zmniejsza prawie całe głupie przycinanie, które musiałem zrobić, aby zabrakło pamięci. Dodatkowo działa znacznie szybciej, ponieważ do kolejki jest znacznie mniej kopii.

Teraz jest to proste, szerokie pierwsze wyszukiwanie w różnych stanach planszy. Ponadto, jak się okazuje, chcę zmienić zestaw kluczy (obecnie przechowywany jako zestaw liczb w bazie-9, z których każdy jest obliczany przez BS :: key jako reprezentacja tablicy w bazie-9) na zestaw bitów mając 9! bity wydają się niepotrzebne; chociaż dowiedziałem się, jak obliczyć klucz w „systemie liczb silnych”, który mógł zostać wykorzystany do obliczenia bitu w zestawie bitów w celu przetestowania / przełączenia.

Tak więc najnowszym rozwiązaniem jest:

#include <iostream>
#include <list>
#include <set>
#include <vector>
using namespace std;
struct BS{
#define LPB(i) for(int*i=b;i-b<9;i++)
struct ROP{int t, d;};
typedef vector<ROP> SV;
typedef unsigned int KEY;
typedef set<KEY> KH;
BS(const int*d){const int*x=d;int*y=b;for(;x-d<9;x++,y++)*y=*x;}
BS(){LPB(i)*i=i-b+1;}
bool solved(){LPB(i)if(i-b+1!=*i)return 0;return 1;}
void rot(int t, int d){return rot((ROP){t,d});}
void rot(ROP r){rotb(r);s.push_back(r);}
bool undo(){if (s.empty())return false;ROP &u=s.back();u.d*=-1;rotb(u);s.pop_back();return true;}
SV &sol(){return s;}
KEY key(){KEY rv=0;LPB(i){rv*=9;rv+=*i-1;}return rv;}
int b[9];
SV s;
void rotb(ROP r){int c=r.t<2?r.t:r.t+1;int bi=(r.d>0?3:4)+c;const int*ri=r.d>0?(const int[]){0,1,4}:(const int[]){1,0,3};for(int i=0;i<3;i++)swap(b[bi],b[c+ri[i]]);}
};
ostream &operator<<(ostream &o, BS::ROP r){static const char *s[]={"tl","tr","bl","br"};o<<s[r.t]<<(r.d<0?"w":"c");return o;}
struct DKH{
~DKH(){for(HV::iterator i=h.begin();i<h.end();++i)if(*i!=NULL)delete *i;}
void add(int d,BS b){h.resize(d+1);if(h[d]==NULL)h[d]=new BS::KH();h[d]->insert(b.key());}
bool exists(BS &b){BS::KEY k=b.key();size_t d=min(b.sol().size(),h.size()-1);do if (h[d]->find(k)!=h[d]->end())return true;while(d--!=0);return false;}
typedef vector<BS::KH *> HV;HV h;
};
static bool solve(BS &b)
{
const BS::ROP v[8]={{0,-1},{0,1},{1,-1},{1,1},{2,-1},{2,1},{3,-1},{3,1}};
DKH h;h.add(0,b);
list<BS> q;q.push_back(b);
while (!q.empty())
{
BS qb=q.front();q.pop_front();
if (qb.solved()){b=qb;return true;}
int d=qb.sol().size()+1;
for (int m=0;m<8;++m){qb.rot(v[m]);if (!h.exists(qb)){h.add(d,qb);q.push_back(qb);}qb.undo();}
}
return false;
}
int main()
{
BS b((const int[]){4,9,2,3,5,7,8,1,6});
if (solve(b)){BS::SV s=b.sol();for(BS::SV::iterator i=s.begin();i!=s.end();++i)cout<<*i<<" ";cout<<endl;}
}

CJam - 39

l{4mr_o_1>+_@m<_[Z0Y4X]\f=\5>+m>__$>}g;

Kolejny losowy solver :)
Pobiera ciąg taki jak 492357816 i wyświetla (długą) serię cyfr od 0 do 3, z których każda reprezentuje obrót bloku zgodnie z ruchem wskazówek zegara: 0 = lewy górny, 1 = prawy górny, 2 = dolny -lewa, 3 = prawy dolny róg.

Krótkie wyjaśnienie:

4mrgeneruje liczbę losową od 0 do 3
_1>+przyrostów, jeśli jest większa niż 1 (więc kończymy na 0, 1, 3 lub 4 - indeksy początkowe 4 bloków)
m<obraca ciąg w lewo (np. 492357816 -> 923578164, a nie obrót bloku), aby obrócić blok w pierwszej pozycji,
[Z0Y4X]\f=wykonuje obrót bloku, który wpływa na pierwsze 5 znaków, na przykład 12345 -> 41352;
X = 1, Y = 2, Z = 3, więc [Z0Y4X] to w rzeczywistości [3 0 2 4 1], a są to indeksy 0 obracanych płytek
5>kopiuje, reszta łańcucha
m>obraca (zmodyfikowany) ciąg z powrotem do prawo
__$>sprawdza, czy łańcuch jest posortowany (jest to warunek zatrzymania)

Mathematica, 104 znaki

Możemy interpretować to zadanie w języku grup permutacyjnych. Cztery obroty to tylko cztery permutacje, które generują symetryczną grupę S ₉ , a zadaniem jest po prostu napisanie permutacji jako iloczynu generatorów. Mathematica ma do tego wbudowaną funkcję.

i={1,2,5,4};GroupElementToWord[PermutationGroup[Cycles/@({i}+#&/@i-1)],Input[]~FindPermutation~Range@9]

Przykład:

Wejście:

{4, 9, 2, 8, 3, 7, 1, 5, 6}

Wynik:

{-2, -3, -4, 2, 4, 1, 4, -1, -2, 3, 2, -4, 3, 4, -3, -3, -4, -4, -2, -2, -3, -2, 3, -1}

• 1: w lewym górnym rogu zgodnie z ruchem wskazówek zegara
• 2: w prawym górnym rogu zgodnie z ruchem wskazówek zegara
• 3: w prawym dolnym rogu zgodnie z ruchem wskazówek zegara
• 4: u dołu po lewej zgodnie z ruchem wskazówek zegara
• -1: w lewym górnym rogu przeciwnie do ruchu wskazówek zegara
• -2: w prawym górnym rogu przeciwnie do ruchu wskazówek zegara
• -3: u dołu po prawej przeciwnie do ruchu wskazówek zegara
• -4: u dołu po lewej przeciwnie do ruchu wskazówek zegara