Сегодня седьмой день Пришествия кода. Сегодня мы будем в значительной степени полагаться на алгоритмы. Мы также пройдем процесс оптимизации одного из решений.

Как всегда, пожалуйста, попробуйте решить проблему, прежде чем искать решение. Для всех статей в этой серии ознакомьтесь с этим списком.

День 7: Часть 1

Наша цель - определить оптимальное горизонтальное положение для крабовых подводных лодок. Ввод представляет собой список позиций, разделенных запятыми, например. 16,1,2,0,4,2,7,1,2,14.

Мы стремимся свести к минимуму общую стоимость перемещения подводных лодок к месту назначения, где стоимость каждой подводной лодки — это просто расстояние от цели. Так, например, для ввода 0,2,2,3 оптимальной целью будет 2, а стоимость также 3 (стоимость двух подводных лодок в нулевой позиции и одной для подводной лодки в третьей позиции).

Начнем, как обычно, с наших объявлений и тестов:

Мы начнем с наивной реализации. Решение будет где-то близко к среднему и медиане. Таким образом, мы можем сортировать подводные лодки, а затем сканировать слева и справа от средней точки, чтобы увидеть, улучшается ли общая стоимость.

Анализ ввода следует той же схеме, что и в предыдущие дни. Мы читаем до конца ввода и проверяем допустимые разделители.

После сортировки (строка 16) мы вычисляем начальную сумму (строка 21), а затем пытаемся выполнить итерацию слева и справа и с каждым элементом проверить, лучше ли сумма с новой средней точкой. Наконец, мы возвращаем лучший из двух результатов поиска (строка 47).

День 7: Часть 2

В части 2 корректируем формулу расчета стоимости. Стоимость перестала быть линейной. Вместо этого каждый шаг становится все дороже, то есть перемещение подводной лодки на один шаг будет стоить 1, на два шага 1+2, на пять шагов 1+2+3+4+5 и т. д.

Важно отметить, что это также означает, что наша цель не обязательно является одной из существующих позиций. К счастью, мы можем изменить решение для части 1, чтобы получить перебор любой монотонной функции стоимости.

Вместо того, чтобы перебирать элементы, мы теперь перебираем все целочисленные значения во время нашего поиска. Однако этот код надежен и будет работать как для части 1, так и для части 2:

День 7: Оптимизация

Оба наших решения будут работать. Однако у вас может возникнуть подозрение, что особенно решение для части 2 далеко от оптимального.

Давайте сначала вернемся к решению для части 1. Когда мы сканируем влево или вправо, мы знаем, насколько изменится общая сумма. Представьте себе ...4,5..., если мы перейдем от четырех к пяти, сумма изменится на (5–4)*len(left)-(5–4)*len(right).

Давайте подробнее рассмотрим формулы, которые мы используем для расчета изменений. Поскольку мы начинаем с середины, вторая часть формулы всегда будет отрицательной, и мы также знаем, что первая часть формулы всегда будет положительной (или равной нулю). Поэтому мы можем вообще пропустить оба цикла.

Это решение короче, и поскольку теперь нам нужно только вычислить медиану, а не сортировать весь массив, он работает в O(n), а не O(n*logn).

Аналогичный подход работает и для part2, используя среднее значение. Смотрите обсуждение на Reddit.

Ссылки и технические примечания

Репозиторий ежедневных решений доступен по адресу: https://github.com/HappyCerberus/moderncpp-aoc-2021.

Посмотрите в этом списке статьи о других днях появления кода.

И, пожалуйста, не забудьте попробовать Пришествие кода на себе.

Спасибо за чтение

Спасибо, что прочитали эту статью. Вам понравилось?

Я также публикую видео на YouTube. У тебя есть вопросы? Напишите мне в Twitter или LinkedIn.