Rubik-sortowanie macierzy (aka torus puzzle)

16

Pomysł na to jest prosty: biorąc pod uwagę macierz liczb całkowitych, posortujmy je stosując ruchy w stylu Rubika. Oznacza to, że możesz wybrać pojedynczy wiersz lub kolumnę i obrócić jej elementy w dowolnym kierunku:

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

Tak więc, biorąc pod uwagę macierz liczb całkowitych o dowolnym wymiarze, posortuj jej elementy stosując tylko te transformacje w stylu Rubika. Matryca

[za11za12za13za14za21za22za23za24za31za32za33za34]

będą uważane za posortowane, jeśli jego elementy są zgodne z następującym ograniczeniem:

za11za12za13za14za21za22za23za24za31za32za33za34

I / O

  • Wejście będzie macierzą dodatnich liczb całkowitych bez powtarzanych wartości.
  • Wyjściowe będą ruchy potrzebne do posortowania. Ponieważ nie jest to wyzwanie dla golfa kodowego i nie musisz się martwić o jego długość, proponowany format każdego ruchu to miejsce, w #[UDLR]którym #znajduje się numer wiersza lub kolumny do przesunięcia (indeksowany 0) i [UDLR]jest to pojedynczy znak zakres określający, czy ruch jest w górę / w dół (dla kolumn) czy w lewo / w prawo (dla wierszy). 1UOznaczałoby to zatem „przesunięcie pierwszej kolumny w górę”, ale 1Roznaczałoby „przesunięcie pierwszego rzędu w prawo”. Zmiany będą rozdzielone przecinkami więc rozwiązanie będzie wyrażona w następujący sposób: 1R,1U,0L,2D.

Punktacja

Próba posortowania macierzy w ten sposób może być kosztowna, ponieważ istnieje wiele możliwych kombinacji ruchów, a także istnieje wiele możliwych list ruchów, które mogą ją posortować, więc celem jest napisanie kodu, który sortuje N * N macierzy poniżej. Wynik będzie największym rozmiarem N, który można rozwiązać w rozsądnym czasie 1 bez błędów (im większy rozmiar rozwiązanej macierzy, tym lepiej). W przypadku remisu rozstrzygającym będzie liczba ruchów na znalezionej ścieżce (im krótsza ścieżka, tym lepiej).

Przykład: jeśli użytkownik A znajdzie rozwiązanie dla N = 5, a B znajdzie rozwiązanie dla N = 6, B wygrywa niezależnie od długości obu ścieżek. Jeśli oboje znajdą rozwiązania dla N = 6, ale rozwiązanie znalezione przez A ma 50 kroków, a rozwiązanie B ma 60 kroków, A wygrywa.

Zachęcamy do wyjaśnienia, w jaki sposób działa Twój kod i opublikuj znalezione rozwiązania, abyśmy mogli je przetestować . Możesz użyć Pastebin lub podobnych narzędzi, jeśli rozwiązania są zbyt duże. Doceniony zostanie również szacunkowy czas poświęcony przez kod na znalezienie rozwiązań.

Przypadki testowe

Utworzono następujące macierze ( łącze Pastebin dla wersji bardziej wklejalnej), zaczynając od już posortowanych macierzy, mieszając je losowymi ruchami w stylu Rubika o wielkości 10K:

