Rubik-Sortierung einer Matrix (auch bekannt als das Torus-Puzzle)

16

Die Idee für diese ist einfach: Bei einer gegebenen Matrix von Ganzzahlen sortieren wir sie durch Anwenden von Bewegungen im Rubik-Stil. Dies bedeutet, dass Sie eine einzelne Zeile oder Spalte auswählen und ihre Elemente in eine beliebige Richtung drehen können:

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

Sortieren Sie also bei einer Matrix von Ganzzahlen beliebiger Dimension die Elemente, indem Sie nur diese Transformationen im Rubik-Stil anwenden. Eine Matrix

[ein11ein12ein13ein14ein21ein22ein23ein24ein31ein32ein33ein34]

gilt als sortiert, wenn seine Elemente der folgenden Einschränkung entsprechen:

ein11ein12ein13ein14ein21ein22ein23ein24ein31ein32ein33ein34

I / O

  • Die Eingabe ist eine Matrix aus positiven ganzen Zahlen ohne wiederholte Werte.
  • Das Ergebnis sind die Bewegungen, die zum Sortieren erforderlich sind. Da dies kein Code Golf Herausforderung ist und Sie nicht Sorge über seine Länge benötigt, ist das vorgeschlagene Format für jede Bewegung , #[UDLR]wo #die Nummer der Zeile oder Spalte zu bewegen (0-indiziert) und [UDLR]ist ein einzelne Zeichen, dass Bereich, der angibt, ob die Bewegung nach oben / unten (für Spalten) oder links / rechts (für Zeilen) erfolgt. Dies 1Uwürde bedeuten, dass "die 1. Spalte nach oben verschoben wird", aber 1R"die 1. Zeile nach rechts verschoben wird". Bewegungen werden durch Komma getrennt sein, so wird eine Lösung wie folgt ausgedrückt werden: 1R,1U,0L,2D.

Wertung

Der Versuch, eine Matrix auf diese Weise zu sortieren, kann kostspielig sein, da es viele mögliche Kombinationen von Zügen gibt und es auch viele mögliche Listen von Zügen gibt, die sie sortieren können. Daher besteht das Ziel darin, einen Code zu schreiben, der das N * sortiert. N Matrizen unten. Die Punktzahl ist die größte Größe N, die Sie in einem angemessenen Zeitraum 1 ohne Fehler lösen können (je größer die Größe der gelösten Matrix, desto besser). Im Falle eines Gleichstandes ist der Gleichstand die Anzahl der Bewegungen auf Ihrem gefundenen Weg (je kürzer der Weg, desto besser).

Beispiel: Wenn ein Benutzer A eine Lösung für N = 5 und B eine Lösung für N = 6 findet, gewinnt B unabhängig von der Länge beider Pfade. Wenn beide Lösungen für N = 6 finden, aber die von A gefundene Lösung 50 Schritte und die von B 60 Schritte hat, gewinnt A.

Erklärungen zur Funktionsweise Ihres Codes werden dringend empfohlen. Veröffentlichen Sie die gefundenen Lösungen, damit wir sie testen können . Sie können Pastebin oder ähnliche Tools verwenden, wenn die Lösungen zu groß sind. Außerdem wird eine Schätzung der Zeit, die Ihr Code benötigt, um Ihre Lösungen zu finden, geschätzt.

Testfälle

Die folgenden Matrizen ( Pastebin-Link für eine kopierfähigere Version) wurden ausgehend von bereits sortierten Matrizen erstellt, indem sie mit 10K zufälligen Bewegungen im Rubik-Stil verschlüsselt wurden:

[8561110131513]
[211012161762214851926132431]
[11381659402126221124143928321937310301736734]
[34214022354118333130124319113924282344136538451417916132683476254]
[20361711550187267341032355424396306139284154272357048132512465863523784533146859655673606422]
[85565275894441682715879132373973676419997846164221631004172131197309328403365070258058960845496172943342335776182482943866]
[567990617112211031551144284851306188443386611324962010275685888098351007713216410810601144023472731068232120263653936910454191111176217278873349155811695112571189151426545]

Klartext-Testfälle:

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

Bitte fragen Sie nach mehr, wenn Sie sie alle lösen. :-) Und vielen Dank an die Leute, die mir geholfen haben, diese Herausforderung im Sandkasten zu verfeinern .


