Rubik trie une matrice (alias le puzzle torus)

16

L'idée de ce est simple: étant donné une matrice d'entiers, trions-la en appliquant des mouvements de style Rubik. Cela signifie que vous pouvez sélectionner une seule ligne ou colonne et faire pivoter ses éléments dans n'importe quelle direction:

[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)

Donc, étant donné une matrice d'entiers de n'importe quelle dimension, triez ses éléments en appliquant uniquement ces transformations de style Rubik. Une matrice

[une11une12une13une14une21une22une23une24une31une32une33une34]

sera considéré trié si ses éléments respectent la restriction suivante:

une11une12une13une14une21une22une23une24une31une32une33une34

E / S

  • L'entrée sera une matrice d'entiers positifs sans valeurs répétées.
  • La sortie sera les mouvements nécessaires pour le trier. Comme ce n'est pas un défi de golf de code et que vous n'avez pas à vous soucier de sa longueur, le format proposé pour chaque mouvement est #[UDLR]#est le numéro de la ligne ou de la colonne à déplacer (indexé 0) et [UDLR]est un seul caractère dans ce plage qui spécifie si le mouvement est Haut / Bas (pour les colonnes) ou Gauche / Droite (pour les lignes). Cela 1Usignifierait donc "déplacer la 1ère colonne vers le haut" mais 1Rserait "déplacer la 1ère ligne vers la droite". Les mouvements seront séparés par des virgules, donc une solution sera exprimée comme suit: 1R,1U,0L,2D.

Notation

Essayer de trier une matrice de cette façon peut être coûteux car il y a beaucoup de combinaisons possibles de mouvements, et il y a aussi beaucoup de listes possibles de mouvements qui peuvent le trier, donc l'objectif est d'écrire du code qui trie le N * N matrices ci-dessous. Le score sera la plus grande taille N que vous pourrez résoudre en un temps raisonnable 1 sans erreurs (plus la taille de la matrice résolue est grande, mieux c'est). En cas d'égalité, le bris d'égalité sera le nombre de mouvements dans votre chemin trouvé (plus le chemin est court, mieux c'est).

Exemple: si un utilisateur A trouve une solution pour N = 5 et B trouve une solution pour N = 6, B gagne quelle que soit la longueur des deux chemins. S'ils trouvent tous les deux des solutions pour N = 6 mais que la solution trouvée par A a 50 étapes et la solution de B a 60 étapes, A gagne.

Les explications sur le fonctionnement de votre code sont fortement encouragées et veuillez publier les solutions trouvées afin que nous puissions les tester . Vous pouvez utiliser Pastebin ou des outils similaires si les solutions sont trop importantes. De plus, une estimation du temps passé par votre code à trouver vos solutions sera appréciée.

Cas de test

Les matrices suivantes ( lien Pastebin pour une version plus copiable) ont été créées à partir de matrices déjà triées en les brouillant avec des mouvements aléatoires de style Rubik de 10K:

[85611dix131513]
[21dix12161762214851926132431]
[113816594021262211241439283219373dix301736sept34]
[34214022354118333130124319113924282344136538451417916132683476254]
[2036171155018726734dix32355424396306139284154272357048132512465863523784533146859655673606422]
27 15 87 91 32 37 39 73 6 7 64 19 99 78 46 16 42 21 63
[855652758944416827158791323739736sept6419997846164221631004172131197309328403365070258058960845496172943342335776182482943866]
18
[5679906171122110315511442848513061884433866113249620102756858880983510077132164108dix601144023472731068232120263653936910454191111176217278873349155811695112571189151426545]

Cas de test en texte clair:

[[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]]

Veuillez demander plus si vous les résolvez tous. :-) Et merci beaucoup aux personnes qui m'ont aidé à affiner ce défi dans le bac à sable .


