Gagasan untuk tantangan kode ini sederhana: diberi matriks bilangan bulat, mari kita urutkan dengan menerapkan gerakan gaya Rubik. Ini berarti Anda dapat memilih satu baris atau kolom dan memutar elemen-elemennya ke segala arah:
[1, 3, 2, 4] => [3, 2, 4, 1] (rotate left for rows/up for columns)
[1, 3, 2, 4] => [4, 1, 3, 2] (rotate right for rows/down for columns)
Jadi, mengingat matriks bilangan bulat dari dimensi apa pun, sortir elemen-elemennya hanya dengan menerapkan transformasi gaya Rubik ini. Sebuah matriks
akan dianggap diurutkan jika elemen-elemennya mematuhi batasan berikut:
I / O
- Input akan menjadi matriks bilangan bulat positif tanpa nilai berulang.
- Output akan menjadi gerakan yang diperlukan untuk mengurutkannya. Karena ini bukan tantangan kode golf dan Anda tidak perlu khawatir tentang panjangnya, format yang diusulkan untuk setiap gerakan adalah di
#[UDLR]
mana#
jumlah baris atau kolom yang akan dipindahkan (diindeks 0) dan[UDLR]
merupakan karakter tunggal di dalamnya. rentang yang menentukan jika gerakan ke Atas / Bawah (untuk kolom) atau Kiri / Kanan (untuk baris). Jadi1U
akan berarti "pindahkan kolom ke-1 ke atas" tetapi1R
akan "memindahkan baris ke-1 ke kanan". Gerakan akan dipisahkan koma, sehingga solusi akan dinyatakan seperti ini:1R,1U,0L,2D
.
Mencetak gol
Mencoba mengurutkan matriks dengan cara ini bisa mahal karena ada banyak kemungkinan kombinasi gerakan, dan ada juga banyak kemungkinan daftar langkah yang dapat mengurutkannya, jadi tujuannya adalah untuk menulis beberapa kode yang mengurutkan N * N matriks di bawah ini. Skor akan menjadi ukuran terbesar N yang dapat Anda pecahkan dalam jumlah waktu yang wajar 1 tanpa kesalahan (semakin besar ukuran matriks dipecahkan, semakin baik). Dalam kasus seri, tie-breaker akan menjadi jumlah gerakan di jalur yang Anda temukan (semakin pendek jalurnya, semakin baik).
Contoh: jika pengguna A menemukan solusi untuk N = 5 dan B menemukan solusi untuk N = 6, B menang terlepas dari panjang kedua jalur. Jika mereka berdua menemukan solusi untuk N = 6 tetapi solusi yang ditemukan oleh A memiliki 50 langkah dan solusi B memiliki 60 langkah, A menang.
Penjelasan tentang cara kerja kode Anda sangat dianjurkan dan kirimkan solusi yang ditemukan sehingga kami dapat mengujinya . Anda dapat menggunakan Pastebin atau alat serupa jika solusinya terlalu besar. Juga, perkiraan waktu yang dihabiskan oleh kode Anda untuk menemukan solusi Anda akan dihargai.
Uji kasus
Matriks berikut ( tautan Pastebin untuk versi yang lebih dapat di-paste) telah dibuat mulai dari matriks yang sudah diurutkan dengan mengacaknya dengan gerakan acak 10K gaya Rubik:
Plaintext Test Cases:
[[8, 5, 6], [11, 10, 1], [3, 15, 13]]
[[21, 10, 12, 16], [17, 6, 22, 14], [8, 5, 19, 26], [13, 24, 3, 1]]
[[1, 13, 8, 16, 5], [9, 40, 21, 26, 22], [11, 24, 14, 39, 28], [32, 19, 37, 3, 10], [30, 17, 36, 7, 34]]
[[34, 21, 40, 22, 35, 41], [18, 33, 31, 30, 12, 43], [19, 11, 39, 24, 28, 23], [44, 1, 36, 5, 38, 45], [14, 17, 9, 16, 13, 26], [8, 3, 47, 6, 25, 4]]
[[20, 36, 17, 1, 15, 50, 18], [72, 67, 34, 10, 32, 3, 55], [42, 43, 9, 6, 30, 61, 39], [28, 41, 54, 27, 23, 5, 70], [48, 13, 25, 12, 46, 58, 63], [52, 37, 8, 45, 33, 14, 68], [59, 65, 56, 73, 60, 64, 22]]
[[85, 56, 52, 75, 89, 44, 41, 68], [27, 15, 87, 91, 32, 37, 39, 73], [6, 7, 64, 19, 99, 78, 46, 16], [42, 21, 63, 100, 4, 1, 72, 13], [11, 97, 30, 93, 28, 40, 3, 36], [50, 70, 25, 80, 58, 9, 60, 84], [54, 96, 17, 29, 43, 34, 23, 35], [77, 61, 82, 48, 2, 94, 38, 66]]
[[56, 79, 90, 61, 71, 122, 110, 31, 55], [11, 44, 28, 4, 85, 1, 30, 6, 18], [84, 43, 38, 66, 113, 24, 96, 20, 102], [75, 68, 5, 88, 80, 98, 35, 100, 77], [13, 21, 64, 108, 10, 60, 114, 40, 23], [47, 2, 73, 106, 82, 32, 120, 26, 36], [53, 93, 69, 104, 54, 19, 111, 117, 62], [17, 27, 8, 87, 33, 49, 15, 58, 116], [95, 112, 57, 118, 91, 51, 42, 65, 45]]
Please ask for more if you solve them all. :-) And many thanks to the people who helped me refine this challenge while in the sandbox.
1 Jumlah waktu yang masuk akal: jumlah waktu yang tidak merusak kesabaran kami saat menguji solusi Anda. Perhatikan bahwa TIO hanya menjalankan kode selama 60 detik, jumlah waktu apa pun yang melebihi batas itu akan membuat kami menguji kode di mesin kami. Contoh: algoritma saya yang agak tidak efisien membutuhkan beberapa milidetik untuk menyelesaikan matriks pesanan 3x3 dan 4x4, tetapi saya baru saja mengujinya dengan matriks 5x5 dan butuh 317 detik untuk menyelesaikannya (dalam lebih dari 5 juta gerakan, sangat lucu jika kita menganggap itu matriks untuk dipecahkan hanya diacak 10K kali). Saya mencoba mengurangi jumlah gerakan menjadi kurang dari 10 ribu tetapi saya menyerah setelah 30 menit mengeksekusi kode.
O(input size)
? Untuk matriks 5x5 yaO(25)
? Itu tampaknya sangat cepat, jadi saya akan sangat tertarik untuk melihat algoritma atau implementasi Anda itu. EDIT: Anda sadar bahwa kita memasukkan matriks 'scrambled' dan mengeluarkan gerakan, kan? Bukan sebaliknya.Jawaban:
Nim
Cobalah online!
Upaya cepat untuk mengimplementasikan algoritma solusi teka-teki Torus dari sebuah artikel yang diterbitkan dalam Algoritma 2012, 5, 18-29 yang saya sebutkan di komentar.
Menerima matriks input dalam bentuk datar, sebagai garis angka yang dibatasi ruang.
Di sini juga adalah validator di Python 2 . Dibutuhkan dua baris sebagai input: matriks orak asli dalam bentuk yang sama dengan kode utama, dan urutan gerakan yang diusulkan. Output dari validator adalah matriks yang dihasilkan dari penerapan gerakan ini.
Penjelasan
Di bagian pertama algoritma, kami memesan semua baris kecuali yang terakhir.
Kami melakukan ini dengan melakukan serangkaian "rotasi segitiga" ([ p , q] , lalu cari selnya [ s , t ] yang saat ini berisi nomor yang harus dituju [ p , q] , dan lengkapi segitiga siku-siku dengan memilih titik ketiga [ u , v ] menurut beberapa pola, seperti yang ditunjukkan pada Gambar. 4 dari artikel yang ditautkan.
proc triangle
) - urutan gerakan yang menghasilkan hanya tiga tempat bertukar tempat, dan semua sisanya tetap tidak berubah. Kami mengambil setiap sel "bekerja" berturut-turut dengan koordinatPada Gambar. 2, penulis menyajikan 8 pola yang mungkin dan urutan bergerak yang sesuai, tetapi dalam kode saya semua kasus sebenarnya telah ditutupi oleh hanya 5 pola, sehingga tidak ada. 1, 5, dan 6 tidak digunakan.
Pada bagian kedua, baris terakhir kecuali dua elemen terakhir diperintahkan dengan melakukan "tiga elemen rotasi" pada garis (
proc line
), yang masing-masing terdiri dari dua rotasi segitiga (lihat Gambar 3 artikel).Kami memilih sel kerja kami saat ini[ p , q] sebagai titik kiri, sel berisi nilai target [ s , t ] sebagai titik pusat, dan [ s , t + 1 ] sebagai titik yang tepat. Gerakan ke barat ini dinamaiTW dalam artikel, dan begitu juga proc membentuk string saya untuk ini. Jikat sudah menjadi kolom terakhir, jadi t + 1 tidak ada, kami ambil [ s , t - 1 ] sebagai titik ketiga, dan memodifikasi tindakan sesuai: dua rotasi segitiga dilakukan oleh pola 7 dan 8 (bukan 7 dan 1 dalam aslinya TW urutan).
Akhirnya, jikan aneh, sisa dua elemen harus sudah ada, karena kami dijamin ada solusinya. Jikan bahkan, dan dua elemen yang tersisa tidak pada tempatnya, maka menurut Lemma 1 (halaman 22), mereka dapat ditukar dengan serangkaian TW bergerak, diikuti oleh satu shift ke timur (= R ). Karena contoh yang diberikan menukar dua entri pertama, dan kita perlu menukar dua entri terakhir, TW bergerak dalam urutan terbalik.
proc swap
kinerja kitaDi tepi kasusn = 2 kita tidak memerlukan semua prosedur rumit ini sama sekali - jika elemen baris terakhir tidak ada setelah bagian 1, satu 1 R Langkah ini cukup untuk membuat matriks terurut sepenuhnya.
Pembaruan: Menambahkan baru
proc rotations
yang membalikkan arah gerakan jika itu akan menghasilkan langkah yang lebih sedikit.sumber
7L,7L,7L,7L,7D,7D,7D,7D
dapat dikurangi dan8R,8R,8R,8R,8R,8R,8R
daripada dapat dikonversi ke8L,8L
untuk matriks 9x9.Python 2 , ukuran 100 dalam <30 detik pada TIO
Cobalah online! Tautan mencakup tiga kotak uji kecil dengan output gerakan penuh, ditambah uji diam 100x100 untuk menunjukkan bahwa kode berfungsi (output gerakan akan melebihi batas TIO). Penjelasan: Kode mencoba untuk melakukan semacam penyisipan pada array, membangunnya dalam urutan menaik saat berjalan. Untuk semua baris kecuali baris terakhir, ada sejumlah kasus:
Rotasi di atas dilakukan ke arah mana pun meminimalkan jumlah langkah; ukuran 2 persegi selalu diselesaikan dengan menggunakan gerakan kiri dan atas, terlepas dari deskripsi di atas.
Sebelum baris bawah selesai, itu diputar untuk meminimalkan jarak total keluar dari tempatnya, tetapi juga untuk memastikan bahwa paritas baris bawah bahkan, karena tidak dapat diubah oleh bagian akhir dari algoritma. Jika ada lebih dari satu rotasi dengan jarak minimal yang sama, rotasi dengan jumlah gerakan terkecil akan dipilih.
Algoritma untuk baris bawah bergantung pada urutan 7-operasi yang bertukar elemen dalam tiga kolom. Urutan diterapkan ke masing-masing nomor yang tersisa dari baris bawah secara bergantian untuk membawanya ke lokasi yang diinginkan; jika memungkinkan elemen di lokasi tersebut dipindahkan ke lokasi yang diinginkan, tetapi jika diperlukan pertukaran langsung, elemen tersebut hanya dipindahkan ke kolom terdekat yang tersedia, semoga memungkinkan untuk diperbaiki di waktu berikutnya.
sumber