Advent of Code 2024
Sorry for the horrible AI generated art. I’ll probably replace it eventually.
In past years, I’ve been aware of but never participated in Advent of Code. This year, I would like to give it a shot. I’m posting my solutions here well after the problems come out so I don’t have to worry about spoilers for people competing on the leaderboard. I’m not going to fully reproduce the problems here, but I will summarize them before my solutions.
I’m also publishing this page before everything is complete. I’ll be adding to it as I go, but the date of this post is the date it was originally published. I’ll come back and edit it after the challenge is over.
Table of Contents
- Day 1: Historian Hysteria
- Day 2: Red-Nosed Reports
- Day 3: Mull it Over
- Day 4: Ceres Search
- Day 5
- Day 6
- Day 7
- Day 8
- Day 9
- Day 10
- Day 11
- Day 12
- Day 13
- Day 14
- Day 15
- Day 16
- Day 17
- Day 18
- Day 19
- Day 20
- Day 21
- Day 22
- Day 23
- Day 24
- Day 25
Day 1: Historian Hysteria
Problem 1
For this problem, we’re given two lists of numbers. We need to pair up the numbers from the two lists and calculate the total “distance” between the two lists. The distance between two numbers is the absolute difference between the two numbers. Example:
3 4
4 3
2 5
1 3
3 9
3 3
We have to pair up the numbers starting with the smallest number in the left list and the smallest number in the right list, then the second-smallest left number with the second-smallest right number, and so on. Within each pair, figure out how far apart the two numbers are; we need to add up all of those distances.
absolute values
1-3 = 2
2-3 = 1
3-3 = 0
3-4 = 1
3-5 = 2
4-9 = 5
Total distance = 2 + 1 + 0 + 1 + 2 + 5 = 11
My instinct was to sort both lists, then do something like zip them together and calculate the distance. Here’s the Python version I used to solve it (the file location_ids.txt is in the same directory as the Python file):
# Read the file
with open('location_ids.txt') as locations_file:
# Parse into lists
left_locations = []
right_locations = []
text = locations_file.read()
lines = text.split("\n")
for line in lines:
tmp_line = line.split(" ")
if(len(tmp_line) > 1):
left_locations.append(int(tmp_line[0]))
right_locations.append(int(tmp_line[3]))
# Sort lists
left_locations.sort()
right_locations.sort()
# Get the distances
distances = []
zipped_locations = zip(left_locations, right_locations)
for left_location, right_location in zipped_locations:
distances.append(abs(left_location - right_location))
# Calculate result
print(sum(distances))
Problem 2
This problem uses the same input as Problem 1, but now we’re calculating the similarity between the lists instead of the distance. Similarity score is calculated by “adding up each number in the left list after multiplying it by the number of times that number appears in the right list”. Example:
3 4
4 3
2 5
1 3
3 9
3 3
(3*3) + (4*1) + (2*0) + (1*0) + (3*3) + (3*3) = 9 + 4 + 0 + 0 + 9 + 9 = 31
With this one, most of it was solved by reusing the code from problem 1. Basically I just looped through and summed the similarity score.
# Read the file
with open('location_ids.txt') as locations_file:
# Parse into lists
left_locations = []
right_locations = []
text = locations_file.read()
lines = text.split("\n")
for line in lines:
tmp_line = line.split(" ")
if(len(tmp_line) > 1):
left_locations.append(int(tmp_line[0]))
right_locations.append(int(tmp_line[3]))
# Count the location overlaps & calculate score
similarity_score = 0
for left_location in left_locations:
location_count = right_locations.count(left_location)
similarity_score += location_count * left_location
print(similarity_score)
Day 2: Red-Nosed Reports
Problem 1
The unusual data (your puzzle input) consists of many reports, one report per line. Each report is a list of numbers called levels that are separated by spaces. For example:
7 6 4 2 1
1 2 7 8 9
9 7 6 2 1
1 3 2 4 5
8 6 4 4 1
1 3 6 7 9
This example data contains six reports each containing five levels.
The engineers are trying to figure out which reports are safe. a report only counts as safe if both of the following are true:
- The levels are either all increasing or all decreasing.
- Any two adjacent levels differ by at least one and at most three.
In the example above, the reports can be found safe or unsafe by checking those rules:
7 6 4 2 1: Safe because the levels are all decreasing by 1 or 2.
1 2 7 8 9: Unsafe because 2 7 is an increase of 5.
9 7 6 2 1: Unsafe because 6 2 is a decrease of 4.
1 3 2 4 5: Unsafe because 1 3 is increasing but 3 2 is decreasing.
8 6 4 4 1: Unsafe because 4 4 is neither an increase or a decrease.
1 3 6 7 9: Safe because the levels are all increasing by 1, 2, or 3.
So for this one, I basically looped through the reports checking the conditions:
# Check for large increases
def is_safe(report_1, report_2):
difference = abs(report_1 - report_2)
if difference > 0 and difference < 4:
return True
return False
with open("input.txt") as file:
safe_reports_count = 0
unsafe_reports_count = 0
reports_file = file.read().split("\n")
reports = [x for x in reports_file if x]
for line in reports:
report = line.split(" ")
# Sorting check doesn't work properly if they aren't integers
report = list(map(int, report))
# Check if the report is sorted (i.e. trending up or down)
if (sorted(report) != report) and (sorted(report, reverse=True) != report):
continue
# Check if the report has duplicate entries
if len(report) != len(set(report)):
continue
unsafe = False
# Call is_safe() to check for large increases
for level in range(1, len(report)):
if not is_safe(int(report[level-1]), int(report[level])):
unsafe = True
if unsafe:
continue
safe_reports_count += 1
print(safe_reports_count)
I had a couple of small hangups on this one. The main one that was throwing me was that I forgot to convert the reports to integers instead of strings. Strings sort ‘12’ before ‘9’, and there were a pretty small number of cases where this happened, so it wasn’t easy to track down.
Also I know using the sets to check for duplication isn’t strictly necessary, since it would also be checked by is_safe(), but I wanted to call that function as few times as possible.
Problem 2
This adds to the first problem a single “freebie” level - if there’s only a single value that is causing a report to be unsafe, it’s considered safe anyway. Unfortunately, the way I structured my solution before makes this one a bit difficult to reuse directly. I did some refactoring and basically iterated through each unsafe report, pulling out a value at a time and retesting.
def contains_large_jumps(report):
large_jump = False
for level in range(1, len(report)):
difference = abs(report[level-1] - report[level])
if difference <= 0 or difference >= 4:
large_jump = True
# print("Unsafe - large jumps: ")
# print(report)
return large_jump
def is_ordered(report):
if (sorted(report) != report) and (sorted(report, reverse=True) != report):
# print("Unsafe - not ordered: ")
# print(report)
return False
return True
def contains_duplicates(report):
if len(report) != len(set(report)):
# print("Unsafe - duplicate level: ")
# print(report)
return True
return False
def problem_dampened(report):
for i in range(len(report)):
level = report[i]
report.pop(i)
if (not contains_large_jumps(report)) and is_ordered(report) and (not contains_duplicates(report)):
return True
report.insert(i, level)
return False
with open("input.txt") as file:
safe_reports_count = 0
new_safe_reports_count = 0
reports_file = file.read().split("\n")
reports = [x for x in reports_file if x]
for line in reports:
report = list(map(int, line.split(" ")))
if (not contains_large_jumps(report)) and is_ordered(report) and (not contains_duplicates(report)):
# print("Safe report:")
# print(report)
safe_reports_count += 1
continue
# If it's unsafe, need to iterate through pulling out the levels one by one and retesting
if problem_dampened(report):
safe_reports_count += 1
print(safe_reports_count)
Day 3: Mull it Over
Problem 1
This problem gives us strings of multiplication instructions with extra characters mixed in. We need to figure out which instructions are valid, multiply them, and then sum the results.
Example:
xmul(2,4)%&mul[3,7]!@^do_not_mul(5,5)+mul(32,64]then(mul(11,8)mul(8,5))
should become
mul(2,4)
mul(5, 5)
mul(11,8)
mul(8,5)
Which is
(2*4) + (5*5) + (11*8) + (8*5) = 8 + 25 + 88 + 40 = 161
This seemed like a good job for regex, so I paid a little visit to Regex 101 to make sure I built it correctly.
import re
with open("input.txt") as file:
regex = r"mul\([0-9]+,[0-9]+\)"
str = file.read()
matches = re.findall(regex, str, re.MULTILINE)
mul_accumulator = 0
for match in matches:
nums = match.split("(")[1].split(")")[0].split(",")
mul_accumulator += (int(nums[0]) * int(nums[1]))
print(mul_accumulator)
Problem 2
The second problem for day 3 adds a conditional “do()” or “don’t()” instruction to the previous multiplication instructions. So as we read the instructions, if we see a “do()”, we start (or continue) summing the multiplication instructions. But if we see a “don’t()”, then we need to skip all multiplication instructions until we see another “do()“. We assume that we start with “do()” enabled.
Example:
xmul(2,4)&mul[3,7]!^don't()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5))
should become
mul(2,4)
don't()
do()
mul(8,5)
Which gives us
(2*4) + (8*5) = 8 + 40 = 48
This one was a good candidate for reuse from the first problem. It just required a little bit of tweaking.
import re
with open("input.txt") as file:
regex = r"mul\([0-9]+,[0-9]+\)|do\(\)|don't\(\)"
str = file.read()
matches = re.findall(regex, str, re.MULTILINE)
mul_accumulator = 0
do = True
for match in matches:
if match == "do()":
print("do match: ")
print(match)
do = True
continue
if match == "don't()":
print("don't match: ")
print(match)
do = False
continue
if do:
nums = match.split("(")[1].split(")")[0].split(",")
mul_accumulator += (int(nums[0]) * int(nums[1]))
else:
continue
print(mul_accumulator)
Day 4: Ceres Search
Problem 1
This problem was essentially a word search. Given a matrix of text, find all instances (forwards and backwards in all directions, including overlapping) of the word “XMAS”.
I wanted to do this one without using NumPy or anything outside the standard libraries, so this one took me a little while. I recommend just using NumPy if you’re doing this though - it makes dealing with the diagonals much easier.
I built a solution and it worked on the example input, but then didn’t work on the input file. So I scrapped it and started over, writing tests to see where things were going wrong. Part of it ended up being the way I was using count(), which doesn’t catch overlapping instances (e.g. “SAMXMAS” should be 2) and my diagonal search wasn’t working correctly. So here’s what I ended up with that gave me the right answer:
ceres_search_1.py
import re
def line_scan(text_list, search_text):
search_text_count = 0
regex = rf"(?=({re.escape(search_text)}))"
search_text_count += len(re.findall(regex, "".join(text_list)))
search_text_count += len(re.findall(regex, "".join(text_list[::-1])))
return search_text_count
def build_diagonal_indices(matrix, direction):
indices_list = []
for row_index, row in enumerate(matrix):
for column_index, column in enumerate(row):
if direction == "declining":
if row_index == 0 or column_index == 0:
indices_list.append((row_index, column_index))
elif direction == "inclining":
if column_index == 0 or row_index == len(matrix)-1:
indices_list.append((row_index, column_index))
else:
return 0
return indices_list
def build_declining_diagonals(matrix, indices_list):
declining_diagonals = []
for diagonal_index, index_pair in enumerate(indices_list):
row_index = index_pair[0]
column_index = index_pair[1]
declining_diagonals.append([])
while (0 <= row_index < len(matrix) and 0 <= column_index < len(matrix[0])):
declining_diagonals[diagonal_index].append(matrix[row_index][column_index])
row_index += 1
column_index += 1
return declining_diagonals
def build_inclining_diagonals(matrix, indices_list):
inclining_diagonals = []
for diagonal_index, index_pair in enumerate(indices_list):
row_index = index_pair[0]
column_index = index_pair[1]
inclining_diagonals.append([])
while(0 <= row_index < len(matrix) and 0 <= column_index < len(matrix[0])):
inclining_diagonals[diagonal_index].append(matrix[row_index][column_index])
row_index -= 1
column_index += 1
return inclining_diagonals
def get_lines_from_matrix(matrix):
# gets horizontal, vertical, inclining diagonal, and declining diagonal lines
# returns them joined in a single list
lines_from_matrix = []
vertical_lines = []
for row in matrix:
lines_from_matrix.append(row)
for column_index, column in enumerate(row):
if 0 <= column_index < len(vertical_lines):
vertical_lines[column_index].append(column)
else:
vertical_lines.append(list(column))
declining_diagonals = build_declining_diagonals(matrix, build_diagonal_indices(matrix, "declining"))
inclining_diagonals = build_inclining_diagonals(matrix, build_diagonal_indices(matrix, "inclining"))
for line in vertical_lines:
lines_from_matrix.append(line)
for line in declining_diagonals:
lines_from_matrix.append(line)
for line in inclining_diagonals:
lines_from_matrix.append(line)
return lines_from_matrix
matrix = []
with open("input.txt") as file:
word_search_text = file.read()
for line in word_search_text.split("\n"):
matrix.append(list(line))
xmas_count = 0
lines = get_lines_from_matrix(matrix)
for line in lines:
xmas_count += line_scan(line, "XMAS")
print(xmas_count)
test_ceres_search_1.py
import ceres_search_1 as cs
matrix_2x2 = [['a','b'],['c','d']]
matrix_2x3 = [['a','b','c'],['d','e','f']]
matrix_3x2 = [['a','b'],['c','d'],['e','f']]
declining_indices_2x2 = [(0, 0), (0, 1), (1, 0)]
declining_indices_2x3 = [(0, 0), (0, 1), (0, 2), (1, 0)]
declining_indices_3x2 = [(0, 0), (0, 1), (1, 0), (2, 0)]
inclining_indices_2x2 = [(0, 0), (1, 0), (1, 1)]
inclining_indices_2x3 = [(0, 0), (1, 0), (1, 1), (1, 2)]
inclining_indices_3x2 = [(0, 0), (1, 0), (2, 0), (2, 1)]
def test_line_scan():
assert cs.line_scan(['t','e','s','t'], "test") == 1
assert cs.line_scan(['t','e','s','t','t','e','s','t'], "test") == 2
assert cs.line_scan(['t','e','s','t','e','s','t'], "test") == 2
assert cs.line_scan([], "test") == 0
assert cs.line_scan(['t','e','s','t','t','s','e','t'], "test") == 2
def test_get_lines_from_matrix():
# horizontal
assert (['a','b'] in cs.get_lines_from_matrix(matrix_2x2))
assert (['c','d'] in cs.get_lines_from_matrix(matrix_2x2))
# vertical
assert (['a','c'] in cs.get_lines_from_matrix(matrix_2x2))
assert (['b','d'] in cs.get_lines_from_matrix(matrix_2x2))
# declining diagonals
assert (['c'] in cs.get_lines_from_matrix(matrix_2x2))
assert (['a','d'] in cs.get_lines_from_matrix(matrix_2x2))
assert (['b'] in cs.get_lines_from_matrix(matrix_2x2))
# inclining diagonals
assert (['a'] in cs.get_lines_from_matrix(matrix_2x2))
assert (['c','b'] in cs.get_lines_from_matrix(matrix_2x2))
assert (['d'] in cs.get_lines_from_matrix(matrix_2x2))
def test_build_diagonal_indices():
#test 2x2 declining
assert ((0, 0) in cs.build_diagonal_indices(matrix_2x2, "declining"))
assert ((0, 1) in cs.build_diagonal_indices(matrix_2x2, "declining"))
assert ((1, 0) in cs.build_diagonal_indices(matrix_2x2, "declining"))
assert len(cs.build_diagonal_indices(matrix_2x2, "declining")) == 3
#test 2x2 inclining
assert ((0, 0) in cs.build_diagonal_indices(matrix_2x2, "inclining"))
assert ((1, 0) in cs.build_diagonal_indices(matrix_2x2, "inclining"))
assert ((1, 1) in cs.build_diagonal_indices(matrix_2x2, "inclining"))
assert len(cs.build_diagonal_indices(matrix_2x2, "inclining")) == 3
# test 2x3 declining
assert ((0, 0) in cs.build_diagonal_indices(matrix_2x3, "declining"))
assert ((0, 1) in cs.build_diagonal_indices(matrix_2x3, "declining"))
assert ((0, 2) in cs.build_diagonal_indices(matrix_2x3, "declining"))
assert ((1, 0) in cs.build_diagonal_indices(matrix_2x3, "declining"))
assert len(cs.build_diagonal_indices(matrix_2x3, "declining")) == 4
# test 2x3 inclining
assert ((0, 0) in cs.build_diagonal_indices(matrix_2x3, "inclining"))
assert ((1, 0) in cs.build_diagonal_indices(matrix_2x3, "inclining"))
assert ((1, 1) in cs.build_diagonal_indices(matrix_2x3, "inclining"))
assert ((1, 2) in cs.build_diagonal_indices(matrix_2x3, "inclining"))
assert len(cs.build_diagonal_indices(matrix_2x3, "inclining")) == 4
# test 3x2
assert ((0, 0) in cs.build_diagonal_indices(matrix_3x2, "declining"))
assert ((0, 1) in cs.build_diagonal_indices(matrix_3x2, "declining"))
assert ((1, 0) in cs.build_diagonal_indices(matrix_3x2, "declining"))
assert ((2, 0) in cs.build_diagonal_indices(matrix_3x2, "declining"))
assert len(cs.build_diagonal_indices(matrix_3x2, "declining")) == 4
# test 3x2 inclining
assert ((0, 0) in cs.build_diagonal_indices(matrix_3x2, "inclining"))
assert ((1, 0) in cs.build_diagonal_indices(matrix_3x2, "inclining"))
assert ((2, 0) in cs.build_diagonal_indices(matrix_3x2, "inclining"))
assert ((2, 1) in cs.build_diagonal_indices(matrix_3x2, "inclining"))
assert len(cs.build_diagonal_indices(matrix_3x2, "inclining")) == 4
def test_build_declining_diagonals():
# test 2x2
assert (['a','d'] in cs.build_declining_diagonals(matrix_2x2, declining_indices_2x2))
assert (['b'] in cs.build_declining_diagonals(matrix_2x2, declining_indices_2x2))
assert (['c'] in cs.build_declining_diagonals(matrix_2x2, declining_indices_2x2))
assert len(cs.build_declining_diagonals(matrix_2x2, declining_indices_2x2)) == 3
# test 2x3
assert (['a','e'] in cs.build_declining_diagonals(matrix_2x3, declining_indices_2x3))
assert (['b','f'] in cs.build_declining_diagonals(matrix_2x3, declining_indices_2x3))
assert (['c'] in cs.build_declining_diagonals(matrix_2x3, declining_indices_2x3))
assert (['d'] in cs.build_declining_diagonals(matrix_2x3, declining_indices_2x3))
assert len(cs.build_declining_diagonals(matrix_2x3, declining_indices_2x3)) == 4
# test 3x2
assert (['a', 'd'] in cs.build_declining_diagonals(matrix_3x2, declining_indices_3x2))
assert (['b'] in cs.build_declining_diagonals(matrix_3x2, declining_indices_3x2))
assert (['c','f'] in cs.build_declining_diagonals(matrix_3x2, declining_indices_3x2))
assert (['e'] in cs.build_declining_diagonals(matrix_3x2, declining_indices_3x2))
assert len(cs.build_declining_diagonals(matrix_3x2, declining_indices_3x2)) == 4
def test_build_inclining_diagonals():
# test 2x2
assert (['a'] in cs.build_inclining_diagonals(matrix_2x2, inclining_indices_2x2))
assert (['c','b'] in cs.build_inclining_diagonals(matrix_2x2, inclining_indices_2x2))
assert (['d'] in cs.build_inclining_diagonals(matrix_2x2, inclining_indices_2x2))
assert len(cs.build_inclining_diagonals(matrix_2x2, inclining_indices_2x2)) == 3
# test 2x3
assert (['a'] in cs.build_inclining_diagonals(matrix_2x3, inclining_indices_2x3))
assert (['d','b'] in cs.build_inclining_diagonals(matrix_2x3, inclining_indices_2x3))
assert (['e','c'] in cs.build_inclining_diagonals(matrix_2x3, inclining_indices_2x3))
assert (['f'] in cs.build_inclining_diagonals(matrix_2x3, inclining_indices_2x3))
assert len(cs.build_inclining_diagonals(matrix_2x3, inclining_indices_2x3)) == 4
# test 3x2
assert (['a'] in cs.build_inclining_diagonals(matrix_3x2, inclining_indices_3x2))
assert (['c','b'] in cs.build_inclining_diagonals(matrix_3x2, inclining_indices_3x2))
assert (['e','d'] in cs.build_inclining_diagonals(matrix_3x2, inclining_indices_3x2))
assert (['f'] in cs.build_inclining_diagonals(matrix_3x2, inclining_indices_3x2))
assert len(cs.build_inclining_diagonals(matrix_3x2, inclining_indices_3x2)) == 4
Problem 2
This changes the search from all instances to X-shaped instances of “MAS”. (XMAS to X-MAS). Unfortunately, my previous code wouldn’t be too useful. I could have potentially adapted the diagonal searches to search for “MAS”, and then with the indices of the “A” in each diagonal “MAS” check the other direction for another “MAS”, but I wasn’t really happy with my previous solution anyway. It works, but it isn’t pretty. This one is a bit better, but still not great.
# convert the text into a 2d matrix
def convert_text_to_matrix(text):
matrix = []
for line in text.split("\n"):
matrix.append(list(line))
return matrix
# if the center of the sliding window is "A", check for a match
def mas_match_check(sliding_window):
if sliding_window[1][1] != 'A':
return False
if sliding_window[0][0] != 'M' and sliding_window[0][0] != 'S':
return False
if sliding_window[0][2] != 'M' and sliding_window[0][2] != 'S':
return False
if sliding_window[2][0] != 'M' and sliding_window[2][0] != 'S':
return False
if sliding_window[2][2] != 'M' and sliding_window[2][2] != 'S':
return False
if sliding_window[0][0] == 'M' and sliding_window[2][2] != 'S':
return False
if sliding_window[0][0] == 'S' and sliding_window[2][2] != 'M':
return False
if sliding_window[2][0] == 'M' and sliding_window[0][2] != 'S':
return False
if sliding_window[2][0] == 'S' and sliding_window[0][2] != 'M':
return False
return True
with open("input.txt") as file:
word_search_text = file.read()
matrix = convert_text_to_matrix(word_search_text)
xmas_count = 0
for row_index, row in enumerate(matrix):
for column_index, column in enumerate(row):
if column == 'A':
if (0 <= (row_index - 1) and
(row_index + 2) <= len(matrix) and
0 <= (column_index - 1) and
(column_index + 2) <= len(row)):
sliding_window = [
[matrix[row_index-1][column_index-1], matrix[row_index-1][column_index], matrix[row_index-1][column_index+1]],
[matrix[row_index][column_index-1], matrix[row_index][column_index], matrix[row_index][column_index+1]],
[matrix[row_index+1][column_index-1], matrix[row_index+1][column_index], matrix[row_index+1][column_index+1]]]
print(sliding_window)
if mas_match_check(sliding_window) == True:
xmas_count += 1
print(xmas_count)