Идея этого вызова кода проста: учитывая матрицу целых чисел, давайте разберем ее, применяя движения в стиле Рубика. Это означает, что вы можете выбрать одну строку или столбец и вращать его элементы в любом направлении:
[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)
Таким образом, учитывая матрицу целых чисел любого измерения, сортируйте ее элементы, применяя только эти преобразования в стиле Рубика. Матрица
будет считаться отсортированным, если его элементы соответствуют следующим ограничениям:
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 КБ:
Тестовые случаи в открытом тексте:
[[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 минут выполнения кода.
O(input size)
тогда? Для матрицы 5x5 это было быO(25)
? Это кажется очень быстрым, поэтому мне было бы очень интересно увидеть ваш алгоритм или его реализацию. РЕДАКТИРОВАТЬ: Вы понимаете, что мы вводим «скремблированную» матрицу и выводим движения, верно? А не наоборот.Ответы:
Nim
Попробуйте онлайн!
Быстрая попытка реализовать алгоритм решения головоломки Torus из статьи, опубликованной в Algorithms 2012, 5, 18-29, которую я упоминал в комментариях.
Принимает матрицу ввода в плоской форме, как строку чисел, разделенных пробелами.
Вот также валидатор в Python 2 . В качестве входных данных используются две строки: исходная скремблированная матрица в том же виде, что и основной код, и предлагаемая последовательность ходов. Вывод валидатора - это матрица, полученная в результате применения этих ходов.
объяснение
В первой части алгоритма мы упорядочиваем все строки, кроме последней.
Мы делаем это, выполняя серию «поворотов треугольника» ([ р , д] затем найдите клетку [ с , т ] который в настоящее время содержит номер, который должен идти [ р , д] и завершите прямоугольный треугольник, выбрав третью точку [ u , v ] согласно некоторому шаблону, как показано на фиг. 4 связанного изделия.
proc triangle
) - последовательности ходов, которые приводят только к обмену трех ячеек, а все остальные остаются неизменными. Берём каждую последовательную «рабочую» ячейку с координатамиНа рис. 2 авторы представляют 8 возможных шаблонов и соответствующие последовательности ходов, но в моем коде все случаи фактически покрыты только 5 шаблонами, так что нет. 1, 5 и 6 не используются.
Во второй части последний ряд, за исключением двух последних элементов, упорядочивается путем выполнения «поворота трех элементов» в строке (
proc line
), состоящей из двух поворотов треугольника в каждом (см. Рис. 3 статьи).Мы выбираем нашу текущую рабочую ячейку[ р , д] в качестве левой точки, ячейка, содержащая целевое значение [ с , т ] в качестве центральной точки, и [ s , t + 1 ] как правильная точка. Это западное движение называетсяTW в статье, и так моя процедура формирования строки для этого. ЕслиT уже последний столбец, так что т + 1 не существует, мы берем [ с , т - 1 ] в качестве третьей точки, и измените действие соответствующим образом: два поворота треугольника выполняются по шаблонам 7 и 8 (вместо 7 и 1 в оригинале TW последовательность).
Наконец, еслиN нечетно, остальные два элемента должны быть уже на месте, так как мы гарантируем, что решение существует. ЕслиN является четным, и два оставшихся элемента не на месте, то, согласно лемме 1 (стр. 22), они могут быть заменены рядом TW движется, а затем один сдвиг на восток (= R ). Поскольку предоставленные например свопы первые две записи, и нам нужно поменять местами два последних, наши TW движется в обратном порядке.
proc swap
выполняемоеВ крайнем случаеп = 2 нам вообще не нужны все эти сложные процедуры - если последние элементы строки не на месте после первой части, 1 р хода достаточно, чтобы сделать матрицу полностью упорядоченной.
Обновление: добавлено новое,
proc rotations
которое изменяет направление движения, если это приведет к меньшему количеству шагов.источник
7L,7L,7L,7L,7D,7D,7D,7D
которые можно уменьшить, а затем8R,8R,8R,8R,8R,8R,8R
преобразовать в8L,8L
матрицу 9x9.Python 2 , размер 100 за <30 секунд на TIO
Попробуйте онлайн! Линк включает в себя три небольших тестовых случая с полным выводом хода, а также бесшумный тест 100x100, чтобы показать, что код работает (вывод хода превысил бы пределы TIO). Объяснение: Код пытается выполнить сортировку вставки в массиве, создавая его в порядке возрастания. Для всех строк, кроме последней, существует ряд случаев:
Вышеуказанные повороты выполняются в любом направлении, минимизирующем количество шагов; квадрат размера 2 всегда решается с помощью движений влево и вверх, независимо от описания выше.
Перед завершением нижнего ряда его вращают, чтобы минимизировать общее расстояние не на своем месте, а также чтобы обеспечить четность нижнего ряда, поскольку он не может быть изменен последней частью алгоритма. Если имеется несколько поворотов с одинаковым минимальным расстоянием, выбирается вращение с наименьшим количеством ходов.
Алгоритм для нижнего ряда основан на последовательности из 7 операций, которая обменивает элементы в три столбца. Последовательность применяется к каждому из оставшихся номеров нижнего ряда, чтобы по очереди привести их в нужное место; если возможно, элемент в этом месте перемещается в желаемое место, но если требуется прямой обмен, элемент просто перемещается в ближайший доступный столбец, надеясь, что его можно будет исправить в следующий раз.
источник