Advent of Code

Cover Image by Lionello DelPiccolo on Unsplash

In December 2024, I decided to participate in the Advent of Code challenge. The Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language. The challenge is organized by Eric Wastl and has been running since 2015. The puzzles are released daily at midnight Eastern Time (05:00 UTC) from December 1st to December 25th. Each puzzle has two parts, and the difficulty increases as the days go by.

I participated in the challenge using Python. I solved the puzzles for each day and shared my solutions on GitHub. The repository contains the solutions for each day, as well as a script to download the input data for each day. There is also a bash script to run the solutions for all days and measure the time it takes to solve each puzzle.

Algorithms Used

For the solutions, I used a variety of algorithms, depending on the requirements of the puzzle. Some of the algorithms I used include:

• Brute Force: I used brute force to solve puzzles that required checking all possible combinations.
• Dynamic Programming: I used dynamic programming to solve puzzles that required finding the optimal solution by breaking it down into smaller subproblems.
• Generators: I used generators to create iterators for puzzles that required iterating over a large number of elements.
• Recursive Functions: I used recursive functions in problems that naturally lend themselves to recursive solutions.
• Memoization: I used memoization to optimize recursive solutions by storing the results of subproblems.
• Breadth-First Search (BFS): I used BFS to solve puzzles that required exploring all possible paths in a graph.
• Djikstra’s Algorithm: I used Djikstra’s algorithm to solve puzzles that required finding the shortest path in a weighted graph.
• A* Search Algorithm: I used the A* search algorithm as an extension of Djikstra’s algorithm to solve puzzles that required finding the shortest path in a weighted graph with a heuristic function.
• Binary Search: I used binary search to solve puzzles that required finding a specific value in a sorted list.
• Entropy: I used entropy to solve puzzles that required finding the entropy of an image.
• Permutations: I used permutations to solve puzzles that required finding all possible arrangements of a set of elements.
• Base-N Combinaions: I used base-N combinations to solve puzzles that required finding all possible combinations of a set of elements.
• Bron-Kerbosch Algorithm: I used the Bron-Kerbosch algorithm to solve puzzles that required finding all maximal cliques in a graph.
• Double-Ended Queue (Deque): I used deques to solve puzzles that required efficient insertion and deletion at both ends of a queue.
• Heap Queue: I used heap queues to solve puzzles that required maintaining a priority queue.

Results

I managed to solve all puzzles for each day of the challenge. The difficulty of the puzzles varied from simple to challenging, and I enjoyed the process of solving them. The puzzles required a combination of programming skills, problem-solving skills, and algorithmic thinking. I learned new algorithms and techniques along the way and improved my Python programming skills. The solutions I shared on Github are well-documented and can be used as a reference for solving similar problems in the future.

Story Arc

The Advent of Code challenge had a story arc that unfolded as the days went by. The story was about finding the missing Chief Historian in time for the the big Christmas sleigh launch, which he never misses. Each day we would search a different location for clues to his whereabouts, learning more about this interesting world and its inhabitants. The story added an extra layer of fun to the challenge and kept me engaged throughout the month of December. The first day story began with the following:

The Chief Historian is always present for the big Christmas sleigh launch, but nobody has seen him in months! Last anyone heard, he was visiting locations that are historically significant to the North Pole; a group of Senior Historians has asked you to accompany them as they check the places they think he was most likely to visit.

As each location is checked, they will mark it on their list with a star. They figure the Chief Historian must be in one of the first fifty places they’ll look, so in order to save Christmas, you need to help them get fifty stars on their list before Santa takes off on December 25th.

Collect stars by solving puzzles. Two puzzles will be made available on each day in the Advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!

Disclaimer

The solutions I shared on Github might not be the most optimal solutions for each puzzle, but they get the job done. I used the solutions as a way to practice my programming skills and learn new algorithms. When facing a new problem, I tried to come up with a solution on my own before looking at hints from other participants or Reddit. I have used LLMs (Large Language Models) such as ChatGPT to assist me in solving some of the puzzles and explaining the solutions in a clear and concise manner. I found this experience to be very helpful and educational, as it allowed me to learn new algorithms and techniques that I can apply in future projects. With this hands-on approach, I was able to learn much more and faster than by just reading about the algorithms.