Решение первой задачи.
Advent of Code — это праздничное соревнование по решению алгоритмических задач с использованием языка программирования. Часто проблемы связаны с манипулированием текстом, сортировкой и иногда динамическим программированием. Я буду решать Advent как можно дольше, вероятно, используя Python, хотя в прошлом году я использовал Haskell и Python. В прошлом году испытания стали тяжелыми, и я не смог финишировать; в этом году я постараюсь закончить весь Адвент. Для первого вызова мы рассмотрим текст вызова и ввод.
Текст вызова
Джунгли должны быть слишком заросшими и трудными для навигации на транспортных средствах или доступа с воздуха; Экспедиция эльфов традиционно идет пешком. Когда ваши лодки приближаются к берегу, эльфы начинают проводить инвентаризацию своих припасов. Одним из важных соображений является еда — в частности, количество калорий, которое несет каждый эльф (ваш вход в головоломку).
Эльфы по очереди записывают количество калорий, содержащихся в различных блюдах, закусках, пайках и т. д., которые они принесли с собой, по одному пункту в строке. Каждый эльф отделяет свой инвентарь от инвентаря предыдущего эльфа (если он есть) пустой строкой.
Например, предположим, что эльфы закончили записывать калории своих предметов и получили следующий список:
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
В этом списке представлены калории еды, которую несут пять эльфов:
Первый эльф несет еду на
1000
,2000
и3000
калорий, всего6000
калорий.
Второй эльф несет одну еду с
4000
калориями.
Третий эльф несет еду на
5000
и6000
калорий, всего11000
калорий.
Четвертый эльф несет еду на
7000
,8000
и9000
калорий, всего24000
калорий.
Пятый эльф несет одну еду с
10000
калориями.
На случай, если эльфы проголодаются и им понадобятся дополнительные закуски, им нужно знать, у какого эльфа спросить: они хотели бы знать, сколько калорий несет эльф, несущий наибольшее количество калорий. В приведенном выше примере это
24000
(у четвертого эльфа).
Найдите эльфа с наибольшим количеством калорий. Сколько всего калорий несет этот эльф?
Решение
Эта задача выглядит относительно простой. Мы прочитаем данные, разделенные на новые строки, а затем сохраним их в списке целых чисел. Первая часть задачи состоит в том, чтобы вернуть наибольшее количество калорий, что означает, что нам нужно суммировать все калории для каждого эльфа, а затем вернуть наибольшее значение. Для решения первой части я использовал сокращение из functools, чтобы уменьшить список, используя max, а затем вернул значение.
Во второй части, которая немного сложнее, нам нужно найти три первых числа калорий, а затем вернуть их сумму. Для этого я отсортировал суммарные калории для каждого эльфа по количеству калорий в обратном порядке от наибольшего к наименьшему. Затем я получил первые три значения из отсортированного списка.
from functools import reduce def find_highest_calories(calories): return reduce(max, calories) def find_top_three(calories): return sorted(calories, reverse=True)[:3] with open("input.txt") as file: text = file.read() blocks = text.split("\n\n") calories = [[int(s) for s in block.split("\n")] for block in blocks] total_calories = [sum(c) for c in calories] print(f"Highest calories = {find_highest_calories(total_calories)}") top_three = find_top_three(total_calories) print(f"Sum of top three calories = {sum(top_three)}")
Сложность
В первой части временная сложность поиска по всему списку с использованием сокращения и нахождения максимума будет линейной, O(n) в худшем случае. Пространственная сложность также равна O(n), так как нам нужно сохранить не более n калорий в списке, включая все калории для каждого эльфа.
Во второй части пространственная сложность по-прежнему будет O(n), потому что мы сохраняем калории аналогичным образом. Однако временная сложность будет лог-линейной, O(n log n), потому что функция sorted в Python использует алгоритм сортировки, основанный на сортировке слиянием.
Финал
Для начала все было нормально, первая задача обычно несложная, и ее легко решить с помощью сортировки и линейного поиска с использованием сокращения. Завтрашняя задача может быть более сложной, но, надеюсь, не слишком.