Рубик-сортировка по матрице (она же головоломка тора)

16

Идея этого проста: учитывая матрицу целых чисел, давайте разберем ее, применяя движения в стиле Рубика. Это означает, что вы можете выбрать одну строку или столбец и вращать его элементы в любом направлении:

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

Таким образом, учитывая матрицу целых чисел любого измерения, сортируйте ее элементы, применяя только эти преобразования в стиле Рубика. Матрица

[a11a12a13a14a21a22a23a24a31a32a33a34]

будет считаться отсортированным, если его элементы соответствуют следующим ограничениям:

a11a12a13a14a21a22a23a24a31a32a33a34

I / O

  • На входе будет матрица натуральных чисел без повторяющихся значений.
  • Выходными данными будут движения, необходимые для его сортировки. Поскольку это не код гольф вызова и вам не нужно беспокоиться о его длине, предлагаемый формат для каждого движения , #[UDLR]где #это число строк или столбцов для перемещения (0 индексированных) и [UDLR]представляет собой один символ в том , что диапазон, который указывает, будет ли движение вверх / вниз (для столбцов) или влево / вправо (для строк). Таким образом, 1Uбудет означать «переместить 1-й столбец вверх», но 1Rбудет «переместить 1-й ряд вправо». Движение будет отделено запятой, поэтому решение будет выражаться следующим образом: 1R,1U,0L,2D.

счет

Попытка сортировки матрицы таким способом может быть дорогостоящей, поскольку существует множество возможных комбинаций ходов, а также существует множество возможных списков ходов, которые могут ее отсортировать, поэтому цель состоит в том, чтобы написать некоторый код, который сортирует N * N матриц ниже. Счет будет наибольшим размером N, который вы сможете решить за приемлемое количество времени 1 без ошибок (чем больше размер решаемой матрицы, тем лучше). В случае ничьей, прерывателем будет количество движений на найденном пути (чем короче путь, тем лучше).

Пример: если пользователь A находит решение для N = 5, а B находит решение для N = 6, B выигрывает независимо от длины обоих путей. Если они оба находят решения для N = 6, но решение, найденное A, имеет 50 шагов, а решение B имеет 60 шагов, A выигрывает.

Мы настоятельно рекомендуем объяснить, как работает ваш код, и, пожалуйста, опубликуйте найденные решения, чтобы мы могли их протестировать . Вы можете использовать Pastebin или аналогичные инструменты, если решения слишком велики. Также будет оценена оценка времени, потраченного вашим кодом на поиск ваших решений.

Контрольные примеры

Следующие матрицы ( ссылка Pastebin для более копируемой версии) были созданы, начиная с уже отсортированных матриц, путем скремблирования их случайными движениями в стиле Рубика по 10 КБ:

[8561110131513]
[211012161762214851926132431]
[11381659402126221124143928321937310301736734]
[3421402235411833+3130124319113924282344136538451417916132683476254]
[20361711550187267341032355424396306139284154272357048132512465863523784533146859655673606422]
[85565275894441682715879132373973676419997846164221631004172131197309328403365070258058960845496172943342335776182482943866]
[567990617112211031551144284851306188443386611324962010275685888098351007713216410810601144023472731068232120263653936910454191111176217278873349155811695112571189151426545]

Тестовые случаи в открытом тексте:

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

Пожалуйста, попросите больше, если вы решите их все. :-) И большое спасибо людям, которые помогли мне решить эту проблему, находясь в песочнице .


1 Разумное количество времени: любое время, которое не подрывает наше терпение при тестировании вашего решения. Обратите внимание, что TIO запускает код только в течение 60 секунд, любое количество времени, превышающее это ограничение, заставит нас протестировать код на наших машинах. Пример: мой довольно неэффективный алгоритм занимает несколько миллисекунд для решения матриц порядка 3x3 и 4x4, но я только что протестировал его с матрицей 5x5, и для его решения потребовалось 317 секунд (более 5 миллионов движений, очень забавно, если учесть, что матрица для решения была взломана только 10K раз). Я пытался уменьшить количество движений до 10K, но я сдался после 30 минут выполнения кода.

