Это снова то время года, так что давайте поможем эльфам с помощью Modern C++. Однако, прежде чем читать мои решения, рекомендую попробовать решить проблемы самостоятельно: https://adventofcode.com/.
Вход
Наш ввод представляет собой ряд чисел, разделенных пустыми строками. Чтобы иметь простой интерфейс для нашего решения на C++, давайте возьмем его как std::vector<std::string>
, где пустые строки служат нашими разделителями.
Часть 1: эльф с наибольшим количеством калорий
Наша цель в первой части — определить эльфа с наибольшим количеством калорий. Давайте подумаем, что нам нужно сделать, чтобы попасть туда из нашего входа std::vector
.
- разделить ввод на эльфа
- перевести каждую строку в число (теперь, когда разделители исчезли)
- суммируем числа, чтобы у нас было общее количество для каждого эльфа
- выберите эльфа с самой высокой суммой
Всего этого можно добиться с помощью представлений и алгоритмов.
- используйте
std::views::lazy_split
, чтобы сделать вид диапазонов, по одному для каждого эльфа - используйте
std::views::transform
, чтобы преобразовать каждый из этих диапазонов в одно число (количество калорий) - используйте
std::max_element
, чтобы выбрать эльфа с наибольшим количеством калорий
Чтобы преобразовать диапазон в одно число, мы снова можем использовать представления и алгоритмы:
- используйте
std::transform
сstd::stoull
для преобразования каждогоstd::string
в число - используйте
std::reduce
, чтобы суммировать числа
Собрав это вместе, мы получим такое решение:
Часть 2: тройка эльфов с наибольшим количеством калорий
Наша вторая цель состоит в том, чтобы вместо поиска высшего эльфа (например, max_element
) найти трех лучших эльфов и вернуть сумму всех калорий, которые они несут.
Мы можем повторно использовать почти все наше предыдущее решение. Основное изменение заключается в том, что нам нужно определить три верхних элемента в нашем преобразованном диапазоне.
Чтобы выбрать три верхних элемента, нам понадобится сортировка. Однако мы не можем сортировать представление (std::views::lazy_split
моделирует только диапазон ввода). К счастью, у нас есть std::partial_sort_copy
, который может работать с диапазоном входных данных, если назначением является произвольный доступ.
Получив три верхних элемента, мы можем снова использовать std::reduce
для получения суммы.
Собрав это вместе, мы получим следующее решение:
Ссылки
Репозиторий с полным решением (включая парсинг ввода) доступен здесь: https://github.com/HappyCerberus/moderncpp-aoc-2022.
Я ежедневно размещаю контент на современном C++ в Twitter, LinkedIn, Mastodon, Medium и Substack.