Задний план
Я хочу купить участок земли и построить на нем свой дом. Мой дом должен быть прямоугольным и максимально большим; Тем не менее, на доступных участках есть много каменистых участков, на которых я не могу построить, и у меня возникают проблемы с установкой потенциального дома на участках. Я хочу, чтобы вы написали программу, которая анализирует графики для меня.
Вход и выход
Ваш ввод представляет собой прямоугольный двумерный массив битов размером не менее 1 × 1 в любом приемлемом формате. Массив представляет собой участок земли; 1
Это «хорошие» районы, где я мог бы построить свой дом, и 0
это «скалистые» районы, где дом не может быть построен.
Ваш вывод должен быть максимальной площадью сплошного прямоугольника 1
s во входном массиве. Он представляет собой площадь самого большого дома, который я мог построить на участке. Обратите внимание, что если 1
на входе нет s, то вывод будет 0
.
пример
Рассмотрим вход
101
011
111
Самый большой прямоугольник 1
s - это прямоугольник 2 × 2 в правом нижнем углу. Это означает, что правильный вывод 4
.
Правила и оценки
Вы можете написать полную программу или функцию. Побеждает меньшее количество байтов, и стандартные лазейки запрещены.
Контрольные примеры
0
-> 0
1
-> 1
00
00
-> 0
01
10
-> 1
01
11
-> 2
111
010
111
-> 3
101
011
111
-> 4
0111
1110
1100
-> 4
1111111
1110111
1011101
-> 7
111011000
110111100
001111110
011111111
001111110
000111100
000011000
-> 20
000110000
110110010
110111110
110011100
010011111
111111111
111101110
-> 12
plow
.Ответы:
Желе ,
21201817 байтПопробуйте онлайн! или проверьте все контрольные примеры .
Задний план
Пусть м будет матрицей битов, такой как
Начнем с подсчета количества 1 бит в каждом столбце M , сбрасывая счет каждый раз, когда встречаем 0 бит.
Для нашего примера матрицы это дает
Далее мы вычисляем все смежные подсписки каждой строки. Мы достигаем этого путем генерации всех срезов длиной k , где k варьируется от 1 до количества записей в каждой строке.
Для предпоследнего ряда это дает
Далее мы сопоставляем каждый срез с произведением его минимума и его длины. Для каждого среза это вычисляет площадь прямоугольника 1 бита максимальной высоты, в которой данный срез является нижней строкой.
Для срезов длины 3 предпоследней строки нашей примерной матрицы это дает
Все, что осталось сделать, это взять максимум на всех срезах всех строк.
Для нашего примера матрицы это дает 12 .
Как это устроено
источник
MATL,
323127 байтПри этом используется метод грубой силы на основе двухмерной свертки. Все возможные размеры прямоугольника созданы и свернуты с ландшафтом. Максимальным результатом всех сверток является максимальная площадь прямоугольника.
Это крайне неэффективное решение, потому что для сохранения байтов я создаю ядра для всех прямоугольников между
[1, 1]
и[numel(input) numel(input)]
, а не на самом деле определения количества строк / столбцов во входных данных , чтобы определить соответствующие диапазоны размеров прямоугольника.Спасибо @Luis за предложение использовать
M
и опустить]]
.Попробуйте онлайн!
объяснение
источник
Юлия,
83605753 байтаПопробуйте онлайн! Последний контрольный пример превышает ограничение времени TIO, но я проверил его локально.
Как это устроено
Во- первых, ! проверяет, состоит ли его матричный аргумент M полностью из 1 .
Если так, то ! возвращает сумму записей M , которая равна его площади.
Если нет, то ! делает следующее:
Поверните M на 0 ° , 90 ° , 180 ° и 270 ° по часовой стрелке.
Удалить первую строку каждый из четырех вращений, эффективно удаляя один из верхнего ряда, нижнего ряда, крайнего левого столбца и правой колонки М .
Вызовите себя рекурсивно для каждой из подматриц.
Вернуть максимум возвращаемых значений из рекурсивных вызовов.
источник
JavaScript (ES6), 97 байт
Оказывается, немного вертеться все еще выигрывает. Принимает массив массив целых чисел. Ungolfed:
Массив разделен по строкам в соответствии с другими ответами, поэтому каждый возможный диапазон строк циклически повторяется. Учитывая диапазон строк, следующий шаг должен измерить доступные прямоугольники. Это достигается путем объединения строк по битам; Результатом является список битов, которые были установлены во всем диапазоне строк. Затем остается найти максимальную длину установленных битов в строке и умножить ее на высоту диапазона. Тест бесстыдно украден у @ ed65:
источник
Python 2.7,
9391898179 байтВход представляет собой список кортежей. Проверьте меньшие контрольные примеры здесь и большие контрольные примеры здесь .
Без напоминания последние два тестовых случая превышают лимит времени Ideone, так как они требуют, соответственно, 1 530 831 935 и 2 848 806 121 звонков на f , что на моей машине занимает 39 и 72 минуты.
Алгоритм
Для данной матрицы M общая идея состоит в том, чтобы выполнить итерацию по всем подматрицам M , удаляя верхние строки и поворачивая четверть оборота против часовой стрелки, отслеживая размеры встречающихся подматриц, которые полностью состоят из 1 бита.
Использование простой рекурсивной реализации приведенной выше идеи приводит к функции f (M), которая выполняет следующее.
Если M не содержит 0 битов, вернуть его количество 1 бит.
Если мы уже повернули M два раза, и он не содержит 1 бит, верните 0 .
Если мы уже повернули M пять раз, вернем 0 .
Рекурсивно вызвать F на M без его верхнего ряда.
Рекурсивно вызвать F на M повернут на четверть оборота против часовой стрелки.
Вернуть максимум возвращаемых значений из рекурсивных вызовов.
Код
В реализации мы используем дополнительный аргумент функции t, который по умолчанию равен 1, чтобы отслеживать, сколько раз мы уже поворачивали эту конкретную матрицу. Это позволяет объединить шаги с 1 по 3 в один шаг путем тестирования
`t/3`in`M`
и возврата в`M`.count(`t`)
случае сбоя теста.Если t = 1 , мы не вращали эту конкретную подматрицу ранее в этой ветви.
t / 3 = 0 , поэтому
`t/3`in`M`
вернет True, если строковое представление M содержит символ 0 .Если этого не произойдет , мы возвращаемся
`M`.count(`t`)
, число раз , символ 1 появляется в строке представления М .Обратите внимание, что матрица без 0 битов может появиться, только если t = 1 , так как в этом случае мы не рекурсивно.
Если 3 ≤ t ≤ 5 , мы ранее вращали эту конкретную подматрицу как минимум два раза в этой ветви.
t / 3 = 1 , поэтому
`t/3`in`M`
вернет True, если строковое представление M содержит символ 1 .Если этого не произойдет , мы возвращаем 0 , вычисленный , как
`M`.count(`t`)
, сколько раз строковое представление т (т.е. символ 3 , 4 или 5 ) появляется в строке представления М .Если т = 6 , мы ранее вращали эту конкретную подматрицу пять раз в этой ветви.
t / 3 = 2 , поэтому
`t/3`in`M`
вернет False , потому что строковое представление M не содержит символа 2 .Возвращается 0 вычисляется
`M`.count(`t`)
, число раз символьные 6 появляется в строковом представлении М .Если f еще не вернулся, остальные шаги выполняются.
f(M[1:])
вызывает f на M без его верхнего ряда. Поскольку t не указан, по умолчанию он равен 1 , что означает, что это первый раз f встречает эту конкретную подматрицу в этой ветви.f(zip(*M)[::-1],t+1)
звонит ф на М повернуты на четверть оборота против часовой стрелки, увеличивая t чтобы отследить время, когда мы повернули эту конкретную подматрицу в этой ветви.Четверть оборота получается путем объединения строк M друг с другом, возвращая кортежи соответствующих элементов строк M , таким образом транспонируя М , затем изменяет порядок строк (то есть, помещая верхнюю строку в нижней части, и наоборот ).
Наконец,
max
возвращает максимум возвращаемых значений из рекурсивных вызовов.источник
zip
возвращает список кортежей соответствующих элементов своих аргументов. С распакованным 2D списком (матрицей)*M
он по существу транспонирует строки и столбцы, поэтомуzip(*M[::-1])
выполняет поворот на 90 ° по часовой стрелке.JavaScript (ES6), 154
176Редактировать попытался немного сократить, но не может конкурировать с решением @ Neil
Попробуйте все возможные прямоугольники, верните максимальный размер. Вероятно, тот же алгоритм ответа Matl, только в 6 раз дольше.
Ввод как двумерный массив целых
Меньше гольфа
Это оригинальный алгоритм, в версии для гольфа используется много функций обхода массива вместо циклов
Тестовое задание
источник
APL (Dyalog Extended) ,
272320 байт-3 байта от Adám и ngn
Попробуйте онлайн!
источник
{⌈/,(×/×1∊⍵⍷⍨⍴∘1)¨⍳⍴⍵}
короче и проще (даже не требует расширенного).{⌈/∊(×/×⍵⍷⍨⍴∘1)¨⍳⍴⍵}
Брахилог ,
201715 байтСпасибо Kroppeb за 2 байта
Попробуйте онлайн!
объяснение
источник
aa
можно заменитьs
Попробуй онлайн!R ,
129122 байтПопробуйте онлайн!
Простой и простой подход грубой силы.
Развернутый код и объяснение:
источник
Stax , 14 байт
Запустите и отладьте его
источник
Matlab 106 байт
Ungolfed:
Операция в цикле начинается с двухмерной свертки
conv2()
входного массива сp*m
массивом единиц.==p*m
проверяет, содержит ли результирующий массив элемент, равныйp*m
. Соответствующий элемент превращается в1
, все остальные элементы превращаются в0
.any()
превращает массив в вектор. В1
противном случае столбцы, содержащие хотя бы одну ненулевую запись, преобразуются в0
.p*m*()
умножает вектор,p*m
превращая все1
-s вp*m
.[__,r]
квадратные скобки объединяют полученный результат с предыдущей максимальной площадью, сохраненной вr
. Наконец,max()
находит максимальное значение в результирующем векторе.источник
any()
возвращает,1
если столбец содержит ненулевой элемент и в0
противном случае.Matlab
(222)(209)На самом деле, это решение приносит мне стыд за то, что я вдвое больше, чем само решение на одном языке, но ... глупо, я думал об этом в течение 6 часов! и хитрость немного отличается от ответов Денниса и Нейла.
Функция называется как
Я мог бы сэкономить больше байтов, если бы вводил длину матрицы в размерах функции, хотя бы и больше игры в гольф продолжается.
Как это происходит?
Этот алгоритм добавляет фактическую матрицу к себе, сдвинутую влево, с небольшим поворотом (&). на любом этапе полученная матрица устанавливается как исходная и добавляется к себе, многократно смещаясь вверх, а затем перезапускается с начала с новой матрицей. Все подэлементы всех матриц, сгенерированных этой операцией
(original_matrix+shifted_matrix)&shifted_and_original_matrices)
, максимизируются до выхода.пример:
источник
Japt , 30 байт
Попробуйте все тестовые случаи
Примерно порт Денниса ответит желе. Тестовые случаи - это просто двумерные массивы чисел, преобразованные из формата вопроса с помощью этого .
Объяснение:
источник
J , 38 байт
Попробуйте онлайн!
как
источник