У наших друзей в Puzzling.SE была опубликована следующая загадка: всегда ли эта хроматическая головоломка разрешима? Эдгар Г. Вы можете сыграть здесь .
Объяснение головоломки
Учитывая m x n
сетку с плитками трех разных цветов, вы можете выбрать любые две соседние плитки , если их цвета разные . Эти две плитки затем преобразуются в третий цвет, то есть в один цвет, не представленный этими двумя плитками. Загадка решается, если все плитки имеют одинаковый цвет . По-видимому, можно доказать, что эта головоломка всегда разрешима, если ни одна из них m
не n
делится на 3.
Конечно, это требует алгоритма решения. Вы напишите функцию или программу, которая решает эту головоломку. Обратите внимание, что функции с «побочными эффектами» (т. Е. Вывод включен, stdout
а не в каком-то неудобном возвращаемом значении типа данных) явно разрешены.
Ввод, вывод
Вход будет m x n
матрица , состоящая из целых чисел 1
, 2
и 3
(или 0
, 1
, 2
если это удобно). Вы можете принять этот вход в любом нормальном формате. Как m
и n
являются >1
и не делится на 3. Можно считать загадку не решена
Затем вы решите головоломку. Это будет включать в себя повторный выбор двух смежных плиток для «преобразования» (см. Выше). Вы будете выводить две координаты этих тайлов для каждого шага, который предпринял ваш алгоритм решения. Это также может быть в любом нормальном формате вывода. Вы можете выбирать между индексированием ваших координат на основе 0 и 1, а также в первую очередь индексировать строки или столбцы. Пожалуйста, укажите это в своем ответе, однако.
Ваш алгоритм должен работать в течение разумного времени в исходном случае 8x8. Грубое форсирование полностью запрещено, т. Е. Ваш алгоритм должен выполняться O(k^[m*(n-1)+(m-1)*n])
с k
количеством шагов, необходимых для решения. Однако решение не обязательно должно быть оптимальным. Доказательство, приведенное в связанном вопросе, может дать вам представление о том, как это сделать (например, сначала сделать все столбцы, используя только вертикально смежные плитки, а затем сделать все строки)
Контрольные примеры
В этих тестовых случаях координаты основаны на 1, и строки индексируются первыми (например, MATLAB / Octave и, возможно, многие другие).
Input:
[1 2]
Output: (result: all 3's)
[1 1],[1,2]
Input:
[ 1 2
3 1 ]
Output: (result: all 1's)
[1 1],[2 1] (turn left column into 2's)
[2 1],[2 2] (turn right column into 3's)
[1 1],[1 2] (turn top row into 1's)
[2 1],[2 2] (turn bottom row into 1's)
Input:
[1 2 3 2
3 2 1 1]
Output: (result: all 3's)
[1 1],[1 2]
[1 3],[1 4]
[1 2],[1 3]
[1 1],[1 2]
[1 2],[1 3]
[1 1],[1 2]
[1 3],[1 4]
[2 1],[2 2]
[1 1],[2 1]
[1 2],[2 2]
[1 3],[2 3]
[1 4],[2 4]
При желании я могу опубликовать пастбин более крупных тестовых случаев, но я думаю, что этого должно быть достаточно.
источник
Ответы:
Рубин, 266 байт
Более или менее всего лишь порт решения Octave, за исключением того, что сначала решаются строки, а не столбцы. Ввод - это массив массивов, с внутренними массивами, являющимися строками. Выходные ходы есть
[row, column, row, column]
. ТестированиеНеуправляемый с объяснением
источник
intersect
это такое громоздкое ключевое слово)intersect
, я не знаю, сможете ли вы исправить это, как работает мой, потому что Ruby вfind
основном работает с функциями, а вашеfunction
ключевое слово столь же громоздко.find
- спасибо! Тем не менее, близко к тому, чтобыОктава,
334313 байтовПоскольку проблема может показаться немного сложной, я представляю свое собственное решение. Я формально не доказал, что этот метод работает (я полагаю, что это сводится к доказательству того, что алгоритм никогда не застрянет в цикле), но пока он работает отлично, выполняя тестовые примеры 100x100 в течение 15 секунд. Обратите внимание, что я решил использовать функцию с побочными эффектами, а не функцию, которая возвращает все координаты, поскольку это сэкономило мне несколько байтов. Координаты являются основными строками, основаны на 1 и отформатированы как
row1 col1 row2 col2
. Цвета ввода таковы, что0,1,2
это работает лучшеmod
, за счет использования,numel
а неnnz
. Версия для гольфа: Edit: сохранил еще несколько байтов, используя технику из ответа Кевина Лау.Пример GIF алгоритма решения:
Безголовая версия:
источник
Луа,
594575559 байтВнимание! До того, как я закончу с этим гольфом, еще много работы! Я должен быть в состоянии принять это до 500 байт, по крайней мере. На данный момент это первое решение, которое сработало, и я все еще работаю над ним.
Я предоставлю полное объяснение, как только я закончу.
источник
Ржавчина,
496495 байтК сожалению, я не могу победить OP, но для ответа Rust я вполне доволен бай-счетом.
Ввод: вектор чисел, а также количество столбцов. Например
выходы
в командной строке.
Сначала я решаю каждую строку, а затем - полученный столбец только один раз, но печатаю шаги для всех столбцов. Так что это на самом деле довольно эффективно :-P.
С форматированием:
Изменить: теперь возвращает цвет решения, которое спасает меня точка с запятой ^^
источник
Befunge ,
197368696754 байта(да, я занимаюсь гольфом с обратным кодом, чем больше байтов, тем лучше)
Я думал, что это может быть проблемой, чтобы написать этот алгоритм в Befunge и что это может быть весело
Я хотел бы, чтобы это была общественная программа, поэтому, если кто-то хочет работать над этим, пожалуйста, сделайте это.В конце концов, пока я все сделал один, так что я закончу сам (это почти сделано)
Что еще сделано: код в форме тролля
(да, это тролль, поверь мне)
По сути, он читает массив и вычисляет движение, которое нужно выполнить, чтобы решить строки, учитывая входные данные как
(весь массив передается в виде списка [row1, row2, row3,…])
вывод
строки и столбцы оба начинаются с 0.
Теперь, когда строки решены, это почти сделано! Ура!
Пояснение: (будет обновлено позже)
Итак, есть 5 основных частей:
Серые части - инициализация
Вот более глубокое объяснение модуля, который находит объединяемые блоки (кстати, здесь это кодируется)
Часть CALL - это когда указатель инструкции собирается в другой модуль, чтобы объединиться в блоки. Он возвращается к этому модулю через запись «B»
Вот некоторый псевдокод: (currentx связан с чтением массива) Для:
Обратите внимание, что если вы хотите проверить его, вам нужно будет поставить некоторое конечное пространство и завершающие новые строки, чтобы было достаточно места для хранения массива, если вы хотите использовать интерпретацию, которую я связал. 22 + количество строк на входе в качестве конечных строк и 34 + количество столбцов в качестве конечных пробелов в одной строке должно быть в порядке.
источник
\r\n
вместо\n
?)C, 404 байта
Мой первый код гольф, я очень доволен тем, как это получилось. Хотя это заняло слишком много времени. Это не полностью стандартный C, только то, что скомпилируется в gcc без специальных флагов (и игнорирует предупреждения). Так что там есть вложенная функция. Функция
f
принимает измеренияm
и вn
качестве своих первых аргументов, а в качестве третьего аргумента принимает (int-указатель) массив массиваm
×n
(индексируется сначала по строкам). Другие аргументы - это фиктивные аргументы, вам не нужно их передавать, они просто предназначены для сохранения байтов при объявлении переменных. Он записывает каждую измененную пару в формат STDOUT в форматеrow1,col1:row1,col1;
с точкой с запятой, разделяющей пары. Использует индексирование на основе 0.Я использовал немного другой алгоритм, чем OP для решения отдельных строк / столбцов. Это выглядит примерно так (псевдокод):
for(;~b;b--)
выполнении цикла ровно в два раза, на втором проходе он решает столбцы вместо строк. Это делается путем заменыn
иm
и изменения значенийo
и,p
которые используются в арифметике указателей для обращения к массиву.Вот версия, которая не разглажена, с тестовой основной и печатает весь массив после каждого хода (нажмите ввод для шага 1 хода):
источник