1 Un temps raisonnable: tout temps qui ne sape pas notre patience lors du test de votre solution. Notez que TIO n'exécute le code que pendant 60 secondes, tout laps de temps dépassant cette limite nous fera tester le code dans nos machines. Exemple: mon algorithme plutôt inefficace prend quelques millisecondes pour résoudre des matrices d'ordre 3x3 et 4x4, mais je viens de le tester avec une matrice 5x5 et il a fallu 317 secondes pour le résoudre (en plus de 5 millions de mouvements, très drôle si l'on considère que la matrice à résoudre a été brouillée uniquement 10 000 fois). J'ai essayé de réduire le nombre de mouvements à moins de 10K mais je me suis rendu après 30 minutes d'exécution du code.

Charlie
la source
1
Beau défi! Cependant, j'ai quelques demandes / questions: 1) Pourriez-vous fournir les cas de test dans un format plus convivial pour le copier-coller? (tel que pastebin) 2) Pourriez-vous fournir une définition plus précise de l'ordre limite de temps? 3) La matrice est-elle garantie carrée? (Les cas de test le suggèrent, mais pas la définition.)
Arnauld
@Arnauld 1) J'y suis. 2) Je ne voulais pas fixer de limite de temps, et personne n'a suggéré de limite pendant que le défi était dans le bac à sable. Si vous en avez besoin, considéreriez-vous 30 minutes comme une limite raisonnable? 3) Oui, les matrices de test sont celles indiquées, et elles seront toutes carrées si d'autres sont nécessaires.
Charlie
Il existe un algorithme O (taille d'entrée) (relativement facile à implémenter) pour ce défi, il n'est donc pas aussi intéressant qu'il n'y paraît au premier abord.
user202729
@ user202729 Quelle serait la taille d'entrée dans votre O(input size)alors? Pour une matrice 5x5, ce serait O(25)? Cela semble être extrêmement rapide, donc je serais très intéressé de voir cet algorithme ou l'implémentation du vôtre. EDIT: Vous vous rendez compte que nous entrons la matrice «brouillée» et émettons les mouvements, non? Pas l'inverse.
Kevin Cruijssen
4
Je pense que c'est quelque chose comme cet algorithme
Kirill L.

Réponses:

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

Essayez-le en ligne!

Une tentative rapide pour implémenter l'algorithme de la solution de puzzle Torus à partir d'un article publié dans Algorithms 2012, 5, 18-29 que j'ai mentionné dans les commentaires.

Accepte la matrice d'entrée sous forme aplatie, comme une ligne de nombres séparés par des espaces.

Voici également un validateur en Python 2 . Il prend deux lignes en entrée: la matrice brouillée d'origine sous la même forme que le code principal et la séquence de mouvements proposée. La sortie du validateur est la matrice résultant de l'application de ces mouvements.

Explication

Dans la première partie de l'algorithme, nous ordonnons toutes les lignes sauf la dernière.

Pour ce faire, nous effectuons une série de "rotations triangulaires" ( proc triangle) - les séquences de mouvements qui se traduisent par un échange de trois cellules seulement, et tout le reste restant inchangé. Nous prenons chaque cellule "de travail" consécutive avec des coordonnées[p,q], puis trouvez la cellule [s,t] qui contient actuellement le numéro qui doit aller à [p,q]et complétez le triangle rectangle en sélectionnant un troisième point [u,v] selon un modèle, comme le montre la figure 4 de l'article lié.

Dans la Fig.2, les auteurs présentent 8 modèles possibles et les séquences de mouvements correspondantes, mais dans mon code, tous les cas ont été couverts par seulement 5 modèles, de sorte que non. 1, 5 et 6 ne sont pas utilisés.

Dans la deuxième partie, la dernière ligne, à l'exception des deux derniers éléments, est ordonnée en effectuant "trois rotations d'éléments" sur une ligne ( proc line), qui consistent en deux rotations triangulaires chacune (voir la figure 3 de l'article).

Nous sélectionnons notre cellule de travail actuelle [p,q] comme point gauche, cellule contenant la valeur cible [s,t] comme point central, et [s,t+1]comme le bon point. Ce mouvement en direction ouest est nomméTWdans l'article, tout comme mon processus de formation de chaîne pour cela. Sit est déjà la dernière colonne, de sorte que t+1 n'existe pas, on prend [s,t-1] comme troisième point, et modifiez l'action en conséquence: deux rotations de triangle sont effectuées par les motifs 7 et 8 (au lieu de 7 et 1 dans l'original TW séquence).

Enfin, si nest étrange, les deux éléments restants doivent être déjà en place, car nous sommes garantis qu'une solution existe. Sin est pair, et les deux éléments restants ne sont pas en place, alors selon le lemme 1 (page 22), ils peuvent être échangés par une série de TW se déplace, suivi d'un décalage vers l'est (=R). Étant donné que l'exemple fourni échange les deux premières entrées et que nous devons échanger les deux dernières, notre proc swapeffectueTW se déplace dans l'ordre inverse.

Dans le cas de bord de n=2 nous n'avons pas du tout besoin de toutes ces procédures complexes - si les derniers éléments de la ligne ne sont pas en place après la partie 1, un seul 1R le mouvement est suffisant pour rendre la matrice entièrement ordonnée.

Mise à jour: Ajout d'un nouveau proc rotationsqui inverse la direction des mouvements si cela se traduirait par moins d'étapes.

