Semacam rotasi matriks

12

Mari kita tentukan matriks yang tidak kosong, tidak disortir, dan terbatas dengan angka unik sebagai berikut:

N={457136}

Mari kita tentukan pergerakan 4 matriks sebagai:

  • ↑ * (atas): Memindahkan kolom ke atas
  • ↓ * (bawah): Memindahkan kolom ke bawah
  • → * (kanan): Memindahkan satu baris ke kanan
  • ← * (kiri): Memindahkan satu baris ke kiri

Tanda bintang (*) mewakili kolom / baris yang dipengaruhi oleh gerakan (Dapat diindeks 0 atau diindeks 1. Terserah Anda. Sebutkan yang mana dalam jawaban Anda).


Tantangannya adalah, menggunakan gerakan di atas, urutkan matriks dalam urutan naik (menjadi sudut kiri atas yang terendah dan sudut kanan bawah yang tertinggi).

Contoh

Input:

N={423156}
Kemungkinan Output: ↑0atau ↓0. (Perhatikan semua gerakan itu dapat mengurutkan matriks sehingga kedua jawabannya benar)


Input:

N={231456}
Kemungkinan Output:→0


Input (Contoh test case):

N={457136}
Kemungkinan Output:↑0↑1←1↑2


Input:

N={596824173}
Kemungkinan Output: ↑0↑2→0→2↑0→2↑1↑2←1


N={127282961023451778139151112181426162119203022232425}
↑2↑1←3→0←3↓0←0←2→3↑3↑4


N={1}


N={1234}


Catatan

  • Mungkin ada keluaran yang benar berbeda (tidak perlu harus sama dengan kasus uji atau yang terpendek)
  • Anda dapat menganggap itu akan selalu menjadi cara untuk memesan matriks
  • Tepi menghubungkan (seperti pacman: v)
  • Tidak akan ada matriks dengan lebih dari 9 kolom atau / dan baris
  • Asumsikan matriks hanya berisi bilangan bulat unik bukan nol yang positif
  • Anda dapat menggunakan 4 nilai berbeda selain angka untuk mewakili gerakan (dalam hal itu, harap sebutkan dalam jawaban Anda)
  • Kolom / baris dapat diindeks 0 atau 1
  • kriteria menang

Kasus uji ekstra selalu diterima

Luis felipe De jesus Munoz
sumber
5
Inilah situs web tempat Anda bisa memecahkan sendiri teka-teki ini.
Gagang Pintu
1
@ Doorknob Itu akan berguna ketika saya sedang menulis tantangan Dx. Bagaimanapun, terima kasih!
Luis felipe De jesus Munoz
Saya tidak berpikir Anda mengatakan di mana pun bahwa solusi yang diberikan harus sesingkat mungkin. Apakah itu disengaja? Misalnya adalah ←0←0solusi yang valid untuk contoh kedua di mana Anda telah memberikan solusi sebagai →0. Jika ya, saya pikir setengah dari opsi pemindahan kemungkinan tidak akan digunakan.
FryAmTheEggman
1
Juga beberapa orang mungkin ingin mencoba openprocessing.org/sketch/580366 yang dibuat oleh youtuber bernama carykh. Ini disebut "loopover"
Gareth Ma

Jawaban:

3

JavaScript (ES6),  226  219 byte

Pencarian kasar, menggunakan gerakan kanan ( "R") dan turun ( "D").

Mengembalikan string yang menggambarkan gerakan, atau array kosong jika matriks input sudah diurutkan. Kolom dan baris dalam output diindeks 0.

f=(m,M=2)=>(g=(s,m)=>m[S='some'](p=r=>r[S](x=>p>(p=x)))?!s[M]&&m[0][S]((_,x,a)=>g(s+'D'+x,m.map(([...r],y)=>(r[x]=(m[y+1]||a)[x])&&r)))|m[S]((_,y)=>g(s+'R'+y,m.map(([...r])=>y--?r:[r.pop(),...r]))):o=s)([],m)?o:f(m,M+2)

Cobalah online!

Berkomentar

