Rubik-sorting a matrix (alias puzzle torus)

16

Gagasan untuk 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

[Sebuah11Sebuah12Sebuah13Sebuah14Sebuah21Sebuah22Sebuah23Sebuah24Sebuah31Sebuah32Sebuah33Sebuah34]

akan dianggap diurutkan jika elemen-elemennya mematuhi batasan berikut:

Sebuah11Sebuah12Sebuah13Sebuah14Sebuah21Sebuah22Sebuah23Sebuah24Sebuah31Sebuah32Sebuah33Sebuah34

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). Jadi 1Uakan berarti "pindahkan kolom ke-1 ke atas" tetapi 1Rakan "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:

[8561110131513]
[211012161762214851926132431]
[11381659402126221124143928321937310301736734]
[34214022354118333130124319113924282344136538451417916132683476254]
[20361711550187267341032355424396306139284154272357048132512465863523784533146859655673606422]
[85565275894441682715879132373973676419997846164221631004172131197309328403365070258058960845496172943342335776182482943866]
[567990617112211031551144284851306188443386611324962010275685888098351007713216410810601144023472731068232120263653936910454191111176217278873349155811695112571189151426545]

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.

Charlie
sumber
1
Tantangan yang bagus! Namun, saya punya beberapa permintaan / pertanyaan: 1) Bisakah Anda memberikan kasus uji dalam format yang lebih ramah-rekat-rekat? (seperti pastebin) 2) Bisakah Anda memberikan definisi yang lebih tepat dari urutan batas waktu? 3) Apakah matriks dijamin persegi? (Kasus uji menyarankan demikian, tetapi definisi tidak.)
Arnauld
@Arnauld 1) I'm on it. 2) I didn't want to establish a time limit, and nobody suggested any limit while the challenge was in the sandbox. If you need one, would you consider 30 minutes a reasonable limit? 3) Yes, the test matrices are the ones shown, and they will all be square if more are needed.
Charlie
There exists an (relatively easy to implement) O(input size) algorithm to this challenge, so it's not as interesting as it may look at first.
user202729
@ user202729 Berapakah ukuran input pada Anda O(input size)? Untuk matriks 5x5 ya O(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.
Kevin Cruijssen
4
Saya pikir, ini seperti algoritma ini
Kirill L.

Jawaban:

8

Nim

import algorithm, math, sequtils, strutils

let l = split(stdin.readLine())
var m = map(l, parseInt)
let n = int(sqrt(float(len(m))))
let o = sorted(m, system.cmp[int])

proc rotations(P, Q: int): tuple[D, L, R, U: string, P, Q: int]=
  result = (D: "D", L: "L", R: "R", U: "U", P: P, Q: Q)
  if P > n - P:
    result.D = "U"
    result.U = "D"
    result.P = n - P
  if Q > n - Q:
    result.L = "R"
    result.R = "L"
    result.Q = n - Q

proc triangle(r: int): string=
  let p = r div n
  let q = r mod n
  let i = find(m, o[r])
  let s = i div n
  let t = i mod n
  var u = s
  var v = q
  if s == p and t == q:
    return ""
  var patt = 0
  if p == s: 
    u = s + 1
    patt = 4
  elif q == t:
    if q == n - 1:
      v = t - 1
      patt = 8
    else:
      u = p
      v = t + 1
      patt = 3
  elif t > q:
    patt = 2
  else:
    patt = 7
  var Q = abs(max([q, t, v]) - min([q, t, v]))
  var P = abs(max([p, s, u]) - min([p, s, u]))
  let x = p*n + q
  let y = s*n + t
  let z = u*n + v
  let w = m[x]
  m[x] = m[y]
  m[y] = m[z]
  m[z] = w
  let R = rotations(P, Q)

  result = case patt:
    of 2:
      repeat("$#$#," % [$v, R.D], R.P) & 
        repeat("$#$#," % [$u, R.L], R.Q) &
        repeat("$#$#," % [$v, R.U], R.P) & 
        repeat("$#$#," % [$u, R.R], R.Q)
    of 3:
      repeat("$#$#," % [$q, R.U], R.P) & 
        repeat("$#$#," % [$p, R.L], R.Q) &
        repeat("$#$#," % [$q, R.D], R.P) & 
        repeat("$#$#," % [$p, R.R], R.Q)
    of 4:
      repeat("$#$#," % [$p, R.L], R.Q) & 
        repeat("$#$#," % [$q, R.U], R.P) &
        repeat("$#$#," % [$p, R.R], R.Q) & 
        repeat("$#$#," % [$q, R.D], R.P)
    of 7:
      repeat("$#$#," % [$v, R.D], R.P) & 
        repeat("$#$#," % [$u, R.R], R.Q) &
        repeat("$#$#," % [$v, R.U], R.P) & 
        repeat("$#$#," % [$u, R.L], R.Q)
    of 8:
      repeat("$#$#," % [$s, R.R], R.Q) & 
        repeat("$#$#," % [$t, R.D], R.P) &
        repeat("$#$#," % [$s, R.L], R.Q) & 
        repeat("$#$#," % [$t, R.U], R.P)
    else: ""

proc Tw(p, t, P, Q: int): string =
  let S = P + Q
  result = "$#D,$#$#U,$#$#D,$#$#U," % [
    $t, if P > n - P: repeat("$#L," % $p, n - P) else: repeat("$#R," % $p, P),
    $t, if S > n - S: repeat("$#R," % $p, n - S) else: repeat("$#L," % $p, S), 
    $t, if Q > n - Q: repeat("$#L," % $p, n - Q) else: repeat("$#R," % $p, Q), 
    $t]

proc line(r: int): string=
  let p = n - 1
  let q = r mod n
  let i = find(m, o[r])
  var t = i mod n
  if t == q: 
    return ""
  let j = t == n - 1
  var P = t - q
  let x = p*n + q
  let y = x + P
  let z = y + (if j: -1 else: 1)
  let w = m[x]
  m[x] = m[y]
  m[y] = m[z]
  m[z] = w
  if j:
    let R = rotations(1, P)
    result = "$#D,$#$#U,$#$#R,$#D,$#L,$#U," % [
      $t, repeat("$#$#," % [$p, R.R], R.Q), 
      $t, repeat("$#$#," % [$p, R.L], R.Q), 
      $p, $t, $p, $t]
  else:
    result = Tw(p, t, P, 1)  
  
proc swap: string=
  result = ""
  if m[^1] != o[^1]:
    m = o
    for i in 0..(n div 2-1):
      result &= Tw(n - 1, n - 2*i - 1, 1, 1)
    result &= "$#R," % $(n - 1)
  
var moves = ""
for r in 0..(n^2 - n - 1):
  moves &= triangle(r)
if n == 2 and m[^1] != o[^1]:
  m = o
  moves &= "1R"
else:
  for r in (n^2 - n)..(n^2 - 3):
    moves &= line(r)
  if n mod 2 == 0:
    moves &= swap()
  if len(moves) > 0:
    moves = moves[0..^2]
  
echo moves

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" ( 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 koordinat[hal,q], lalu cari selnya [s,t] yang saat ini berisi nomor yang harus dituju [hal,q], dan lengkapi segitiga siku-siku dengan memilih titik ketiga [kamu,v] menurut beberapa pola, seperti yang ditunjukkan pada Gambar. 4 dari artikel yang ditautkan.

Pada 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 [hal,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 dinamaiTWdalam 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, jika naneh, 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, proc swapkinerja kitaTW bergerak dalam urutan terbalik.

Di tepi kasus n=2 kita tidak memerlukan semua prosedur rumit ini sama sekali - jika elemen baris terakhir tidak ada setelah bagian 1, satu 1R Langkah ini cukup untuk membuat matriks terurut sepenuhnya.

Pembaruan: Menambahkan baru proc rotationsyang membalikkan arah gerakan jika itu akan menghasilkan langkah yang lebih sedikit.

Kirill L.
sumber
Impresif! Saya akan membuat beberapa test case lagi. Sementara itu, saya yakin solusi ini dapat dioptimalkan, karena ada potongan seperti yang 7L,7L,7L,7L,7D,7D,7D,7Ddapat dikurangi dan 8R,8R,8R,8R,8R,8R,8Rdaripada dapat dikonversi ke 8L,8Luntuk matriks 9x9.
Charlie
Saya telah mencoba algoritma Anda dengan matriks 100x100 dan menyelesaikannya dalam waktu kurang dari 4 detik. Saya benar-benar tidak berharap masalah ini memiliki solusi linear-waktu. Saya akan mencoba menulis tantangan yang lebih baik di masa depan!
Charlie
Mungkin akan lebih baik untuk mengajukan tantangan ini dengan satu, matriks tetap sebagai satu-satunya kasus uji, dan menetapkan kriteria pemenang menjadi hanya ukuran jalan yang ditemukan untuk menyelesaikannya, seandainya saya tahu sebelumnya bahwa masalah ini memiliki O (n ^ 2) solusi. Apakah Anda akan mempertimbangkan untuk memasukkan jawaban ini ke pertanyaan baru dengan kriteria kemenangan seperti itu?
Charlie
@Charlie Sementara saya masih akan mencoba untuk memperbaiki solusi saat ini sedikit, saya benar-benar tidak tahu, bagaimana mengatasi masalah optimasi jalur secara keseluruhan ...
Kirill L.
5

Python 2 , ukuran 100 dalam <30 detik pada TIO

import random
def f(a):
 d = len(a)
 r = []
 def V(j, b = -1):
  b %= d
  if d - b < b:
   for k in range(d - b):
    if r and r[-1] == "U%d" % j:r.pop()
    else:r.append("D%d" % j)
    b = a[-1][j]
    for i in range(len(a) - 1):
     a[-1 - i][j] = a[-2 - i][j]
    a[0][j] = b
  else:
   for k in range(b):
    if r and r[-1] == "D%d" % j:r.pop()
    else:r.append("U%d" % j)
    b = a[0][j]
    for i in range(len(a) - 1):
     a[i][j] = a[i + 1][j]
    a[-1][j] = b
 def H(i, b = -1):
  b %= d
  if d - b < b:
   for k in range(d - b):
    if r and r[-1] == "L%d" % i:r.pop()
    else:r.append("R%d" % i)
    a[i] = a[i][-1:] + a[i][:-1]
  else:
   for k in range(b):
    if r and r[-1] == "R%d" % i:r.pop()
    else:r.append("L%d" % i)
    a[i] = a[i][1:] + a[i][:1]
 b = sorted(sum(a, []))
 for i in range(d - 1):
  for j in range(d):
   c = b.pop(0)
   e = sum(a, []).index(c)
   if e / d == i:
    if j == 0:H(i, e - j)
    elif j < e % d:
     if i:
      V(e % d, 1)
      H(i, j - e)
      V(e % d)
      H(i, e - j)
     else:
      V(e)
      H(1, e - j)
      V(j, 1)
   else:
    if j == e % d:
     H(e / d)
     e += 1
     if e % d == 0:e -= d
    if i:
     V(j, i - e / d)
    H(e / d, e - j)
    V(j, e / d - i)
 c = [b.index(e) for e in a[-1]]
 c = [sum(c[(i + j) % d] < c[(i + k) % d] for j in range(d) for k in range(j)) % 2 and d * d or sum(abs(c[(i + j) % d] - j) for j in range(d)) for i in range(d)]
 e = min(~c[::-1].index(min(c)), c.index(min(c)), key = abs)
 H(d - 1, e)
 for j in range(d - 2):
  e = a[-1].index(b[j])
  if e > j:
   c = b.index(a[-1][j])
   if c == e:
    if e - j == 1:c = j + 2
    else:c = j + 1
   V(e)
   H(d - 1, j - e)
   V(e, 1)
   H(d - 1, c - j)
   V(e)
   H(d - 1, e - c)
   V(e, 1)
 return r

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:

  • Elemen berada di baris yang benar, tetapi termasuk dalam kolom 0. Dalam hal ini, elemen tersebut diputar secara sederhana hingga mencapai kolom 0.
  • Elemen berada di tempat yang benar. Dalam hal ini, tidak ada yang terjadi. (Ini juga benar jika elemennya berada di kolom 0, hanya saja 0 rotasi terjadi dalam kasus itu.)
  • Elemen ada di baris atas tetapi di kolom yang salah. Dalam hal ini, ia diputar ke bawah, lalu secara horizontal hingga elemen berada di kolom yang benar, kemudian diputar lagi.
  • Elemen berada di baris yang benar tetapi di kolom yang salah. Dalam hal ini, ia diputar ke atas, kemudian baris diputar ke kolomnya, kemudian diputar ke bawah, kemudian baris diputar kembali. (Secara efektif ini adalah rotasi dari kasus selanjutnya.)
  • Elemen di kolom yang benar tetapi di baris yang salah. Dalam hal ini, baris diputar ke kanan, untuk menguranginya ke kasus terakhir.
  • Elemen berada di baris yang salah dan kolom yang salah. Dalam hal ini, kolom yang benar diputar ke baris yang salah (dilewati untuk baris atas), baris itu kemudian diputar ke kolom yang benar, dan kolom kemudian diputar kembali.

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.

Neil
sumber
Terima kasih banyak atas jawaban Anda, Neil! Tapi ingat, ini bukan kode golf. Alih-alih panjang kode Anda harus menunjukkan ukuran terbesar N dari matriks NxN yang telah Anda pecahkan dan panjang daftar gerakan untuk menyelesaikan matriks itu.
Charlie
@ Charlie Yah, itu 6, tapi hanya karena aku sudah terlalu malas untuk menempelkan dalam matriks yang lebih besar. Meskipun itu brute force, ia berskala secara linear dengan area, jadi ia harus mampu menghasilkan matriks besar.
Neil
Sebenarnya, kasus terburuk mungkin kuadratik dengan luas.
Neil
1
Tautan @Charlie TIO sekarang memecahkan matriks 100x100 acak.
Neil
1
@Charlie Saya sekarang telah datang dengan optimasi besar untuk baris bawah, tapi saya pikir itu perubahan terakhir yang akan saya buat untuk jawaban ini.
Neil