Чарли
источник
1
Отличный вызов! Однако у меня есть несколько запросов / вопросов: 1) Не могли бы вы предоставить контрольные примеры в более удобном для копирования формате? (например, pastebin) 2) Не могли бы вы дать более точное определение порядка ограничения времени? 3) Матрица гарантированно будет квадратной? (Тестовые случаи предполагают это, но определение не дает.)
Арно
@Arnauld 1) Я нахожусь на этом. 2) Я не хотел устанавливать ограничение по времени, и никто не предлагал никаких ограничений, пока задача находилась в песочнице. Если вам это нужно, считаете ли вы 30 минут разумным ограничением? 3) Да, показаны тестовые матрицы, и все они будут квадратными, если потребуется больше.
Чарли
Для этой задачи существует (относительно простой в реализации) алгоритм O (входной размер), поэтому он не так интересен, как может показаться на первый взгляд.
user202729
@ user202729 Каким будет размер ввода у вас O(input size)тогда? Для матрицы 5x5 это было бы O(25)? Это кажется очень быстрым, поэтому мне было бы очень интересно увидеть ваш алгоритм или его реализацию. РЕДАКТИРОВАТЬ: Вы понимаете, что мы вводим «скремблированную» матрицу и выводим движения, верно? А не наоборот.
Кевин Круйссен
4
Я думаю, что-то вроде этого алгоритма
Кирилл Л.

Ответы:

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

Попробуйте онлайн!

Быстрая попытка реализовать алгоритм решения головоломки Torus из статьи, опубликованной в Algorithms 2012, 5, 18-29, которую я упоминал в комментариях.

Принимает матрицу ввода в плоской форме, как строку чисел, разделенных пробелами.

Вот также валидатор в Python 2 . В качестве входных данных используются две строки: исходная скремблированная матрица в том же виде, что и основной код, и предлагаемая последовательность ходов. Вывод валидатора - это матрица, полученная в результате применения этих ходов.

объяснение

В первой части алгоритма мы упорядочиваем все строки, кроме последней.

Мы делаем это, выполняя серию «поворотов треугольника» ( proc triangle) - последовательности ходов, которые приводят только к обмену трех ячеек, а все остальные остаются неизменными. Берём каждую последовательную «рабочую» ячейку с координатами[п,Q]затем найдите клетку [s,T] который в настоящее время содержит номер, который должен идти [п,Q]и завершите прямоугольный треугольник, выбрав третью точку [U,v] согласно некоторому шаблону, как показано на фиг. 4 связанного изделия.

На рис. 2 авторы представляют 8 возможных шаблонов и соответствующие последовательности ходов, но в моем коде все случаи фактически покрыты только 5 шаблонами, так что нет. 1, 5 и 6 не используются.

Во второй части последний ряд, за исключением двух последних элементов, упорядочивается путем выполнения «поворота трех элементов» в строке ( proc line), состоящей из двух поворотов треугольника в каждом (см. Рис. 3 статьи).

Мы выбираем нашу текущую рабочую ячейку [п,Q] в качестве левой точки, ячейка, содержащая целевое значение [s,T] в качестве центральной точки, и [s,T+1]как правильная точка. Это западное движение называетсяTWв статье, и так моя процедура формирования строки для этого. ЕслиT уже последний столбец, так что T+1 не существует, мы берем [s,T-1] в качестве третьей точки, и измените действие соответствующим образом: два поворота треугольника выполняются по шаблонам 7 и 8 (вместо 7 и 1 в оригинале TW последовательность).

Наконец, если Nнечетно, остальные два элемента должны быть уже на месте, так как мы гарантируем, что решение существует. ЕслиN является четным, и два оставшихся элемента не на месте, то, согласно лемме 1 (стр. 22), они могут быть заменены рядом TW движется, а затем один сдвиг на восток (знак равнор). Поскольку предоставленные например свопы первые две записи, и нам нужно поменять местами два последних, наши proc swapвыполняемоеTW движется в обратном порядке.

В крайнем случае Nзнак равно2 нам вообще не нужны все эти сложные процедуры - если последние элементы строки не на месте после первой части, 1р хода достаточно, чтобы сделать матрицу полностью упорядоченной.

Обновление: добавлено новое, proc rotationsкоторое изменяет направление движения, если это приведет к меньшему количеству шагов.

