Pada beberapa ponsel Nokia lama, ada variasi dari lima belas teka - teki yang disebut Rotasi. Dalam variasi ini, alih-alih menggeser satu ubin sekaligus, Anda memutar empat ubin sekaligus dalam satu arah.

Dalam permainan ini, Anda akan mulai dengan papan seperti ini:

4 9 2
3 5 7
8 1 6

Dan dengan memutar blok kiri bawah dua kali searah jarum jam dan kiri atas, searah jarum jam, Anda akan mendapatkan ini:

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

dan 1ubin akan berada di sudut kiri atas di mana seharusnya. Akhirnya, setelah beberapa langkah lagi, Anda akan berakhir dengan:

1 2 3
4 5 6
7 8 9

yang merupakan konfigurasi "asli".

Tugas Anda adalah membuat program yang akan memasukkan 3x3 kisi angka mulai dari 1 hingga 9 (dalam format apa pun yang Anda pilih) dan kembali sebagai keluaran dengan urutan gerakan yang mewakili langkah yang harus Anda ambil untuk mengembalikan papan ke aslinya. konfigurasi (sekali lagi, dalam format apa pun yang Anda pilih). Pergerakan hukum didefinisikan sebagai memindahkan blok [atas / bawah] - [kiri / kanan] dengan 4 ubin [searah / berlawanan arah jarum jam].

Program Anda harus dapat menyelesaikan semua kisi 3x3 yang mungkin (semua permutasi dapat dipecahkan).

Kode terpendek untuk melakukan ini akan menang.

GolfScript, 39/83 byte

# 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`*

Kecepatan vs ukuran

Versi ukuran-dioptimalkan secara acak memilih rotasi searah jarum jam sampai permutasi yang diinginkan tercapai. Ini cukup, karena rotasi berlawanan arah jarum jam setara dengan tiga rotasi searah jarum jam berturut-turut dari bujur sangkar yang sama.

Versi yang dioptimalkan kecepatan melakukan hal yang sama, kecuali untuk yang berikut:

1. Jika angka 1 di sudut kiri atas, itu tidak memutar persegi kiri atas lagi.

2. Jika angka 9 ada di sudut kanan bawah, itu tidak memutar kotak kanan bawah lagi.

3. Langkah-langkah untuk bertukar posisi 7 dan 8 adalah hardcode, sehingga ada dua posisi yang memungkinkan loop untuk istirahat.

Selain mengubah algoritme, versi yang dioptimalkan kecepatan juga mencapai rotasi secara langsung, sedangkan versi yang dioptimalkan ukuran menggunakan sortir bawaan GolfScript dengan memetakan. Itu juga hardcodes keadaan akhir (untuk perbandingan) alih-alih menyortir negara di setiap iterasi.

Versi yang dioptimalkan kecepatan membutuhkan lebih sedikit iterasi dan setiap iterasi jauh lebih cepat dengan sendirinya.

Tolak ukur

Saya telah menggunakan kode berikut untuk mengacak posisi angka-angka dan melakukan uji coba, menghapus tanda komentar pada baris yang sesuai dengan versi yang akan diuji:

