Решение первой задачи.

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 использует алгоритм сортировки, основанный на сортировке слиянием.

Финал

Для начала все было нормально, первая задача обычно несложная, и ее легко решить с помощью сортировки и линейного поиска с использованием сокращения. Завтрашняя задача может быть более сложной, но, надеюсь, не слишком.