La idea de este desafío de código es simple: dada una matriz de enteros, clasifíquela aplicando movimientos de estilo Rubik. Esto significa que puede seleccionar una sola fila o columna y rotar sus elementos en cualquier dirección:
[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)
Entonces, dada una matriz de enteros de cualquier dimensión, clasifique sus elementos aplicando solo estas transformaciones de estilo Rubik. Una matriz
se considerará ordenado si sus elementos cumplen con la siguiente restricción:
I / O
- La entrada será una matriz de enteros positivos sin valores repetidos.
- La salida serán los movimientos necesarios para ordenarlo. Como este no es un desafío de código de golf y no necesita preocuparse por su longitud, el formato propuesto para cada movimiento es
#[UDLR]
dónde#
está el número de la fila o columna a mover (índice 0) y[UDLR]
es un solo carácter en ese rango que especifica si el movimiento es Arriba / Abajo (para columnas) o Izquierda / Derecha (para filas). Entonces1U
significaría "mover la 1ª columna hacia arriba" pero1R
sería "mover la 1ª fila hacia la derecha". Los movimientos serán separados por comas, por lo que una solución se expresa así:1R,1U,0L,2D
.
Puntuación
Intentar ordenar una matriz de esta manera puede ser costoso ya que hay muchas combinaciones posibles de movimientos, y también hay muchas listas posibles de movimientos que pueden ordenarlo, por lo que el objetivo es escribir un código que clasifique el N * N matrices a continuación. El puntaje será el mayor tamaño N que puede resolver en una cantidad razonable de tiempo 1 sin errores (cuanto mayor sea el tamaño de la matriz resuelta, mejor). En caso de empate, el desempate será el número de movimientos en su camino encontrado (cuanto más corto sea el camino, mejor).
Ejemplo: si un usuario A encuentra una solución para N = 5 y B encuentra una solución para N = 6, B gana independientemente de la longitud de ambas rutas. Si ambos encuentran soluciones para N = 6 pero la solución encontrada por A tiene 50 pasos y la solución de B tiene 60 pasos, A gana.
Las explicaciones sobre cómo funciona su código son altamente recomendables y publique las soluciones encontradas para que podamos probarlas . Puedes usar Pastebin o herramientas similares si las soluciones son demasiado grandes. Además, se apreciará una estimación del tiempo empleado por su código para encontrar sus soluciones.
Casos de prueba
Las siguientes matrices ( enlace de Pastebin para una versión más pegable) se han creado a partir de matrices ya ordenadas al mezclarlas con 10K movimientos aleatorios de estilo 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 A reasonable amount of time: any amount of time that doesn't undermine our patience while testing your solution. Note that TIO only runs code for 60 seconds, any amount of time over that limit will make us test the code in our machines. Example: my rather inefficient algorithm takes a few milliseconds to solve matrices of order 3x3 and 4x4, but I have just tested it with a 5x5 matrix and it took 317 seconds to solve it (in over 5 million movements, very funny if we consider that the matrix to solve was scrambled only 10K times). I tried to reduce the number of movements to less than 10K but I surrendered after 30 minutes executing the code.
O(input size)
entonces? ¿Para una matriz de 5x5 lo haríaO(25)
? Eso parece ser extremadamente rápido, por lo que me interesaría mucho ver ese algoritmo o implementación tuya. EDITAR: Te das cuenta de que ingresamos la matriz 'codificada' y emitimos los movimientos, ¿verdad? No de la otra manera.Respuestas:
Nim
Pruébalo en línea!
Un intento rápido de implementar el algoritmo de solución de rompecabezas Torus de un artículo publicado en Algorithms 2012, 5, 18-29 que mencioné en los comentarios.
Acepta la matriz de entrada en forma aplanada, como una línea de números delimitados por espacios.
Aquí también hay un validador en Python 2 . Toma dos líneas como entrada: la matriz codificada original en la misma forma que el código principal y la secuencia de movimientos propuesta. La salida del validador es la matriz resultante de la aplicación de estos movimientos.
Explicación
En la primera parte del algoritmo, ordenamos todas las filas excepto la última.
Hacemos esto realizando series de "rotaciones de triángulos" ([ p , q] , luego encuentra la celda [ s , t ] que actualmente contiene el número que debería ir a [ p , q] y complete el triángulo rectángulo seleccionando un tercer punto [ u , v ] según algún patrón, como se muestra en la Fig. 4 del artículo vinculado.
proc triangle
): las secuencias de movimientos que resultan en solo tres celdas intercambiando lugares, y todo el resto permanece sin cambios. Tomamos cada celda "en funcionamiento" consecutiva con coordenadasEn la Fig. 2, los autores presentan 8 patrones posibles y las secuencias de movimientos correspondientes, pero en mi código todos los casos han sido cubiertos por solo 5 patrones, de modo que no. 1, 5 y 6 no se utilizan.
En la segunda parte, la última fila, excepto los dos últimos elementos, se ordena realizando "tres rotaciones de elementos" en una línea (
proc line
), que consiste en dos rotaciones triangulares cada una (ver Fig. 3 del artículo).Seleccionamos nuestra celda de trabajo actual[ p , q] como el punto izquierdo, celda que contiene el valor objetivo [ s , t ] como el punto central, y [ s , t + 1 ] como el punto correcto Este movimiento hacia el oeste se llamaTW en el artículo, y también mi proceso de formación de cadenas para esto. Sit ya es la última columna, de modo que t + 1 no existe, tomamos [ s , t - 1 ] como tercer punto, y modifique la acción en consecuencia: los patrones 7 y 8 realizan dos rotaciones triangulares (en lugar de 7 y 1 en el original TW secuencia).
Finalmente sinorte es extraño, los dos elementos restantes ya deben estar en su lugar, ya que tenemos la garantía de que existe una solución. Sinorte es par, y los dos elementos restantes no están en su lugar, de acuerdo con el Lema 1 (página 22), se pueden intercambiar por una serie de TW movimientos, seguido de un turno al este (= R ) Dado que el ejemplo proporcionado intercambia las dos primeras entradas, y necesitamos intercambiar las dos últimas, nuestro TW se mueve en orden inverso.
proc swap
rendimientoEn el caso límite den = 2 no necesitamos todos estos procedimientos complejos en absoluto: si los elementos de la última fila no están en su lugar después de la parte 1, un solo 1 R mover es suficiente para hacer que la matriz esté completamente ordenada.
Actualización: Se agregó nuevo
proc rotations
que invierte la dirección de los movimientos si eso daría como resultado menos pasos.fuente
7L,7L,7L,7L,7D,7D,7D,7D
que pueden reducirse y8R,8R,8R,8R,8R,8R,8R
convertirse en8L,8L
una matriz de 9x9.Python 2 , tamaño 100 en <30 segundos en TIO
Pruébalo en línea! Link incluye tres casos de prueba pequeños con salida de movimiento completa, más una prueba silenciosa de 100x100 para mostrar que el código funciona (la salida de movimiento excedería los límites de TIO). Explicación: El código intenta realizar una ordenación por inserción en la matriz, acumulándola en orden ascendente a medida que avanza. Para todas las filas excepto la última fila, hay varios casos:
Las rotaciones anteriores se realizan en cualquier dirección que minimice el número de pasos; un cuadrado de tamaño 2 siempre se resuelve utilizando movimientos hacia la izquierda y hacia arriba, independientemente de la descripción anterior.
Antes de completar la fila inferior, se gira para minimizar la distancia total fuera de lugar, pero también para garantizar que la paridad de la fila inferior sea uniforme, ya que la parte final del algoritmo no puede cambiarla. Si hay más de una rotación con la misma distancia mínima, se elige la rotación con el menor número de movimientos.
El algoritmo para la fila inferior se basa en una secuencia de 7 operaciones que intercambia los elementos en tres columnas. La secuencia se aplica a cada uno de los números restantes de la fila inferior con el fin de llevarlos a su ubicación deseada; si es posible, el elemento en esa ubicación se mueve a la ubicación deseada, pero si se necesita un intercambio directo, el elemento simplemente se mueve a la columna disponible más cercana, con suerte permitiendo que se repare la próxima vez.
fuente