Matrix Rotation sortieren

12

Definieren wir eine nicht leere, unsortierte und endliche Matrix mit eindeutigen Zahlen wie folgt:

N={457136}

Definieren wir 4 Matrixbewegungen als:

  • ↑ * (nach oben): Verschiebt eine Spalte nach oben
  • ↓ * (nach unten): Verschiebt eine Spalte nach unten
  • → * (rechts): Verschiebt eine Reihe nach rechts
  • ← * (links): Verschiebt eine Zeile nach links

Das Sternchen (*) stellt die Spalte / Zeile dar, die von der Verschiebung betroffen ist. (Es kann 0-indiziert oder 1-indiziert sein. Bitte geben Sie in Ihrer Antwort an, welche).


Die Herausforderung besteht darin, die Matrix mithilfe der obigen Schritte in aufsteigender Reihenfolge zu sortieren (wobei die obere linke Ecke die niedrigste und die untere rechte Ecke die höchste ist).

Beispiel

Eingabe:

N={423156}
Mögliche Ausgabe: ↑0oder ↓0. (Beachten Sie, dass jede dieser Bewegungen die Matrix sortieren kann, sodass beide Antworten korrekt sind.)


Eingabe: Mögliche Ausgabe:

N={231456}
→0


Eingabe (Beispiel Testfall): Mögliche Ausgabe:

N={457136}
↑0↑1←1↑2


Eingabe: Mögliche Ausgabe:

N={596824173}
↑0↑2→0→2↑0→2↑1↑2←1


Eingabe:

N={127282961023451778139151112181426162119203022232425}
Mögliche Ausgabe: ↑2↑1←3→0←3↓0←0←2→3↑3↑4


N={1}


N={1234}


Anmerkungen

  • Es kann verschiedene korrekte Ausgaben geben (es müssen nicht unbedingt die gleichen wie die Testfälle oder die kürzesten sein)
  • Sie können davon ausgehen, dass es immer eine Möglichkeit sein wird, die Matrix zu bestellen
  • Kanten verbindet (wie Pacman: v)
  • Es wird keine Matrix mit mehr als 9 Spalten oder / und Zeilen geben
  • Angenommen, die Matrix enthält nur positive eindeutige Ganzzahlen ungleich Null
  • Sie können 4 verschiedene Werte als Zahlen verwenden, um die Bewegungen darzustellen (in diesem Fall geben Sie dies bitte in Ihrer Antwort an).
  • Spalte / Zeile kann mit 0 oder 1 indiziert werden
  • Gewinnkriterien

Zusätzliche Testfälle sind immer willkommen

Luis Felipe De Jesus Munoz
quelle
5
Hier ist eine Website, auf der Sie diese Rätsel selbst lösen können.
Türklinke
1
@Doorknob Das wäre nützlich gewesen, als ich die Herausforderung Dx geschrieben habe. Danke trotzdem!
Luis Felipe De Jesus Munoz
Ich glaube nicht, dass Sie irgendwo sagen, dass die gegebene Lösung so kurz wie möglich sein muss. Ist das beabsichtigt? Zum Beispiel ist ←0←0eine gültige Lösung für das zweite Beispiel, in dem Sie eine Lösung als angegeben haben →0. Wenn dies der Fall ist, wird wahrscheinlich die Hälfte der Verschiebeoptionen nicht verwendet.
FryAmTheEggman
1
Einige Leute möchten vielleicht auch openprocessing.org/sketch/580366 ausprobieren, das von einem Youtuber namens Carykh erstellt wurde. Es heißt "Loopover"
Gareth Ma

Antworten:

3

JavaScript (ES6),  226.219  Byte

Brute-Force-Methode, mit rechts ( "R") und nach unten ( "D") bewegt.

Gibt entweder eine Zeichenfolge zurück, die die Bewegungen beschreibt, oder ein leeres Array, wenn die Eingabematrix bereits sortiert ist. Spalten und Zeilen in der Ausgabe sind 0-indiziert.

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)

Probieren Sie es online!

Kommentiert

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
quelle
Gute Antwort. Wissen Sie, ob es dafür einen effizienten Algorithmus gibt oder ob es möglich ist, die maximale Anzahl von Zügen zu bestimmen, die eine Lösung ohne grobe Gewalt ausführen kann?
Jonah
1
@Jonah Hier ist ein Artikel , der eine Lösung beschreibt und eine Obergrenze für die Anzahl der Züge angibt . (Siehe auch diese Herausforderung, die im Grunde die gleiche Aufgabe mit einem anderen Gewinnkriterium ist.)
Arnauld
Wow, danke @Arnauld
Jonah
2

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

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

Probieren Sie es online!

-19: Unicode-Pfeile wurden nicht benötigt ...
-32: leicht überarbeitet, aber im Durchschnitt viel langsamer.
-45: Hat sich von @ Arnauld inspirieren lassen. Für f''(-4 Byte)
-6 auf Python 3 umgestellt: range( )r_[: ] , diff(ravel( ))ediff1d( )


Vollständige Suche nach Kombinationen aller möglichen Züge und →0. Zeitüberschreitung beim dritten Testfall.

Da →nist gleichbedeutend mit

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

Wo rund cwie viele Zeilen und Spalten vorhanden sind, reichen diese Bewegungen aus, um jede Lösung zu finden.


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

>ventsprechen jeweils →↓. (andere undefiniert)

attinat
quelle
0

Gelee , 35 Bytes

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

Probieren Sie es online!

Volles Programm. Die Ausgänge werden mit L für links und R für rechts nach STDOUT verschoben. Versucht weiterhin zufällige Bewegungen, bis die Matrix sortiert ist, was die Geschwindigkeit oder die algorithmische Komplexität betrifft.

Nick Kennedy
quelle