Как лучше решать такие задачи?
От: Lazytech Ниоткуда  
Дата: 25.10.20 12:19
Оценка:
Есть такая задача: 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. Рекурсивно решаем задачу, значительно сократив количество вариантов за счет использования возможных количеств зданий из вышеупомянутого вложенного массива.

Внимание, дилетантский вопрос: правильный ли это подход? Я уже начал неспешно решать эту задачу, но вот код получается чересчур замороченный, и это для такого простого случая...