Advent of Code: Day 1

Solving the first challenge.

Photo by Elena Mozhvilo on Unsplash

The Advent of Code is a holiday competition to solve algorithmic challenges using a programming language. Often the challenges involve text manipulation, sorting, and sometimes dynamic programming. I will solve the Advent for as long as possible, probably using Python, although I used Haskell and Python last year. Last year the challenges got tough, and I didn’t finish; this year, I’ll try my best to finish the entire Advent. For the first challenge, we will look at the challenge text and the input.

Challenge Text

The jungle must be too overgrown and difficult to navigate in vehicles or access from the air; the Elves’ expedition traditionally goes on foot. As your boats approach land, the Elves begin taking inventory of their supplies. One important consideration is food — in particular, the number of Calories each Elf is carrying (your puzzle input).

The Elves take turns writing down the number of Calories contained by the various meals, snacks, rations, etc. that they’ve brought with them, one item per line. Each Elf separates their own inventory from the previous Elf’s inventory (if any) by a blank line.

For example, suppose the Elves finish writing their items’ Calories and end up with the following list:

1000
2000
3000

4000

5000
6000

7000
8000
9000

10000

This list represents the Calories of the food carried by five Elves:

The first Elf is carrying food with 1000, 2000, and 3000 Calories, a total of 6000 Calories.

The second Elf is carrying one food item with 4000 Calories.

The third Elf is carrying food with 5000 and 6000 Calories, a total of 11000 Calories.

The fourth Elf is carrying food with 7000, 8000, and 9000 Calories, a total of 24000 Calories.

The fifth Elf is carrying one food item with 10000 Calories.

In case the Elves get hungry and need extra snacks, they need to know which Elf to ask: they’d like to know how many Calories are being carried by the Elf carrying the most Calories. In the example above, this is 24000 (carried by the fourth Elf).

Find the Elf carrying the most Calories. How many total Calories is that Elf carrying?

Solution

This challenge looks relatively simple. We’ll read the data split on newlines and then store this in a list of integers. The first part of the challenge is to return the most amount of calories which means we need to sum all the calories for each elf and then return the largest value. For the solution to the first part, I used reduce from functools to reduce the list using max and then returned the value.

For the second part, which is a bit more complicated, we need to find the top three numbers of calories and then return their sum. To do this, I sorted the summed calories for each elf by the number of calories in reverse order from largest to smallest. Then I got the first three values from the sorted list.

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)}")

Complexity

For the first part, the time complexity of searching through the entire list using reduce and finding the max would be linear, O(n) in the worst case. Space complexity is also O(n) since, at most, we need to store n total calories in a list, including all the calories for each elf.

For the second part, the space complexity would still be O(n) because we store the calories similarly. Time complexity, however, would be log-linear, O(n log n), because Python’s sorted function uses a sorting algorithm based on mergesort.

Finale

It was ok for a start, the first challenge is usually easy, and this was easily solved by sorting and linear searching using reduce. Tomorrow’s challenge may be more complicated but hopefully not by too much.