Orden de rotación de matriz

12

Vamos a definir una matriz no vacía, sin clasificar y finita con números únicos de la siguiente manera:

N={457136}

Vamos a definir 4 movimientos de matriz como:

  • ↑ * (arriba): Mueve una columna hacia arriba
  • ↓ * (abajo): mueve una columna hacia abajo
  • → * (derecha): mueve una fila a la derecha
  • ← * (izquierda): mueve una fila a la izquierda

El asterisco (*) representa la columna / fila que se ve afectada por el movimiento (puede estar indexado 0 o indexado. Depende de usted. Indique cuál en su respuesta).


El desafío es, usando los movimientos anteriores, ordenar la matriz en orden ascendente (siendo la esquina superior izquierda la más baja y la esquina inferior derecha la más alta).

Ejemplo

Entrada:

N={423156}
Salida posible: ↑0o ↓0. (Observe que cualquiera de esos movimientos puede ordenar la matriz para que ambas respuestas sean correctas)


Entrada:

N={231456}
Salida posible:→0


Entrada (Ejemplo de caso de prueba):

N={457136}
Salida posible:↑0↑1←1↑2


Entrada:

N={596824173}
Salida posible: ↑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}


Notas

  • Puede haber diferentes resultados correctos (no es necesario que sean necesariamente los mismos que los casos de prueba o el más corto)
  • Puede suponer que siempre será una forma de ordenar la matriz
  • Bordes conecta (como pacman: v)
  • No habrá una matriz con más de 9 columnas o filas
  • Suponga que la matriz contiene solo enteros únicos positivos distintos de cero
  • Puede usar 4 valores distintos que no sean números para representar los movimientos (en ese caso, indíquelo en su respuesta)
  • La columna / fila puede ser 0 o 1 indexada
  • Criterio ganador

Los casos de prueba adicionales siempre son bienvenidos

Luis felipe De jesus Munoz
fuente
55
Aquí hay un sitio web donde puede resolver estos rompecabezas usted mismo.
Pomo de la puerta
1
@Doorknob Eso hubiera sido útil cuando estaba escribiendo el desafío Dx. ¡Gracias de cualquier manera!
Luis felipe De jesus Munoz
No creo que digas en ningún lado que la solución dada debe ser lo más breve posible. ¿Es eso intencional? Por ejemplo, es ←0←0una solución válida para el segundo ejemplo donde ha dado una solución como →0. Si es así, creo que la mitad de las opciones de movimiento probablemente no se utilizarán.
FryAmTheEggman
1
También algunas personas pueden querer probar openprocessing.org/sketch/580366 hecho por un youtuber llamado carykh. Se llama "loopover"
Gareth Ma

Respuestas:

3

JavaScript (ES6),  226  219 bytes

Búsqueda de fuerza bruta, utilizando movimientos hacia la derecha ( "R") y hacia abajo ( "D").

Devuelve una cadena que describe los movimientos o una matriz vacía si la matriz de entrada ya está ordenada. Las columnas y filas en la salida están indexadas a 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)

Pruébalo en línea!

Comentado

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
fuente
Buena respuesta. ¿Sabes si existe un algoritmo eficiente para esto, o si es posible determinar el número máximo de movimientos que una solución puede tener sin forzarlo?
Jonás
1
@ Jonás Aquí hay un artículo que describe una solución y da un límite superior del número de movimientos. (Vea también este desafío, que es básicamente la misma tarea con un criterio ganador diferente.)
Arnauld
Wow, gracias @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

Pruébalo en línea!

-19: no se necesitaban flechas unicode ...
-32: ligeramente reelaborado, pero un rendimiento mucho más lento en promedio.
-45: se inspiró en la respuesta de @ Arnauld. Cambió a Python 3 para f''(-4 bytes)
-6: range( )r_[: ] , diff(ravel( ))ediff1d( )


Busca exhaustivamente combinaciones de todos los movimientos posibles y →0. Tiempos de espera en el tercer caso de prueba.

Como →nes equivalente a

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

donde ry cson los números de filas y columnas, estos movimientos son suficientes para encontrar todas las soluciones.


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

>vcorresponden respectivamente a →↓. (otros indefinidos)

attinat
fuente
0

Jalea , 35 bytes

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

Pruébalo en línea!

Programa completo Las salidas se mueven a STDOUT usando L para la izquierda y R para la derecha. Sigue intentando movimientos aleatorios hasta que se ordena la matriz, por lo que no es muy eficiente en términos de velocidad o complejidad algorítmica.

Nick Kennedy
fuente