1 Eine angemessene Zeitspanne: Jede Zeitspanne, die unsere Geduld beim Testen Ihrer Lösung nicht beeinträchtigt. Beachten Sie, dass TIO den Code nur 60 Sekunden lang ausführt. Wenn diese Zeit überschritten wird, können wir den Code auf unseren Computern testen. Beispiel: Mein ineffizienter Algorithmus benötigt ein paar Millisekunden, um Matrizen der Größenordnung 3x3 und 4x4 zu lösen, aber ich habe ihn gerade mit einer 5x5-Matrix getestet und es dauerte 317 Sekunden, um ihn zu lösen (in über 5 Millionen Bewegungen, sehr lustig, wenn wir das betrachten Die zu lösende Matrix wurde nur 10K-mal verschlüsselt . Ich habe versucht, die Anzahl der Bewegungen auf weniger als 10 KB zu reduzieren, aber ich habe mich nach 30 Minuten ergeben, nachdem ich den Code ausgeführt hatte.

Charlie
quelle
1
Schöne Herausforderung! Ich habe jedoch ein paar Anfragen / Fragen: 1) Können Sie die Testfälle in einem kopierfreundlicheren Format bereitstellen? (z. B. Pastebin) 2) Können Sie die Reihenfolge der Fristen genauer definieren? 3) Ist die Matrix garantiert quadratisch? (Die Testfälle legen dies nahe, aber die Definition nicht.)
Arnauld
@ Arnauld 1) Ich bin dabei. 2) Ich wollte kein Zeitlimit festlegen, und niemand schlug ein Limit vor, während sich die Herausforderung im Sandkasten befand. Wenn Sie eine benötigen, halten Sie 30 Minuten für ein angemessenes Limit? 3) Ja, die Testmatrizen sind die gezeigten und sie sind alle quadratisch, wenn mehr benötigt werden.
Charlie
Es gibt einen (relativ einfach zu implementierenden) O-Algorithmus (Eingabegröße) für diese Herausforderung, daher ist er nicht so interessant, wie es zunächst aussehen mag.
user202729
@ user202729 Wie groß wäre dann deine Eingabe O(input size)? Für eine 5x5 Matrix wäre das O(25)? Das scheint extrem schnell zu sein, also wäre ich sehr interessiert, diesen Algorithmus oder Ihre Implementierung zu sehen. EDIT: Sie wissen, dass wir die 'verschlüsselte' Matrix eingeben und die Bewegungen ausgeben, richtig? Nicht umgekehrt.
Kevin Cruijssen
4
Ich denke, es ist so etwas wie dieser Algorithmus
Kirill L.

Antworten:

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

Probieren Sie es online!

Ein kurzer Versuch, den Algorithmus der Torus-Rätsellösung aus einem Artikel in Algorithms 2012, 5, 18-29 zu implementieren, den ich in den Kommentaren erwähnt habe.

Akzeptiert die Eingabematrix in abgeflachter Form als Zeile mit durch Leerzeichen getrennten Zahlen.

Hier ist auch ein Validator in Python 2 . Es werden zwei Zeilen als Eingabe verwendet: die ursprüngliche verwürfelte Matrix in derselben Form wie der Hauptcode und die vorgeschlagene Bewegungssequenz. Die Ausgabe des Validators ist die Matrix, die sich aus der Anwendung dieser Züge ergibt.

Erläuterung

Im ersten Teil des Algorithmus ordnen wir alle Zeilen mit Ausnahme der letzten an.

proc triangle[p,q][s,t][p,q][u,v]

In Abb. 2 präsentieren die Autoren 8 mögliche Muster und die entsprechenden Abfolgen von Zügen, aber in meinem Code wurden tatsächlich alle Fälle von nur 5 Mustern abgedeckt, sodass Nr. 1, 5 und 6 werden nicht verwendet.

Im zweiten Teil wird die letzte Reihe mit Ausnahme der beiden letzten Elemente durch Ausführen von " proc lineDreieckdrehungen " auf einer Linie ( ) angeordnet, die jeweils aus zwei Dreieckdrehungen besteht (siehe Abb. 3 des Artikels).

[p,q][s,t][s,t+1]TWtt+1[s,t-1]TW

nnTW=Rproc swapTW

n=21R

Update: Neu hinzugefügt proc rotations, wodurch die Bewegungsrichtung umgekehrt wird, wenn dies zu weniger Schritten führen würde.

Kirill L.
quelle
Beeindruckend! Dann erstelle ich noch ein paar Testfälle. In der Zwischenzeit bin ich sicher, dass diese Lösung optimiert werden kann, da es Teile 7L,7L,7L,7L,7D,7D,7D,7Dgibt, die reduziert und 8R,8R,8R,8R,8R,8R,8Rdann 8L,8Lfür eine 9x9-Matrix konvertiert werden können.
Charlie
Ich habe Ihren Algorithmus mit einer 100x100-Matrix ausprobiert und er löst ihn in weniger als 4 Sekunden. Ich habe wirklich nicht damit gerechnet, dass dieses Problem eine zeitlineare Lösung hat. Ich werde versuchen, in Zukunft bessere Herausforderungen zu schreiben!
Charlie
Vielleicht wäre es besser gewesen, diese Herausforderung mit einer einzigen festen Matrix als einzigem Testfall zu stellen und das Gewinnkriterium auf die Größe des gefundenen Pfades zu setzen, um sie zu lösen, hätte ich vorher gewusst, dass dieses Problem ein O hat (n ^ 2) Lösung. Würden Sie in Betracht ziehen, diese Antwort auf eine neue Frage mit einem solchen Gewinnkriterium zu portieren?
Charlie
@Charlie Ich werde zwar immer noch versuchen, die aktuelle Lösung ein wenig zu verfeinern, aber ich habe wirklich keine Ahnung, wie ich das allgemeine Problem der Pfadoptimierung angehen soll ...
Kirill L.
5