[856111013)1513]
[21101216176221485192613243)1]
[113816594021262211241439283219373)10301736734]
[34214022354118333130124319113924282344136538451417916132683)476254]
[20361711550187267341032355424396306139284154272357048132512465863523784533146859655673606422]
[85565275894441682715879132373973676419997846164221631004172131197309328403365070258058960845496172943342335776182482943866]
[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
źródło
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 Jaki byłby Twój rozmiar wejściowy O(input size)? W przypadku matrycy 5x5 O(25)? Wydaje się to niezwykle szybkie, więc bardzo chciałbym zobaczyć ten algorytm lub jego implementację. EDYCJA: Zdajesz sobie sprawę, że wprowadzamy matrycę „zakodowaną” i wysyłamy ruchy, prawda? Nie na odwrót.
Kevin Cruijssen
4
Wydaje mi się, że jest to taki algorytm
Kirill L.

Odpowiedzi:

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

Wypróbuj online!

Szybka próba zaimplementowania algorytmu rozwiązania łamigłówki Torus z artykułu opublikowanego w Algorytmach 2012, 5, 18–29, o którym wspomniałem w komentarzach.

Akceptuje macierz wejściową w spłaszczonej formie, jako linię liczb rozdzielanych spacjami.

Tutaj także znajduje się walidator w Python 2 . Dane wejściowe wymagają dwóch wierszy: oryginalnej zaszyfrowanej matrycy w tej samej formie co kod główny i proponowanej sekwencji ruchów. Wyjściem walidatora jest macierz wynikająca z zastosowania tych ruchów.

Wyjaśnienie

W pierwszej części algorytmu porządkujemy wszystkie wiersze z wyjątkiem ostatniego.

Robimy to, wykonując serię „rotacji trójkątów” ( proc triangle) - sekwencje ruchów, w wyniku których tylko trzy komórki zamieniają się miejscami, a cała reszta pozostaje niezmieniona. Bierzemy każdą kolejną „działającą” komórkę ze współrzędnymi[p,q], a następnie znajdź komórkę [s,t] która obecnie zawiera numer, na który należy przejść [p,q]i ukończ właściwy trójkąt, wybierając trzeci punkt [u,v] zgodnie z pewnym wzorem, jak pokazano na ryc. 4 połączonego artykułu.

Na ryc. 2 autorzy przedstawiają 8 możliwych wzorców i odpowiadające im sekwencje ruchów, ale w moim kodzie wszystkie przypadki zostały objęte jedynie 5 wzorami, więc nie. 1, 5 i 6 nie są używane.

W drugiej części ostatni rząd, z wyjątkiem dwóch ostatnich elementów, jest uporządkowany poprzez wykonanie „trzech rotacji elementów” na linii ( proc line), która składa się z dwóch rotacji trójkątów każdy (patrz ryc. 3 artykułu).

Wybieramy naszą obecną działającą komórkę [p,q] jako lewy punkt komórka zawierająca wartość docelową [s,t] jako punkt centralny, oraz [s,t+1]jako właściwy punkt. Ten ruch na zachód nazywa sięT.W.w artykule, podobnie jak mój proces formowania łańcucha w tym celu. Gdybyt jest już ostatnią kolumną, więc t+1 nie istnieje, bierzemy [s,t-1] jako trzeci punkt i odpowiednio zmodyfikuj akcję: dwa obroty trójkątów są wykonywane według wzorów 7 i 8 (zamiast 7 i 1 w oryginale T.W. sekwencja).

Wreszcie, jeśli njest dziwny, pozostałe dwa elementy muszą już być na miejscu, ponieważ gwarantujemy, że istnieje rozwiązanie. Gdybyn jest parzysty, a dwa pozostałe elementy nie są na swoim miejscu, więc zgodnie z Lematem 1 (strona 22) można je zamienić serią T.W. ruchy, a następnie jedna zmiana na wschód (=R). Ponieważ podany przykład zamienia pierwsze dwa wpisy, a my musimy zamienić ostatnie dwa, nasze proc swapwykonanieT.W. porusza się w odwrotnej kolejności.

W przypadku krawędzi n=2) w ogóle nie potrzebujemy tych wszystkich skomplikowanych procedur - jeśli elementy ostatniego rzędu nie są na miejscu po części 1, pojedynczym 1R ruch jest wystarczający, aby matryca była w pełni uporządkowana.

Aktualizacja: Dodano nowy, proc rotationsktóry odwraca kierunek ruchów, jeśli spowodowałoby to mniej kroków.

Kirill L.
źródło
Imponujący! W takim razie stworzę więcej przypadków testowych. Tymczasem jestem pewien, że to rozwiązanie można zoptymalizować, ponieważ istnieją fragmenty, które 7L,7L,7L,7L,7D,7D,7D,7Dmożna zmniejszyć, a 8R,8R,8R,8R,8R,8R,8Rnastępnie przekształcić 8L,8Lw matrycę 9x9.
Charlie,
Wypróbowałem twój algorytm z matrycą 100 x 100 i rozwiązuje go on w mniej niż 4 sekundy. Naprawdę nie spodziewałem się, że ten problem będzie miał rozwiązanie w czasie liniowym. W przyszłości postaram się pisać lepsze wyzwania!
Charlie,
Być może lepiej byłoby postawić to wyzwanie za pomocą pojedynczej, stałej matrycy jako jedynego przypadku testowego i ustawić kryterium wygranej jako wielkość znalezionej ścieżki do jego rozwiązania, gdybym wiedział wcześniej, że ten problem ma O (n ^ 2) rozwiązanie. Czy zastanowiłbyś się nad przeniesieniem tej odpowiedzi na nowe pytanie z takim kryterium wygranej?
Charlie
@Charlie Chociaż nadal będę próbował trochę dopracować obecne rozwiązanie, tak naprawdę nie mam pojęcia, jak rozwiązać ogólny problem optymalizacji ścieżki ...
Kirill L.
5

