Vamos a definir una matriz no vacía, sin clasificar y finita con números únicos de la siguiente manera:
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:
↑0
o ↓0
. (Observe que cualquiera de esos movimientos puede ordenar la matriz para que ambas respuestas sean correctas)
Entrada:
→0
Entrada (Ejemplo de caso de prueba):
↑0↑1←1↑2
Entrada:
↑0↑2→0→2↑0→2↑1↑2←1
↑2↑1←3→0←3↓0←0←2→3↑3↑4
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 código-golf
Los casos de prueba adicionales siempre son bienvenidos
←0←0
una 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.Respuestas:
JavaScript (ES6),
226219 bytesBú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.
Pruébalo en línea!
Comentado
fuente
Python 2 , 296 277 245Python 3 ,200194 bytesPrué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
→n
es equivalente adonde
r
yc
son los números de filas y columnas, estos movimientos son suficientes para encontrar todas las soluciones.>v
corresponden respectivamente a→↓
. (otros indefinidos)fuente
Jalea , 35 bytes
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.
fuente