Для получения дополнительной информации посмотрите это видео и перейдите к A276523 для связанной последовательности.
Головоломка Мондриана (целое число n
) выглядит следующим образом:
Вставьте неконгруэнтные прямоугольники в n*n
квадратную сетку. Какая наименьшая разница возможна между самым большим и самым маленьким прямоугольником?
Для 6
, разницы оптимальной для M(6)
IS 5
, и может быть продемонстрировано следующим образом:
___________
| |S|_______|
| | | L |
| |_|_______|
| | | |
| |_____|___|
|_|_________| (fig. I)
Самый большой прямоугольник (L) имеет площадь 2 * 4 = 8
, а самый маленький прямоугольник (S) имеет площадь 1 * 3 = 3
. Поэтому разница есть 8 - 3 = 5
.
Имейте в виду, что в настоящее время не найдено оптимальных решений для n > 44
.
Ваша задача - создать программу, которая генерирует сетку Мондриана, которая содержит (неоптимальное) решение с заданным целым числом n
.
Вы будете проверены на числа от 100 до 150. Ваша оценка для каждого теста будет разница между самым большим и самым маленьким прямоугольником. Ваш общий балл - это сумма ваших баллов за все тесты от 100 до 150.
Вы должны представить свой вывод так:
{number}
{grid}
Где number
находится оценка (разница между наибольшим и наименьшим), а grid
также:
- Многолинейная строка, или
- Двумерный список.
Сетка ДОЛЖНА четко показывать, где начинается и заканчивается прямоугольник.
Правила:
- Ваша программа должна соответствовать вашему ответу.
- Ваша программа должна вывести значение для любого числа от 100 до 150 в течение 1 часа на современном ноутбуке.
- Ваша программа должна генерировать одно и то же решение для целого числа
n
каждый раз, когда программа запускается. - Вы должны предоставить ссылку на результаты всех 51 решений (используя Pastebin, Github Gist ... что угодно, правда).
- У вас должно быть как минимум два прямоугольника на квадратной сетке для вашего решения.
источник
Ответы:
Пит, 9625
(Это наконец работает!)
Люди требовали этого, так что вот оно. Это чрезвычайно наивное решение (по сути такое же, как и свободные верхние границы на странице OEIS): оно делит каждый квадрат всего на два прямоугольника.
Эта суть содержит детали в двух файлах:
?
это приглашение к вводу, за которым сразу следует оценка результата, а затем сетка.объяснение
Эта программа занимает одно число
N
качестве ввода. Если число нечетное, оценка является числом; если даже, счет в два раза больше.После вывода результата остальная часть левой части программы тратится на заполнение стека пятью лотами следующей информации:
N
)_
пробел)|
)Правая часть программы берет каждый набор из четырех значений и печатает эту часть сетки.
источник
C 6108
При этом используется рекурсивная (действительно итеративная) версия минимального решения. Вместо того, чтобы делить квадрат на два прямоугольника, где один немного больше половины площади, он делит его на N прямоугольников. Таким образом, первый прямоугольник немного больше, чем
1/N
общая площадь. Затем, взяв остаток, программа отсекает прямоугольник, немного больший, чем1/(N-1)
остаток, и так далее, пока не возьмет остаток как последний прямоугольник. Прямоугольники отрезаются от остатка по спирали по часовой стрелке, поэтому сначала сверху, затем справа и т. Д.Поскольку это очень прямой метод, а не поиск по широкому пространству, он работает быстро - примерно 25 секунд (на Raspberry Pi), чтобы найти 74 решения, каждое для данного набора проблем.
Мое намерение состоит в том, чтобы использовать эти результаты для лучшего информирования алгоритма поиска для более сложного подхода.
Выходные данные дают оценку, а также (ascii) рисунок и координаты для вершин прямоугольников. Вершины расположены по часовой стрелке, начиная с верхнего левого угла рассматриваемого прямоугольника.
Разработано с использованием gcc 4.9.2-10.
Результаты на https://github.com/JaySpencerAnderson/mondrian
Код:
источник
С - 2982
Эта программа реализует поиск по широкому набору результатов. Важной частью практического поиска был провал на раннем этапе и / или отказ от плохих путей.
Это создает набор прямоугольников, которые необходимо учитывать при решении. Сгенерированный набор прямоугольников позволяет избежать тех с размерами, которые не будут полезны. Например, если программа пытается найти решение для квадрата 128x128, разделенного на 8 прямоугольников, она сгенерирует прямоугольник 128x16. Он не сгенерирует это значение 120x17, потому что нет перспективы создания прямоугольника шириной 8, чтобы заполнить пробел в конце 120.
Первоначальная стратегия размещения прямоугольников состоит в том, чтобы разместить их внутри периметра квадрата (функция buildedge). Таким образом, алгоритм получает довольно быструю обратную связь на каждом углу относительно того, есть ли проблема с выбранной последовательностью. Размещая прямоугольники, логика продолжает следить за тем, чтобы не возникли какие-либо пробелы в пространстве, которые слишком узки для какого-либо прямоугольника. После успешного заполнения периметра стратегия меняется на попытку сопоставить оставшееся пространство с оставшимися прямоугольниками (функция соответствия).
Еще одна вещь, которая может представлять интерес, - это то, что она реализует транзакции с откатом для стеков прямоугольников.
Эта программа не пытается найти наиболее подходящее. Он получает бюджет (64) и выходит, когда находит первое решение. Если решение не найдено, мы увеличиваем бюджет (на 16) и пытаемся снова. Требуемое время (на ноутбуке Dell с процессором I7) варьировалось от чуть менее минуты до 48 минут на 150 на стороне (149 на стороне заняло менее 2 минут). Все 51 решения использовали 11 прямоугольников. Баллы 51 решения варьировались от 41 до 78. Причины, по которым я использовал 11 прямоугольников, заключались в том, что оценка была ниже, чем при меньшем количестве прямоугольников, и казалось, что для 12 прямоугольников потребуется намного больше, чем выделенный час.
Решения и код можно найти по адресу https://github.com/JaySpencerAnderson/mondrian . Это два файла my4 *.
Кстати, если вы скомпилируете это в «my4» и выполните его следующим образом: «./my4 -h», это даст вам возможность использования. Если вы хотите увидеть это в действии, попробуйте что-то вроде «./my4 -l 50 -n 8». Если вы измените значение «#if 0» на «#if 1», оно отобразит оставшееся место на экране. Если вы хотите изменить это для отображения прямоугольников, найдите одну точку, где код выполняет «graph (space, side)» и замените ее на «graph (callstack, side)». Я бы также предложил изменить первоначальный бюджет с 64 до 32, если вы хотите поиграть с решениями для квадратов шириной около 50. Решение для меньших квадратов будет лучше с меньшим бюджетом.
Программа ниже является функциональной. Проверьте github на полный код (с использованием, комментариями и т. Д.).
источник