Array dua dimensi dengan ukuran n × n diisi dengan angka n * n, mulai dari angka 1. Angka-angka itu harus diurutkan per baris dalam urutan menaik; angka pertama dari suatu baris harus lebih besar dari jumlah terakhir dari baris sebelumnya (jumlah terkecil dari semua (1) adalah [0,0]). Ini mirip dengan 15 puzzle .

Ini, misalnya, array ukuran diurutkan n = 3 .

1 2 3
4 5 6
7 8 9

Memasukkan

Input adalah array yang diacak. Ukurannya bisa berapa saja hingga n = 10. Contoh untuk n = 3:

4 2 3
1 8 5
7 9 6

Keluaran

Keluarkan daftar swap yang diperlukan untuk mengurutkan array. Suatu swap didefinisikan sebagai berikut: Dua posisi angka yang berdekatan menukar posisi, baik secara horizontal maupun vertikal; swapping diagonal tidak diizinkan.

Contoh output untuk contoh di atas:

Tukar 4 dan 1
Tukar 8 dan 5
Tukar 8 dan 6
Tukar 9 dan 8

Semakin sedikit swap yang dibutuhkan, semakin baik. Waktu perhitungan harus layak.

Berikut ini contoh input lain, dengan n = 10:

41 88 35 34 76 44 66 36 58 28
6 71 24 89 1 49 9 14 74 2
80 31 95 62 81 63 5 40 29 39
17 86 47 59 67 18 42 61 53 100
73 30 43 12 99 51 54 68 98 85
13 46 57 96 70 20 82 97 22 8
10 69 50 65 83 32 93 45 78 92
56 16 27 55 84 15 38 19 75 72
33 11 94 48 4 79 87 90 25 37
77 26 3 52 60 64 91 21 23 7

Jika saya tidak salah, ini akan membutuhkan sekitar 1000-2000 swap.

code-challenge array-manipulation sorting JCarter
sumber

Apakah ini masalah puzzle, kecepatan, atau golf?

Michael Klein

@MichaelKlein Ini adalah teka-teki.

JCarter

Apakah sudah dicetak? Rentang apa yang perlu ditangani?

Michael Klein

@steveverrill Saya khawatir sangat tidak mungkin untuk menyelesaikan contoh n = 10 dalam waktu kurang dari 100 swap (atau bahkan 1000; tapi tolong buktikan saya salah). Namun, jumlah swap adalah kriteria yang menang (meskipun perhitungan harus layak!), Orang yang menemukan solusi dengan jumlah swap yang paling rendah menang.

JCarter

@JCarter Saya pikir Anda bermaksud mengatakan bahwa hanya nomor yang berdekatan yang dapat ditukar?

kuintopia

Mathematica, bukan golf

towards[a_,b_]:={a,a+If[#==0,{0,Sign@Last[b-a]},{#,0}]&@Sign@First[b-a]};
f[m_]:=Block[{m2=Map[QuotientRemainder[#-1,10]+1&,m,{2}]},
  Rule@@@Apply[10(#1-1)+#2&,#,{2}]&@
    Reap[Table[
      m2=NestWhile[
        Function[{x},x/.(Sow[#];Thread[#->Reverse@#])&[x[[##]]&@@@towards[First@Position[x,i,{2}],i]]]
        ,m2,#~Extract~i!=i&];
      ,{i,Reverse/@Tuples[Range[10],2]}];][[2,1]]]

Penjelasan :

Algoritma ini mirip dengan "bubble sort". 100 nomor ini dimasukkan ke dalam urutan yang benar satu per satu 1, 11, 21, ..., 91; 2, ..., 92; ...; 10, ..., 100,. Pertama-tama mereka bergerak naik / turun ke baris yang benar, dan kemudian pindah ke kiri ke kolom yang benar.

Fungsi towardsmemberi dua posisi untuk bertukar. Misalnya, jika {5,2}pindah ke {1,1}, towards[{5,2},{1,1}]beri {{5,2},{5,1}}(naik); dan towards[{5,1},{1,1}]memberi {{5,1},{4,1}}(bergerak ke kiri).

Hasil :

Untuk kasus uji, jumlah total swap adalah 558. Beberapa swap pertama adalah,

{1->76,1->34,1->35,1->88,1->41,11->16,11->69,11->46, ...

Untuk konfigurasi acak, jumlah total swap adalah 558,5 ± 28,3 (1σ).

njpipeorgan
sumber

Urutkan array dua dimensi yang diacak diisi dengan angka dengan menukar angka yang berdekatan [ditutup]

Memasukkan

Keluaran

Jawaban:

Mathematica, bukan golf