How to solve Advent of Code 2024 - Day 5 with Python
This day is all about sorting and sequence-checking in this years's Advent of Code! 🎄❄️💻 Also I am aware of the spelling mistake in the thumbnail. I actually thought AI was doing so well with all the writing and then it messed up on the last word 😂 We all gave our best today, okay?!
But before we get right into the day and my solution for this day's puzzle, here is the info on how I approach this whole event (where my code is, what editor I use, etc):
Sarah Glasmacher
Day 5 Puzzle
On my blog here, I will go through the puzzle and my way of solving it. If you want, you can jump directly to the code solution here:
GitHub .py script
Here is the challenge, if you want to read the full puzzle:
Advent of Code 2024 - Day 5
Today's historical location is the printing facility of Advent of Code 2017 Day 1 - where the sleigh launch safety manuals are being printed. Or should be being printed, however we aren't yet sure if all the pages are in the right order to be printed, so we need to check them based on some weird sorting rules.
Part 1
Day 5 gives us two things (separated by an empty line):
- the sorting rules (
before_page|after_page) - the printing runs we should check
# Example input
47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13
75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47
Solution Approach:
I store the sorting instructions in a dict, so 97|29 and 97|75 becomes 97: [29, 75]. All the numbers that have to come before 97, so when we see a 97 we can move all those numbers from the array from the front to after the 97.
Key Code Snippets:
Read the instructions and the printing runs/orders:
def read_sorting_instructions(file_lines: list[str]) -> dict[int, list[int]]:
sorting_instructions = {}
for line in file_lines:
if "|" in line:
lower_number, upper_number = read_two_ints_from_string(line)
if lower_number not in sorting_instructions:
sorting_instructions[lower_number] = []
sorting_instructions[lower_number].append(upper_number)
return sorting_instructions
def read_printing_runs(file_lines: list[str]) -> list[list[int]]:
printing_runs = []
for line in file_lines:
if "," in line:
printing_order = [int(number) for number in line.split(",")]
printing_runs.append(printing_order)
return printing_runs
Check if all sorting instructions are followed:
def check_printing_order(
sorting_instructions: dict[int, list[int]], printing_order: list[int]
) -> bool:
for index, printing_entry in enumerate(printing_order):
if printing_entry in sorting_instructions:
if index > 0:
previous_printing_entries = printing_order[:index]
wrongly_ordered_entries = set(previous_printing_entries).intersection(
set(sorting_instructions[printing_entry])
)
if len(wrongly_ordered_entries) > 0:
return False
return True
Full Solution for Part 1:
def solve_part_1(mode: str = "example"):
file_lines = read_input_file(day=5, mode=mode)
sorting_instructions = read_sorting_instructions(file_lines)
printing_runs = read_printing_runs(file_lines)
correct_printings_middle_entries = []
for printing_order in printing_runs:
if check_printing_order(sorting_instructions, printing_order):
correct_printings_middle_entries.append(
return_middle_printing_entry(printing_order)
)
return sum(correct_printings_middle_entries)
Part 2
This time my data structure for Part 1 worked out for Part 2. Reordering the runs according to the sorting instructions was not completely surprising.
Like I said in the intro, my strategy is to move all the wrong pages at every step of the list. So we go through the list while fixing the printing order and every step has a reordering process where we append of bunch of sublists to each other:
- the remaining front-matter
- the current page we're looking at
- the pages we had to move to the back because of the sorting instructions
- the rest of the pages at the end
Overarching method for fixing a whole printing order:
def fix_printing_order(
sorting_instructions: dict[int, list[int]], printing_order: list[int]
) -> list[int]:
index = 0
while index < len(printing_order):
current_entry = printing_order[index]
if current_entry in sorting_instructions and index > 0:
previous_entries = printing_order[:index]
required_entries = set(sorting_instructions[current_entry])
wrongly_ordered_entries = set(previous_entries).intersection(
required_entries
)
if wrongly_ordered_entries:
printing_order, index = reorder_entries(
previous_entries,
current_entry,
wrongly_ordered_entries,
printing_order[index + 1 :],
)
index += 1
return printing_order
The step for pasting together sublists:
def reorder_entries(
previous_entries: list[int],
current_entry: int,
wrongly_ordered_entries: set[int],
remaining_entries: list[int],
) -> tuple[list[int], int]:
correct_entries = [
entry for entry in previous_entries if entry not in wrongly_ordered_entries
]
reordered_entries = [
entry for entry in previous_entries if entry in wrongly_ordered_entries
]
new_order = (
correct_entries + [current_entry] + reordered_entries + remaining_entries
)
new_index = len(correct_entries) - 1
return new_order, new_index
Full Solution for Part 2:
def solve_part_2(mode: str = "example"):
file_lines = read_input_file(day=5, mode=mode)
sorting_instructions = read_sorting_instructions(file_lines)
printing_runs = read_printing_runs(file_lines)
incorrect_printings_middle_entries = []
for printing_order in printing_runs:
if not check_printing_order(sorting_instructions, printing_order):
fixed_printing_order = fix_printing_order(
sorting_instructions, printing_order
)
incorrect_printings_middle_entries.append(
return_middle_printing_entry(fixed_printing_order)
)
return sum(incorrect_printings_middle_entries)
Conclusion
I should be drawing an image for the slicing and reordering of the list I do, because if you don't "see" the solution in your head, the code is probably a mess to understand. I gave my best in refactoring it into meaningful functions, so I hope that helps.
It's 4am and I need to go to sleep soon, so no drawing here, sorry.