Есть такая задача:
4 By 4 Skyscrapers | Codewars
Полагаю, в простейшем случае можно, особо не заморачиваясь, решить ее в лоб, то есть путем перебора всех возможных вариантов с отсеиванием неподходящих. Но, во-первых, так неинтересно; во-вторых, есть усложненные задачи того же типа, для которых брутфорсный подход, скорее всего, не подойдет из-за ограничения на время выполнения кода:
7×7 Skyscrapers | Codewars
Вернемся к нашим
баранам зданиям высотой от одного до четырех этажей, расставленных на гриде 4x4.
После долгих раздумий я решил поступить следующим образом.
1. Генерируем все варианты расположения зданий на линии, то есть в ряду или в колонке:
1, 2, 3, 4
2, 1, 3, 4
...
4, 3, 2, 1
2. Для каждого варианта расположения генерируем условия (виды «слева и справа» либо «сверху и снизу»), при которых они возможны, например:
1 [ 4 2 3 1 ] 3
1 [ 4 1 3 2 ] 3
1 [ 4 3 1 2 ] 3
3. Создаем вложенный массив, соответствующий гриду со зданиями, только вместо каждого здания — пустой массив:
[
[ [], [], [], [] ],
[ [], [], [], [] ],
[ [], [], [], [] ],
[ [], [], [], [] ]
]
4. Заполняем каждый пустой внутренний массив возможным количеством зданий, исходя из того, сколько зданий видно, если смотреть на грид сверху, снизу, слева и справа.
[ 1, 2, 3 ]
5. Рекурсивно решаем задачу, значительно сократив количество вариантов за счет использования возможных количеств зданий из вышеупомянутого вложенного массива.
Внимание, дилетантский вопрос: правильный ли это подход? Я уже начал неспешно решать эту задачу, но вот код получается чересчур замороченный, и это для такого простого случая...