[{[
    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: '\+

Output menunjukkan jumlah langkah minimum dan maksimum yang diperlukan untuk memesan angka, rata-rata, dan median semua proses, serta waktu yang berlalu dalam hitungan detik:

$ 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

Di komputer saya (Intel Core i7-3770), waktu eksekusi rata-rata versi yang dioptimalkan adalah 3,58 menit. Waktu eksekusi rata-rata dari versi yang dioptimalkan kecepatan adalah 0,20 detik. Dengan demikian, versi yang dioptimalkan kecepatan sekitar 1075 kali lebih cepat.

Versi yang dioptimalkan kecepatan menghasilkan rotasi 114 kali lebih sedikit. Melakukan setiap rotasi adalah 9,4 kali lebih lambat, yang terutama disebabkan oleh bagaimana negara diperbarui.

I / O

Output terdiri dari angka 3-bit. MSB diatur untuk rotasi berlawanan arah jarum jam, bit tengah ditetapkan untuk kotak yang lebih rendah dan LSB diatur untuk kotak kanan. Jadi, 0 (4) adalah kuadrat kiri atas, 1 (5) yang kanan atas, 2 (6) kiri bawah dan 3 (7) yang kanan bawah.

Versi yang dioptimalkan kecepatan mencetak semua rotasi dalam satu baris. Versi ukuran-dioptimalkan mencetak satu rotasi per baris, diikuti oleh posisi akhir angka.

Untuk versi yang dioptimalkan kecepatan, input harus menghasilkan array yang berisi angka dari 1 hingga 9 ketika dievaluasi. Untuk versi yang dioptimalkan ukuran, input harus berupa string tanpa baris akhir akhir; itu tidak dievaluasi.

Contoh berjalan:

$ echo -n '253169748' | golfscript rotation-size.gs
3
0
123456789
$ golfscript rotation-speed.gs <<< '[5 4 7 1 2 9 3 8 6]'
2210300121312212222212211121122211122221211111122211211222112230764

Kode yang dioptimalkan ukuran

{               #
  .             # 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.

Memperbarui status dicapai dengan cara berikut:

Rotasi 2 menghasilkan bilangan bulat 3 setelah menambahkan 1. Jika negara adalah "123456789", mengiris negara menghasilkan "456789".

Tepat sebelum menjalankan "$", elemen paling atas dari tumpukan adalah:

[ 1 2 3 4 5 6 7 8 9 ] { [ 4 5 6 7 8 9 ] ? "1420344440" = }

"$" Mengeksekusi blok sekali untuk setiap elemen array yang akan diurutkan, setelah mendorong elemen itu sendiri.

Indeks 1 dalam “[4 5 6 7 8 9]” adalah -1 (tidak ada), jadi elemen terakhir dari "1420344440" didorong. Ini menghasilkan 48, kode ASCII yang sesuai dengan karakter 0. Untuk 2 dan 3, 48 juga didorong.

Bilangan bulat yang didorong untuk 4, 5, 6, 7, 8 dan 9 adalah 49, 52, 50, 48, 51, dan 52.

Setelah disortir, elemen pertama dari negara akan menjadi salah satu elemen yang menghasilkan 48; yang terakhir akan menjadi salah satu yang menghasilkan 52. Jenis bawaan pada umumnya tidak stabil, tetapi saya telah memverifikasi secara empiris bahwa itu stabil dalam kasus khusus ini.

Hasilnya adalah "[1 2 3 7 4 6 8 5 9]", yang sesuai dengan rotasi searah jarum jam dari alun-alun kiri bawah.

Kode yang dioptimalkan kecepatan

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

Perhatikan bahwa rotasi 3, 0, 7, 6 dan 4 menukar elemen di posisi 7 dan 8, tanpa mengubah posisi tujuh elemen yang tersisa.

Python dengan 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]

Input harus dengan format berikut:

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

Setiap baris output adalah langkah yang dikodekan dalam string seperti trwatau blcdan dibaca sebagai berikut:

• t: atas
• b: bawah
• l: kiri
• r: Baik
• c: searah jarum jam
• w: berlawanan arah jarum jam (widdershins)

Program ini melakukan gerakan acak hingga konfigurasi target tercapai. Di bawah asumsi perkiraan bahwa setiap gerakan memiliki probabilitas independen 1/9! untuk mencapai konfigurasi target¹, jumlah rotasi sebelum solusi didistribusikan secara eksponensial dengan rata-rata (yaitu jumlah rata-rata gerakan) dari 9! ≈ 3.6 · 10⁵. Ini sesuai dengan percobaan singkat (20 kali jalan).

^{¹ 9! menjadi jumlah total konfigurasi.}

Solusi C ++ paling sedikit bergerak - luasnya pertama (1847 karakter.)

Setelah sedikit berpikir, saya pikir saya telah melakukan ini jauh lebih efisien dan lebih masuk akal. Solusi ini, walaupun tentu saja tidak memenangkan golf ini, sejauh ini adalah satu-satunya yang akan berusaha untuk menemukan jumlah putaran terpendek yang akan memecahkan papan. Sejauh ini, ini memecahkan setiap papan acak yang saya lemparkan dalam sembilan gerakan atau lebih sedikit. Ini juga berkinerja lebih baik daripada yang terakhir saya dan, semoga, menanggapi komentar Dennis di bawah ini.

Dari solusi sebelumnya, perubahan terbesar adalah memindahkan sejarah kunci dari board state (BS) ke kelas baru yang menyimpan sejarah pada kedalaman tertentu (DKH). Kapan saja aplikasi bergerak, ia memeriksa sejarah pada kedalaman itu dan semua kedalaman sebelum melihat apakah itu pernah dievaluasi, jika demikian, itu tidak akan ditambahkan ke antrian lagi. Ini tampaknya secara signifikan mengurangi penyimpanan pada antrian (dengan menghapus semua riwayat ini dari status board itu sendiri) dan karena itu mengurangi hampir semua pemangkasan bodoh yang harus saya lakukan untuk menjaga kode agar tidak kehabisan memori. Plus itu berjalan jauh lebih cepat karena ada jauh lebih sedikit untuk menyalin ke antrian.

Sekarang, ini adalah pencarian pertama yang luas dan sederhana di berbagai negara bagian. Plus, ternyata, saya ingin mengubah set kunci (saat ini disimpan sebagai set angka dalam basis-9, yang masing-masing dihitung oleh BS :: key sebagai basis-9 representasi papan) ke bitset memiliki 9! bit tampaknya tidak perlu; meskipun saya menemukan bagaimana menghitung kunci dalam "sistem bilangan faktorial" yang bisa digunakan untuk menghitung bit dalam bitset untuk menguji / beralih.

Jadi, solusi terbaru adalah:

#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;

Pemecah acak lain :)
Dibutuhkan string seperti 492357816 dan menghasilkan serangkaian (panjang) digit dari 0 hingga 3, masing-masing mewakili rotasi searah jarum jam: 0 = kiri atas, 1 = kanan atas, 2 = bawah -kiri, 3 = kanan bawah.

Penjelasan singkat:

4mrmenghasilkan angka acak dari 0 hingga 3
_1>+menambah angka jika lebih besar dari 1 (jadi kita berakhir dengan 0, 1, 3 atau 4 - indeks awal dari 4 blok)
m<memutar string ke kiri (seperti 492357816 -> 923578164, bukan rotasi blok) untuk membawa blok berotasi pada posisi pertama
[Z0Y4X]\f=melakukan rotasi blok yang mempengaruhi 5 karakter pertama, seperti 12345 -> 41352;
X = 1, Y = 2, Z = 3 jadi [Z0Y4X] sebenarnya [3 0 2 4 1] dan itu adalah indeks berbasis 0 dari ubin yang diputar
5>menyalin sisa string
m>memutar (dimodifikasi) string kembali ke hak
__$>memeriksa apakah string diurutkan (ini adalah kondisi berhenti)

Mathematica, 104 karakter

Kita bisa menafsirkan tugas dalam bahasa kelompok permutasi. Keempat rotasi hanyalah empat permutasi yang menghasilkan grup simetris S ₉ , dan tugasnya hanyalah menulis permutasi sebagai produk dari generator. Mathematica memiliki fungsi bawaan untuk melakukan ini.

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

Contoh:

Memasukkan:

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

Keluaran:

{-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: kiri atas searah jarum jam
• 2: searah jarum jam kanan atas
• 3: searah jarum jam bawah kanan
• 4: kiri bawah searah jarum jam
• -1: kiri atas berlawanan arah jarum jam
• -2: kanan-atas berlawanan arah jarum jam
• -3: kanan bawah berlawanan arah jarum jam
• -4: kiri bawah berlawanan arah jarum jam