Python 2 , Größe 100 in <30 Sekunden bei 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

Probieren Sie es online! Link enthält drei kleine Testfälle mit voller Bewegungsausgabe sowie einen unbeaufsichtigten Test von 100x100, um zu zeigen, dass der Code funktioniert (die Bewegungsausgabe würde die TIO-Grenzwerte überschreiten). Erläuterung: Der Code versucht, eine Einfügesortierung für das Array durchzuführen und baut sie dabei in aufsteigender Reihenfolge auf. Für alle Zeilen mit Ausnahme der letzten Zeile gibt es eine Reihe von Fällen:

  • Das Element befindet sich in der richtigen Zeile, gehört jedoch zu Spalte 0. In diesem Fall wird es einfach gedreht, bis es Spalte 0 erreicht.
  • Das Element befindet sich an der richtigen Stelle. In diesem Fall passiert nichts. (Dies gilt auch, wenn das Element zu Spalte 0 gehört. In diesem Fall werden nur 0-Umdrehungen ausgeführt.)
  • Das Element befindet sich in der obersten Zeile, aber in der falschen Spalte. In diesem Fall wird es nach unten und dann horizontal gedreht, bis sich das Element in der richtigen Spalte befindet, und dann wieder nach oben gedreht.
  • Das Element befindet sich in der richtigen Zeile, aber in der falschen Spalte. In diesem Fall wird es nach oben gedreht, dann wird die Zeile zu ihrer Spalte gedreht, dann wird es nach unten gedreht, dann wird die Zeile zurückgedreht. (Tatsächlich ist dies eine Rotation des nächsten Falls.)
  • Das Element befindet sich in der richtigen Spalte, aber in der falschen Zeile. In diesem Fall wird die Zeile nach rechts gedreht, um sie auf den letzten Fall zu reduzieren.
  • Das Element befindet sich in der falschen Zeile und in der falschen Spalte. In diesem Fall wird die richtige Spalte in die falsche Zeile gedreht (für die obere Zeile übersprungen), diese Zeile wird dann in die richtige Spalte gedreht und die Spalte wird dann zurückgedreht.

Die obigen Drehungen werden in welcher Richtung auch immer durchgeführt, um die Anzahl der Schritte zu minimieren; Ein Quadrat der Größe 2 wird unabhängig von der obigen Beschreibung immer mit Links- und Aufwärtsbewegungen gelöst.

Bevor die untere Reihe fertiggestellt ist, wird sie gedreht, um die Gesamtentfernung zu minimieren, aber auch um sicherzustellen, dass die Parität der unteren Reihe gleichmäßig ist, da sie durch den letzten Teil des Algorithmus nicht geändert werden kann. Gibt es mehr als eine Umdrehung mit derselben Mindestentfernung, wird die Umdrehung mit der geringsten Anzahl von Bewegungen ausgewählt.

Der Algorithmus für die unterste Zeile basiert auf einer Sequenz mit 7 Operationen, bei der die Elemente in drei Spalten ausgetauscht werden. Die Reihenfolge wird auf jede der verbleibenden Nummern der untersten Reihe angewendet, um sie an den gewünschten Ort zu bringen. Wenn möglich, wird das Element an dieser Position an die gewünschte Position verschoben. Wenn jedoch ein gerader Tausch erforderlich ist, wird das Element einfach in die nächste verfügbare Spalte verschoben, damit es beim nächsten Mal repariert werden kann.

Neil
quelle
Vielen Dank für Ihre Antwort, Neil! Aber denken Sie daran, dies ist kein Code-Golf. Anstelle der Länge des Codes sollten Sie die größte Größe N der NxN-Matrix angeben, die Sie gelöst haben, und die Länge der Liste der Bewegungen, um diese Matrix zu lösen.
Charlie
@ Charlie Nun, das ist 6, aber nur, weil ich zu faul war, um eine größere Matrix einzufügen. Obwohl es sich um rohe Gewalt handelt, skaliert es linear mit der Fläche, sodass es große Matrizen verarbeiten kann.
Neil
Im schlimmsten Fall ist die Fläche möglicherweise quadratisch.
Neil
1
@ Charlie TIO Link löst jetzt eine zufällige 100x100 Matrix.
Neil
1
@ Charlie Ich habe mir jetzt eine große Optimierung für die unterste Reihe ausgedacht, aber ich denke, das ist die letzte Änderung, die ich an dieser Antwort vornehmen werde.
Neil