Python 2 , rozmiar 100 w <30 sekund na 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

Wypróbuj online! Link zawiera trzy małe przypadki testowe z pełnym wyjściem ruchu oraz plus cichy test 100 x 100, aby pokazać, że kod działa (wyjście ruchu przekroczyłoby granice TIO). Objaśnienie: Kod próbuje wykonać sortowanie wstawiania na tablicy, budując go w porządku rosnącym w miarę upływu czasu. Dla wszystkich wierszy z wyjątkiem ostatniego wiersza istnieje wiele przypadków:

  • Element znajduje się we właściwym wierszu, ale należy do kolumny 0. W takim przypadku jest on po prostu obracany, aż osiągnie kolumnę 0.
  • Element znajduje się we właściwym miejscu. W tym przypadku nic się nie dzieje. (Jest to również prawdą, jeśli element należy do kolumny 0, po prostu w tym przypadku ma miejsce 0 obrotów).
  • Element znajduje się w górnym rzędzie, ale w niewłaściwej kolumnie. W takim przypadku jest on obracany w dół, a następnie poziomo, aż element znajdzie się we właściwej kolumnie, a następnie ponownie obracany w górę.
  • Element znajduje się we właściwym wierszu, ale w niewłaściwej kolumnie. W takim przypadku jest on obracany w górę, następnie rząd jest obracany do swojej kolumny, następnie jest obracany w dół, a następnie rząd jest obracany z powrotem. (W rzeczywistości jest to rotacja następnego przypadku.)
  • Element znajduje się we właściwej kolumnie, ale w niewłaściwym wierszu. W takim przypadku wiersz zostanie obrócony w prawo, aby zredukować go do ostatniego przypadku.
  • Element znajduje się w niewłaściwym wierszu i niewłaściwej kolumnie. W takim przypadku poprawna kolumna jest obracana do niewłaściwego wiersza (pomijana dla górnego wiersza), wiersz ten jest następnie obracany do właściwej kolumny, a następnie kolumna jest obracana z powrotem.

Powyższe obroty są wykonywane w dowolnym kierunku, co minimalizuje liczbę kroków; kwadrat 2 zawsze rozwiązuje się za pomocą ruchów w lewo iw górę, niezależnie od powyższego opisu.

Przed zakończeniem dolnego rzędu jest on obracany, aby zminimalizować całkowitą odległość poza miejscem, ale także w celu zapewnienia, że ​​parzystość dolnego rzędu jest równa, ponieważ nie można go zmienić w końcowej części algorytmu. Jeśli istnieje więcej niż jeden obrót przy tej samej minimalnej odległości, wybierany jest obrót z najmniejszą liczbą ruchów.

Algorytm dla dolnego rzędu opiera się na 7-operacyjnej sekwencji, która wymienia elementy w trzech kolumnach. Sekwencja jest stosowana do każdej z pozostałych liczb dolnego rzędu po kolei, aby doprowadzić je do pożądanego miejsca; jeśli to możliwe, element w tej lokalizacji jest przenoszony do pożądanej lokalizacji, ale jeśli potrzebna jest prosta zamiana, element jest po prostu przenoszony do najbliższej dostępnej kolumny, co ma nadzieję, że można go naprawić następnym razem.

Neil
źródło
Dziękuję bardzo za odpowiedź, Neil! Pamiętaj jednak, że to nie jest golf golfowy. Zamiast długości kodu powinieneś wskazać największy rozmiar N rozwiązywanej macierzy NxN oraz długość listy ruchów rozwiązujących tę macierz.
Charlie,
@Charlie Cóż, to 6, ale tylko dlatego, że byłem zbyt leniwy, aby wkleić do większej matrycy. Chociaż jest to brutalna siła, skaluje się liniowo wraz z obszarem, więc powinna być zdolna do dużych matryc.
Neil
W rzeczywistości najgorszy przypadek może być kwadratowy z obszarem.
Neil
1
@Charlie TIO link rozwiązuje teraz losową macierz 100 x 100.
Neil
1
@Charlie Wymyśliłem teraz główną optymalizację dla dolnego rzędu, ale myślę, że to ostatnia zmiana, którą zamierzam wprowadzić w tej odpowiedzi.
Neil