Кирилл Л.
источник
Впечатляет! Я создам еще несколько тестов. Между тем, я уверен, что это решение можно оптимизировать, так как есть такие фрагменты, 7L,7L,7L,7L,7D,7D,7D,7Dкоторые можно уменьшить, а затем 8R,8R,8R,8R,8R,8R,8Rпреобразовать в 8L,8Lматрицу 9x9.
Чарли
Я попробовал ваш алгоритм с матрицей 100x100, и он решает его менее чем за 4 секунды. Я действительно не ожидал, что у этой проблемы будет решение с линейным временем. Я постараюсь написать лучшие задачи в будущем!
Чарли
Возможно, было бы лучше представить эту проблему с единственной фиксированной матрицей в качестве единственного контрольного примера и установить критерий выигрыша равным размеру найденного пути для ее решения, если бы я знал, что эта проблема имеет O (п ^ 2) решение. Не могли бы вы перенести этот ответ на новый вопрос с таким критерием победы?
Чарли
@Charlie Хотя я все еще попытаюсь немного усовершенствовать текущее решение, я действительно понятия не имею, как решить общую проблему оптимизации пути ...
Кирилл Л.
5

Python 2 , размер 100 за <30 секунд на 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

Попробуйте онлайн! Линк включает в себя три небольших тестовых случая с полным выводом хода, а также бесшумный тест 100x100, чтобы показать, что код работает (вывод хода превысил бы пределы TIO). Объяснение: Код пытается выполнить сортировку вставки в массиве, создавая его в порядке возрастания. Для всех строк, кроме последней, существует ряд случаев:

  • Элемент находится в правильной строке, но принадлежит столбцу 0. В этом случае он просто поворачивается, пока не достигнет столбца 0.
  • Элемент находится в правильном месте. В этом случае ничего не происходит. (Это также верно, если элемент принадлежит столбцу 0, просто в этом случае происходит вращение на 0).
  • Элемент находится в верхней строке, но не в том столбце. В этом случае он поворачивается вниз, затем горизонтально, пока элемент не окажется в правильном столбце, а затем снова поворачивается вверх.
  • Элемент находится в правильной строке, но в неправильном столбце. В этом случае он поворачивается вверх, затем ряд поворачивается к своему столбцу, затем он поворачивается вниз, а затем ряд поворачивается назад. (По сути, это поворот следующего дела.)
  • Элемент находится в правильном столбце, но в неправильной строке. В этом случае ряд поворачивается вправо, чтобы уменьшить его до последнего случая.
  • Элемент находится в неправильной строке и неправильном столбце. В этом случае правильный столбец поворачивается на неправильную строку (пропускается для верхней строки), затем эта строка поворачивается на правильный столбец, а затем столбец поворачивается обратно.

Вышеуказанные повороты выполняются в любом направлении, минимизирующем количество шагов; квадрат размера 2 всегда решается с помощью движений влево и вверх, независимо от описания выше.

Перед завершением нижнего ряда его вращают, чтобы минимизировать общее расстояние не на своем месте, а также чтобы обеспечить четность нижнего ряда, поскольку он не может быть изменен последней частью алгоритма. Если имеется несколько поворотов с одинаковым минимальным расстоянием, выбирается вращение с наименьшим количеством ходов.

Алгоритм для нижнего ряда основан на последовательности из 7 операций, которая обменивает элементы в три столбца. Последовательность применяется к каждому из оставшихся номеров нижнего ряда, чтобы по очереди привести их в нужное место; если возможно, элемент в этом месте перемещается в желаемое место, но если требуется прямой обмен, элемент просто перемещается в ближайший доступный столбец, надеясь, что его можно будет исправить в следующий раз.

Нил
источник
Большое спасибо за ответ, Нил! Но помните, это не код гольф. Вместо длины кода вы должны указать наибольший размер N матрицы NxN, которую вы решили, и длину списка движений для решения этой матрицы.
Чарли
@Charlie Ну, это 6, но только потому, что мне было лень вставлять матрицу большего размера. Хотя это грубая сила, она линейно масштабируется по площади, поэтому она должна быть способна работать с большими матрицами.
Нил
На самом деле, наихудший случай может быть квадратичным с площадью.
Нил
1
Ссылка @Charlie TIO теперь решает случайную матрицу 100x100.
Нил,
1
@Charlie Теперь я разработал основную оптимизацию для нижней строки, но я думаю, что это последнее изменение, которое я собираюсь внести в этот ответ.
Нил