Могут ли эти прямоугольники заполнить прямоугольное пространство?
Учитывая группу прямоугольников, вас спрашивают, могут ли они быть расположены так, чтобы заполнить прямоугольное пространство.
Спекуляции
Задано множество произвольных m x n
прямоугольников; 0 <= m, n <= 1000
Определите, можно ли расположить их так, чтобы они точно покрывали прямоугольную область без каких-либо отверстий или перекрытий. Прямоугольники не могут быть повернуты, и каждый прямоугольник может быть размещен только один раз.
вход
Входные данные для этого очень гибкие, поскольку входные данные дают некоторый список двухмерных измерений. Например, оба из следующих допустимы:
Разделенный пробелом, возвращение
1 2
1 5
4 5
3 6
Список размеров
[[1, 2], [1, 5], [4, 5], [3, 6]]
Выход
Любые значения true / false, такие как true / false, 0/1, T / F, True / False и т. Д. Если вы собираетесь использовать метод вывода, который не очень очевиден, пожалуйста, укажите в своем ответе.
Примеры
Тестовый пример 1
Входные данные:
1 1
1 5
2 6
Вывод:
true
(или что-то подобное)
Как это устроить:
XYYYYY
ZZZZZZ
ZZZZZZ
Тестовый пример 2
Входные данные:
1 1
2 2
Вывод:
false
(или что-то похожее)
Объяснение: Становится очевидным, что вы не можете расположить два квадрата разных размеров и выровнять их края.
Тестовый пример 3
Входные данные:
1 1
1 2
1 2
2 1
2 1
Вывод:
true
(или что-то подобное) Как это устроить:
AAB
DEB
DCC
Как указывало @ETHProductions, для всех остальных тестовых случаев вы можете продолжать комбинировать прямоугольники с общей длиной ребра, пока у вас не будет только одного прямоугольника, поэтому этот тестовый случай просто нарушает любой код, использующий эту идею.
Тестовый пример 4
Входные данные:
3 2
4 1
2 1
4 1
2 1
5 2
3 2
1 4
3 2
2 1
2 1
1 1
5 1
Вывод:
true
(или что-то подобное)
Как это устроить:
AAABBBBEE
AAACCDDDD
FFFFFGGGH
FFFFFGGGH
IIIJJKKLH
IIIMMMMMH
Примечание : вам не нужно указывать, как это организовать, вам нужно только определить, можно ли это организовать.
Это код гольф, поэтому самый короткий ответ в байтах выигрывает! Я приму кратчайший ответ от 14 января, но не стесняйтесь отправлять ответы позже, так как я все еще могу отдать голоса! :)
Удачного игры в гольф!
~ AL
PS Если вы знаете, какой тег должен быть применен к этой проблеме, пожалуйста, добавьте его, я абсолютно не знаю, что поставить в качестве тега, кроме code-golf.
РЕДАКТИРОВАТЬ : Ваша программа должна быть способна обрабатывать до 25 прямоугольников, самое большее за 10 секунд на приличном компьютере (я буду достаточно гибок в этом правиле).
РЕДАКТИРОВАТЬ : я продлил срок приема заявок до последнего дня года, но я сомневаюсь, что получу ответ к тому времени ...
РЕДАКТИРОВАТЬ : я продлил срок приема заявок на 2 недели, поэтому, если к тому времени больше не будет ответов, текущий ответ C будет принят! :)
источник
[[1, 2], [2, 1], [1, 1], [1, 2], [2, 1]]
(который может быть устроенABB ACD EED
). Вы можете добавить этот простой контрольный пример.Ответы:
C 1135
115812311598байтЧто ж, он прошел установленный срок, но, учитывая, что ответов пока нет, вот один (немного длинный) на C.
Возвращает:
Обновить:
Исходный код может застрять на некоторых матрицах, занимая намного больше времени, чем разрешенные 10 секунд. Текущая редакция должна завершить все матрицы до 1 с. Это достигается путем 1) сортировки входных прямоугольников и 2) пропуска повторяющихся размеров при подгонке.
Golfed:
UnGolfed:
Объяснение: У нас есть 6 функций:
main
,O
,Q
,F
,L
иT
.T
т эстов , чтобы увидеть , если есть пространство для прямоугольника в данном месте.L
фил л а м прямоугольник в выходной буфер или, альтернативно удаляет один путем перезаписи его.O
иQ
создать левые и верхние стенки, соответственно , иF
е бед оставшуюся часть прямоугольника путем итеративного поиска.Хотя основной поиск является итеративным, мы исключаем подавляющее большинство возможных векторов поиска, сначала создавая допустимые комбинации ширины и высоты для основного прямоугольника, а затем устраняя невозможные конфигурации. Дополнительную скорость можно получить в больших прямоугольниках, определяя нижнюю и правую стенки перед заполнением центра, но это не требуется для приличной скорости при ограничении до 25 внутренних прямоугольников.
источник
Haskell, 226 байт
Попробуйте это на Ideone
Как это работает
Это рекурсивно ищет все частичные наклоны, форма которых представляет собой диаграмму Юнга , добавляя один прямоугольник за раз, и проверяет, являются ли какие-либо из конечных результатов прямоугольниками.
Чтобы увидеть, что любая мозаика прямоугольника может быть построена следующим образом: в любой мозаике непустой диаграммы Юнга пусть R будет набором прямоугольников в мозаике, юго-западный угол которых не касается другого прямоугольника. Поскольку каждая вогнутая вершина диаграммы Юнга примыкает к ребру (а не только к углу) не более чем к одному прямоугольнику в R, а количество этих вогнутых вершин на один меньше, чем число прямоугольников в R, должно быть не менее один прямоугольник в R, примыкающий к ребру ни к одной из этих вогнутых вершин. Удаление его приводит к другой диаграмме Юнга, поэтому мы можем действовать по индукции.
источник