Kirill L.
la source
Impressionnant! Je vais ensuite créer d'autres cas de test. En attendant, je suis sûr que cette solution peut être optimisée, car il y a des morceaux comme 7L,7L,7L,7L,7D,7D,7D,7Dceux qui peuvent être réduits et 8R,8R,8R,8R,8R,8R,8Rceux qui peuvent être convertis 8L,8Lpour une matrice 9x9.
Charlie
J'ai essayé votre algorithme avec une matrice 100x100 et il le résout en moins de 4 secondes. Je ne m'attendais vraiment pas à ce que ce problème ait une solution à temps linéaire. J'essaierai d'écrire de meilleurs défis à l'avenir!
Charlie
Il aurait peut-être été préférable de poser ce défi avec une seule matrice fixe comme seul cas de test et de définir le critère gagnant comme étant juste la taille du chemin trouvé pour le résoudre, si j'avais su auparavant que ce problème avait un O (n ^ 2) solution. Envisageriez-vous de porter cette réponse à une nouvelle question avec un tel critère de gain?
Charlie
@Charlie Alors que j'essaierai encore d'affiner un peu la solution actuelle, je n'ai vraiment aucune idée de la façon de résoudre le problème global d'optimisation des chemins ...
Kirill L.
5

Python 2 , taille 100 en <30 secondes sur 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

Essayez-le en ligne! Link comprend trois petits cas de test avec sortie de déplacement complet, plus un test silencieux de 100x100 pour montrer que le code fonctionne (la sortie de déplacement dépasserait les limites de TIO). Explication: Le code tente d'effectuer un tri par insertion sur le tableau, en le construisant dans l'ordre croissant au fur et à mesure. Pour toutes les lignes sauf la dernière ligne, il existe un certain nombre de cas:

  • L'élément est dans la bonne ligne, mais appartient à la colonne 0. Dans ce cas, il est simplement tourné jusqu'à ce qu'il atteigne la colonne 0.
  • L'élément est au bon endroit. Dans ce cas, rien ne se passe. (Cela est également vrai si l'élément appartient à la colonne 0, c'est juste que 0 rotation se produit dans ce cas.)
  • L'élément est dans la ligne du haut mais dans la mauvaise colonne. Dans ce cas, il est tourné vers le bas, puis horizontalement jusqu'à ce que l'élément se trouve dans la bonne colonne, puis à nouveau tourné vers le haut.
  • L'élément est dans la bonne ligne mais dans la mauvaise colonne. Dans ce cas, il est tourné vers le haut, puis la ligne est tournée vers sa colonne, puis elle est tournée vers le bas, puis la ligne est tournée vers l'arrière. (En fait, c'est une rotation du cas suivant.)
  • L'élément est dans la bonne colonne mais dans la mauvaise ligne. Dans ce cas, la ligne est tournée vers la droite, pour la réduire au dernier cas.
  • L'élément est dans la mauvaise ligne et la mauvaise colonne. Dans ce cas, la colonne correcte est tournée vers la mauvaise ligne (sautée pour la ligne du haut), cette ligne est ensuite tournée vers la colonne correcte et la colonne est ensuite tournée en arrière.

Les rotations ci-dessus sont effectuées dans la direction qui minimise le nombre de pas; un carré de taille 2 est toujours résolu à l'aide de mouvements vers la gauche et vers le haut, quelle que soit la description ci-dessus.

Avant que la rangée du bas ne soit terminée, elle est tournée pour minimiser la distance totale hors de sa place, mais aussi pour s'assurer que la parité de la rangée du bas est régulière, car elle ne peut pas être modifiée par la dernière partie de l'algorithme. S'il y a plus d'une rotation avec la même distance minimale, la rotation avec le plus petit nombre de mouvements est choisie.

L'algorithme de la ligne du bas repose sur une séquence de 7 opérations qui échange les éléments en trois colonnes. La séquence est appliquée à chacun des numéros restants de la rangée inférieure afin de les amener à leur tour à l'emplacement souhaité; si possible, l'élément de cet emplacement est déplacé vers son emplacement souhaité, mais si un échange direct est nécessaire, l'élément est simplement déplacé vers la colonne disponible la plus proche, ce qui, espérons-le, peut être corrigé la prochaine fois.

Neil
la source
Merci beaucoup pour votre réponse, Neil! Mais rappelez-vous, ce n'est pas un golf de code. Au lieu de la longueur du code, vous devez indiquer la plus grande taille N de la matrice NxN que vous avez résolue et la longueur de la liste des mouvements pour résoudre cette matrice.
Charlie
@ Charlie Eh bien, c'est 6, mais seulement parce que j'ai été trop paresseux pour coller dans une matrice plus grande. Bien que ce soit la force brute, il évolue linéairement avec la zone, il devrait donc être capable de grandes matrices.
Neil
En fait, le pire des cas pourrait être quadratique avec la surface.
Neil
1
Le lien @Charlie TIO résout désormais une matrice aléatoire 100x100.
Neil
1
@Charlie J'ai maintenant trouvé une optimisation majeure pour la ligne du bas, mais je pense que c'est le dernier changement que je vais apporter à cette réponse.
Neil