f =                              // f = main recursive function taking:
(m, M = 2) => (                  //   m[] = input matrix; M = maximum length of the solution
  g =                            // g = recursive solver taking:
  (s, m) =>                      //   s = solution, m[] = current matrix
    m[S = 'some'](p =            // we first test whether m[] is sorted
      r =>                       // by iterating on each row
        r[S](x =>                // and each column
          p > (p = x)            // and comparing each cell x with the previous cell p
        )                        //
    ) ?                          // if the matrix is not sorted:
      !s[M] &&                   //   if we haven't reached the maximum length:
      m[0][S]((_, x, a) =>       //     try all 'down' moves:
        g(                       //       do a recursive call:
          s + 'D' + x,           //         append the move to s
          m.map(([...r], y) =>   //         for each row r[] at position y:
            (r[x] =              //           rotate the column x by replacing r[x] with
              (m[y + 1] || a)[x] //           m[y + 1][x] or a[x] for the last row (a = m[0])
            ) && r               //           yield the updated row
      ))) |                      //
      m[S]((_, y) =>             //     try all 'right' moves:
        g(                       //       do a recursive call:
          s + 'R' + y,           //         append the move to s
          m.map(([...r]) =>      //         for each row:
            y-- ?                //           if this is not the row we're looking for:
              r                  //             leave it unchanged
            :                    //           else:
              [r.pop(), ...r]    //             rotate it to the right
      )))                        //
    :                            // else (the matrix is sorted):
      o = s                      //   store the solution in o
)([], m) ?                       // initial call to g(); if we have a solution:
  o                              //   return it
:                                // else:
  f(m, M + 2)                    //   try again with a larger maximum length
Arnauld
sumber
Jawaban bagus. Apakah Anda tahu jika ada algo yang efisien untuk ini, atau jika mungkin untuk menentukan jumlah gerakan maksimum yang dapat dilakukan suatu solusi tanpa harus memaksa?
Jonah
1
@Jonah Berikut ini adalah makalah yang menjelaskan solusi dan memberikan batas atas jumlah gerakan. (Lihat juga tantangan ini yang pada dasarnya tugas yang sama dengan kriteria kemenangan yang berbeda.)
Arnauld
Wow, terima kasih @Arnauld
Jonah
2

Python 2 , 296 277 245 Python 3 , 200 194 byte

from numpy import*
def f(p):
 s='';u=[]
 while any(ediff1d(p)<0):u+=[(copy(p),s+f'v{v}',f':,{v}')for v in r_[:shape(p)[1]]]+[(p,s+'>0',0)];p,s,i=u.pop(0);exec(f'p[{i}]=roll(p[{i}],1)')
 return s

Cobalah online!

-19: panah unicode tidak diperlukan ...
-32: sedikit ulang, tapi kinerja lebih lambat rata-rata.
-45: mengambil inspirasi dari jawaban @ Arnauld. Beralih ke Python 3 untuk f''(-4 byte)
-6: range( )r_[: ] , diff(ravel( ))ediff1d( )


Secara teliti mencari kombinasi dari semua kemungkinan gerakan dan →0. Hentikan uji kasus ketiga.

Karena →nsetara dengan

01...↓(c-1) 	... repeated r-n times
0
01...↓(c-1)	... repeated n times

di mana rdan cjumlah baris dan kolom, gerakan ini cukup untuk menemukan setiap solusi.


from numpy import*
def f(p):
    s=''                                    #s: sequence of moves, as string
    u=[]                                    #u: queue of states to check
    while any(ediff1d(p)<0):                #while p is not sorted
        u+=[(copy(p),s+f'v{v}',f':,{v}')    #add p,↓v to queue
            for v in r_[:shape(p)[1]]]      # for all 0<=v<#columns
        u+=[(p,s+'>0',0)]                   #add p,→0
        p,s,i=u.pop(0)                      #get the first item of queue
        exec(f'p[{i}]=roll(p[{i}],1)')      #transform it
    return s                                #return the moves taken

>vmasing-masing sesuai dengan →↓. (lainnya tidak terdefinisi)

attinat
sumber
0

Jelly , 35 byte

ṙ€LXȮƊ¦1
ÇZÇZƊ⁾ULXȮOịØ.¤?F⁻Ṣ$$¿,“”Ṫ

Cobalah online!

Program lengkap. Output bergerak ke STDOUT menggunakan L untuk kiri dan R untuk kanan. Terus mencoba gerakan acak sampai matriks diurutkan, jadi tidak terlalu efisien dalam hal kecepatan atau kompleksitas algoritmik.

Nick Kennedy
sumber