Rubik-ordenando una matriz (también conocido como el rompecabezas toro)

16

La idea de este 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

[un11un12un13un14un21un22un23un24un31un32un33un34]

se considerará ordenado si sus elementos cumplen con la siguiente restricción:

un11un12un13un14un21un22un23un24un31un32un33un34

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). Entonces 1Usignificaría "mover la 1ª columna hacia arriba" pero 1Rserí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:

[85 56 61110131513]
[211012dieciséis176 6221485 51926132431]
[1138dieciséis5 59 94021262211241439283219373103017367 734]
[34214022354118 años3331301243191139242823441365 5384514179 9dieciséis132683476 6254 4]
[2036171155018 años726734103235542439 96 630613928415427235 57048132512465863523784533146859sesenta y cinco567360 606422]
[855652758944416827158791 91323739736 67 76419997846dieciséis4221631004 41721311973093284033650702580589 960 60845496172943342335776182482943866]
[567990617112211031551144284851306188443386611324962010275685888098351007713216410810601144023472731068232120263653936910454191111176217278873349155811695112571189151426545]

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.

Charlie
fuente
1
Nice challenge! However, I have a few requests/questions: 1) Could you provide the test cases in a more copy-paste friendly format? (such as pastebin) 2) Could you provide a more precise definition of the time limit order? 3) Is the matrix guaranteed to be square? (The test cases suggest so, but the definition does not.)
Arnauld
@Arnauld 1) I'm on it. 2) I didn't want to establish a time limit, and nobody suggested any limit while the challenge was in the sandbox. If you need one, would you consider 30 minutes a reasonable limit? 3) Yes, the test matrices are the ones shown, and they will all be square if more are needed.
Charlie
There exists an (relatively easy to implement) O(input size) algorithm to this challenge, so it's not as interesting as it may look at first.
user202729
@ user202729 ¿Cuál sería el tamaño de entrada en su O(input size)entonces? ¿Para una matriz de 5x5 lo haría O(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.
Kevin Cruijssen
44
Creo que es algo así como este algoritmo
Kirill L.

Respuestas:

8

Nim

import algorithm, math, sequtils, strutils

let l = split(stdin.readLine())
var m = map(l, parseInt)
let n = int(sqrt(float(len(m))))
let o = sorted(m, system.cmp[int])

proc rotations(P, Q: int): tuple[D, L, R, U: string, P, Q: int]=
  result = (D: "D", L: "L", R: "R", U: "U", P: P, Q: Q)
  if P > n - P:
    result.D = "U"
    result.U = "D"
    result.P = n - P
  if Q > n - Q:
    result.L = "R"
    result.R = "L"
    result.Q = n - Q

proc triangle(r: int): string=
  let p = r div n
  let q = r mod n
  let i = find(m, o[r])
  let s = i div n
  let t = i mod n
  var u = s
  var v = q
  if s == p and t == q:
    return ""
  var patt = 0
  if p == s: 
    u = s + 1
    patt = 4
  elif q == t:
    if q == n - 1:
      v = t - 1
      patt = 8
    else:
      u = p
      v = t + 1
      patt = 3
  elif t > q:
    patt = 2
  else:
    patt = 7
  var Q = abs(max([q, t, v]) - min([q, t, v]))
  var P = abs(max([p, s, u]) - min([p, s, u]))
  let x = p*n + q
  let y = s*n + t
  let z = u*n + v
  let w = m[x]
  m[x] = m[y]
  m[y] = m[z]
  m[z] = w
  let R = rotations(P, Q)

  result = case patt:
    of 2:
      repeat("$#$#," % [$v, R.D], R.P) & 
        repeat("$#$#," % [$u, R.L], R.Q) &
        repeat("$#$#," % [$v, R.U], R.P) & 
        repeat("$#$#," % [$u, R.R], R.Q)
    of 3:
      repeat("$#$#," % [$q, R.U], R.P) & 
        repeat("$#$#," % [$p, R.L], R.Q) &
        repeat("$#$#," % [$q, R.D], R.P) & 
        repeat("$#$#," % [$p, R.R], R.Q)
    of 4:
      repeat("$#$#," % [$p, R.L], R.Q) & 
        repeat("$#$#," % [$q, R.U], R.P) &
        repeat("$#$#," % [$p, R.R], R.Q) & 
        repeat("$#$#," % [$q, R.D], R.P)
    of 7:
      repeat("$#$#," % [$v, R.D], R.P) & 
        repeat("$#$#," % [$u, R.R], R.Q) &
        repeat("$#$#," % [$v, R.U], R.P) & 
        repeat("$#$#," % [$u, R.L], R.Q)
    of 8:
      repeat("$#$#," % [$s, R.R], R.Q) & 
        repeat("$#$#," % [$t, R.D], R.P) &
        repeat("$#$#," % [$s, R.L], R.Q) & 
        repeat("$#$#," % [$t, R.U], R.P)
    else: ""

proc Tw(p, t, P, Q: int): string =
  let S = P + Q
  result = "$#D,$#$#U,$#$#D,$#$#U," % [
    $t, if P > n - P: repeat("$#L," % $p, n - P) else: repeat("$#R," % $p, P),
    $t, if S > n - S: repeat("$#R," % $p, n - S) else: repeat("$#L," % $p, S), 
    $t, if Q > n - Q: repeat("$#L," % $p, n - Q) else: repeat("$#R," % $p, Q), 
    $t]

proc line(r: int): string=
  let p = n - 1
  let q = r mod n
  let i = find(m, o[r])
  var t = i mod n
  if t == q: 
    return ""
  let j = t == n - 1
  var P = t - q
  let x = p*n + q
  let y = x + P
  let z = y + (if j: -1 else: 1)
  let w = m[x]
  m[x] = m[y]
  m[y] = m[z]
  m[z] = w
  if j:
    let R = rotations(1, P)
    result = "$#D,$#$#U,$#$#R,$#D,$#L,$#U," % [
      $t, repeat("$#$#," % [$p, R.R], R.Q), 
      $t, repeat("$#$#," % [$p, R.L], R.Q), 
      $p, $t, $p, $t]
  else:
    result = Tw(p, t, P, 1)  
  
proc swap: string=
  result = ""
  if m[^1] != o[^1]:
    m = o
    for i in 0..(n div 2-1):
      result &= Tw(n - 1, n - 2*i - 1, 1, 1)
    result &= "$#R," % $(n - 1)
  
var moves = ""
for r in 0..(n^2 - n - 1):
  moves &= triangle(r)
if n == 2 and m[^1] != o[^1]:
  m = o
  moves &= "1R"
else:
  for r in (n^2 - n)..(n^2 - 3):
    moves &= line(r)
  if n mod 2 == 0:
    moves &= swap()
  if len(moves) > 0:
    moves = moves[0..^2]
  
echo moves

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" ( 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 coordenadas[pag,q], luego encuentra la celda [s,t] que actualmente contiene el número que debería ir a [pag,q]y complete el triángulo rectángulo seleccionando un tercer punto [tu,v] según algún patrón, como se muestra en la Fig. 4 del artículo vinculado.

En 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 [pag,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 llamaTWen 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 si nortees 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 proc swaprendimientoTW se mueve en orden inverso.

En el caso límite de norte=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 1R mover es suficiente para hacer que la matriz esté completamente ordenada.

Actualización: Se agregó nuevo proc rotationsque invierte la dirección de los movimientos si eso daría como resultado menos pasos.

Kirill L.
fuente
¡Impresionante! Crearé más casos de prueba entonces. Mientras tanto, estoy seguro de que esta solución se puede optimizar, ya que hay fragmentos 7L,7L,7L,7L,7D,7D,7D,7Dque pueden reducirse y 8R,8R,8R,8R,8R,8R,8Rconvertirse en 8L,8Luna matriz de 9x9.
Charlie
He probado su algoritmo con una matriz de 100x100 y lo resuelve en menos de 4 segundos. Realmente no esperaba que este problema tuviera una solución de tiempo lineal. ¡Intentaré escribir mejores desafíos en el futuro!
Charlie
Tal vez hubiera sido mejor plantear este desafío con una única matriz fija como único caso de prueba, y establecer el criterio ganador para que fuera solo el tamaño de la ruta encontrada para resolverlo, si hubiera sabido antes que este problema tenía un O (n ^ 2) solución. ¿Consideraría transferir esta respuesta a una nueva pregunta con un criterio tan ganador?
Charlie
@Charlie Aunque aún intentaré refinar un poco la solución actual, realmente no tengo idea de cómo abordar el problema general de optimización de ruta ...
Kirill L.
5

Python 2 , tamaño 100 en <30 segundos en TIO

import random
def f(a):
 d = len(a)
 r = []
 def V(j, b = -1):
  b %= d
  if d - b < b:
   for k in range(d - b):
    if r and r[-1] == "U%d" % j:r.pop()
    else:r.append("D%d" % j)
    b = a[-1][j]
    for i in range(len(a) - 1):
     a[-1 - i][j] = a[-2 - i][j]
    a[0][j] = b
  else:
   for k in range(b):
    if r and r[-1] == "D%d" % j:r.pop()
    else:r.append("U%d" % j)
    b = a[0][j]
    for i in range(len(a) - 1):
     a[i][j] = a[i + 1][j]
    a[-1][j] = b
 def H(i, b = -1):
  b %= d
  if d - b < b:
   for k in range(d - b):
    if r and r[-1] == "L%d" % i:r.pop()
    else:r.append("R%d" % i)
    a[i] = a[i][-1:] + a[i][:-1]
  else:
   for k in range(b):
    if r and r[-1] == "R%d" % i:r.pop()
    else:r.append("L%d" % i)
    a[i] = a[i][1:] + a[i][:1]
 b = sorted(sum(a, []))
 for i in range(d - 1):
  for j in range(d):
   c = b.pop(0)
   e = sum(a, []).index(c)
   if e / d == i:
    if j == 0:H(i, e - j)
    elif j < e % d:
     if i:
      V(e % d, 1)
      H(i, j - e)
      V(e % d)
      H(i, e - j)
     else:
      V(e)
      H(1, e - j)
      V(j, 1)
   else:
    if j == e % d:
     H(e / d)
     e += 1
     if e % d == 0:e -= d
    if i:
     V(j, i - e / d)
    H(e / d, e - j)
    V(j, e / d - i)
 c = [b.index(e) for e in a[-1]]
 c = [sum(c[(i + j) % d] < c[(i + k) % d] for j in range(d) for k in range(j)) % 2 and d * d or sum(abs(c[(i + j) % d] - j) for j in range(d)) for i in range(d)]
 e = min(~c[::-1].index(min(c)), c.index(min(c)), key = abs)
 H(d - 1, e)
 for j in range(d - 2):
  e = a[-1].index(b[j])
  if e > j:
   c = b.index(a[-1][j])
   if c == e:
    if e - j == 1:c = j + 2
    else:c = j + 1
   V(e)
   H(d - 1, j - e)
   V(e, 1)
   H(d - 1, c - j)
   V(e)
   H(d - 1, e - c)
   V(e, 1)
 return r

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:

  • El elemento está en la fila correcta, pero pertenece a la columna 0. En este caso, simplemente se gira hasta llegar a la columna 0.
  • El elemento está en el lugar correcto. En este caso, no pasa nada. (Esto también es cierto si el elemento pertenece a la columna 0, es solo que ocurren 0 rotaciones en ese caso).
  • El elemento está en la fila superior pero en la columna incorrecta. En ese caso, se gira hacia abajo, luego horizontalmente hasta que el elemento esté en la columna correcta, luego se gira nuevamente hacia arriba.
  • El elemento está en la fila correcta pero en la columna incorrecta. En ese caso, se gira hacia arriba, luego la fila se gira hacia su columna, luego se gira hacia abajo, luego la fila se gira hacia atrás. (Efectivamente, esta es una rotación del siguiente caso).
  • El elemento está en la columna correcta pero en la fila incorrecta. En ese caso, la fila se gira hacia la derecha, para reducirla al último caso.
  • El elemento está en la fila incorrecta y la columna incorrecta. En este caso, la columna correcta se gira a la fila incorrecta (se omite para la fila superior), esa fila se gira a la columna correcta y la columna se gira hacia atrás.

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.

Neil
fuente
Muchas gracias por tu respuesta, Neil! Pero recuerde, este no es un código de golf. En lugar de la longitud del código, debe indicar el mayor tamaño N de la matriz NxN que ha resuelto y la longitud de la lista de movimientos para resolver esa matriz.
Charlie
@ Charlie Bueno, eso es 6, pero solo porque he sido demasiado vago para pegar en una matriz más grande. Aunque es fuerza bruta, se escala linealmente con el área, por lo que debería ser capaz de matrices grandes.
Neil
En realidad, el peor de los casos podría ser cuadrático con el área.
Neil
1
El enlace @Charlie TIO ahora resuelve una matriz aleatoria de 100x100.
Neil
1
@Charlie Ahora tengo una gran optimización para la fila inferior, pero creo que ese es el último cambio que haré en esta respuesta.
Neil