Fifth day of December and the difficulty is ramping up a bit. I’m all for it as I’m feeling surprisingly confident this year.
This time, the elves had managed to mess up the sleigh launch safety manual updates and they were printing in incorrect order. Let’s help elves fix them, shall we!
Read input
For the first time this year, we face what I call multisection input in my code, meaning there are sections, separated by empty lines, that require different mapping functions for each section.
I have a function in my utility file for exactly this:
def read_multisection_input(day, map_fns=None, example=False):
"""
Read multisection puzzle input for file `/inputs/day_{day}.txt'
and apply transformer function to each section.
If `example` is set to True, read file `/inputs/day_{day}_example.txt`
instead
"""
try:
if example:
filename = f"day_{day}_example.txt"
else:
filename = f"day_{day}.txt"
with open(os.path.join("..", "inputs", filename)) as input_file:
sections = input_file.read().split("\n\n")
return [
transformer(section)
for section, map_fn in zip(sections, cycle(map_fns))
]
except FileNotFoundError as e:
print(e)
sys.exit(1)Its interface is similar to the read_input we’ve been using until now but instead of accepting just one map_fn, it accepts a list of them. And each map_fn now takes in a list of lines rather than a single line. Which comes handy today as we want to map the first section into a single dictionary.
The first section is the printing rules:
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|13This notation means that the number on the left side of | needs to be printed before the number on the right side.
When I read that this puzzle is about ordering, my mind immediately went to writing a custom sorting function. To do that, I need to record this order somehow.
First, I read the rules into a list of tuples of integers:
def map_rules(lines):
rules = []
for line in lines.split("\n"):
before, after = line.split("|")
rules.append((int(before), int(after)))
return rulesThe second part were the updates and the order of pages they were actually printed in:
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,47These I read into lists of integers:
def map_updates(lines):
updates = []
for line in lines.split("\n"):
updates.append([int(n) for n in line.split(",")])
return updatesPart 1
In the first part, we need to find all the correctly printed updates and sum up the page numbers of the middle pages together.
First, lets the rules into a dictionary:
def create_rules_map(rules):
rules_map = defaultdict(list)
for before, after in rules:
rules_map[before].append(after)
return rules_mapHere the keys are the left numbers and for each of them, I create a list of page numbers that needs to come after them.
I store this rule map in a global variable RULES because I couldn’t figure out another way to pass it to my custom sort function:
rules, updates = read_multisection_input(5, [map_rules, map_updates])
RULES = create_rules_map(rules)I then created a custom sorting function that I didn’t believe would be sufficient when I wrote it but it worked without any needs for changes:
def sort_by_rules(a, b):
if a in RULES:
if b in RULES[a]:
return -1
if b in RULES:
if a in RULES[b]:
return 1
else:
return 0In it, we look at the two numbers and if either of them exists as the “before” number in rules, we check if the other one should come after it and return -1 or 1 accordingly.
Now that we have the ability to sort our pages, we can check if a print order is correct by comparing the original to a sorted version:
def is_in_order(update):
s_update = sorted(update, key=functools.cmp_to_key(sort_by_rules))
return update == s_updateSince Python’s sort/sorted functions don’t accept a sort function directly, we summon the help of functools.cmp_to_key which accepts a comparison function and turns it into a class that sorted’s key argument can work with.
Sorting every list isn’t the most efficient way to solve problems but knowing that the maximum size of inputs isn’t that long in these Advent of Code solutions, we can accept this tradeoff. Remember kids, no premature optimization!
We can now filter the original updates and only pick correct ones:
correct_updates = [update for update in updates if is_in_order(update)]and calculate the sum of the middle pages:
def sum_middle_pages(updates):
total = 0
for update in updates:
mid = len(update) // 2
total += update[mid]
return totalWhen everything is put together, here’s what our part 1 solution looks like:
def part_1():
global RULES
rules, updates = read_multisection_input(5, [map_rules, map_updates])
RULES = create_rules_map(rules)
correct_updates = [update for update in updates if is_in_order(update)]
result = sum_middle_pages(correct_updates)
print(f"Part 1: {result}")The global RULES line is needed to tell Python we want to change the global variable instead of creating a new local one.
Part 2
My initial hunch served us well for the second part. Even though in the first part we only needed to care if an update was in correct order, I had a hunch that in the second part we’d also care about the ordered updates themselves.
In the second part of the puzzle, we care only about the ones that were not in the right order, need to sort them and then calculate the middle sum again.
This means we don’t need to write any new helper functions, we have everything we need!
def part_2():
global RULES
rules, updates = read_multisection_input(5, [map_rules, map_updates])
RULES = create_rules_map(rules)
corrected_updates = [
sorted(update, key=cmp_to_key(sort_by_rules))
for update in updates
if not is_in_order(update)
]
result = sum_middle_pages(corrected_updates)
print(f"Part 2: {result}")There are two changes compared to part 1:
- Our filter predicate is now
not is_in_order(update) - We sort the updates in the filter
This is even more inefficient than the previous solution because we now sort the incorrect ones twice: once when we check if they are in order and second time when we sort them for our use. Still, the inputs are small enough for this to be insignificant.
Two stars in the bag and I got both of them on the first try which surprised me. When I read through the description, I was a bit worried of the complexity. Santa’s sleigh can now be launched safely.
Appendix for improvements
First appendix of the year! I use these appendixes as postscripts if after solving the puzzle and publishing my notes, I find particularly interesting alternatives or some of my questions I had while solving are answered somewhere.
This time, there are three changes. The improved code can be found in GitHub.
The first one was my use of global RULES that I didn’t like. In the heat of fixing the printer, I didn’t figure out a way to insert a custom rules object into the comparison function. Thanks to Juha, I learned that I can do:
def create_sorter(rules):
def sort_by_rules(a, b):
if b in rules[a]:
return -1
if a in rules[b]:
return 1
else:
return 0
return sort_by_rulesand then call that as
sort_by_rules = cmp_to_key(create_sorter(rules))and pass that as the key function to the sorting function.
Getting rid of global state is always a win. Thanks Juha for the tip!
The other change is in the same function. My original sorter looked like this:
def sort_by_rules(a, b):
if a in RULES:
if b in RULES[a]:
return -1
if b in RULES:
if a in RULES[b]:
return 1
else:
return 0and I was pointed out that I’m doing extra dictionary access and since my rules dictionary is a defaultdict(list), I can skip the outer layer of ifs:
def sort_by_rules(a, b):
if b in rules[a]:
return -1
if a in rules[b]:
return 1
return 0rules[a] will return a list and if a is not a key in rules, it returns an empty list. I also got rid of the else which to be fair shouldn’t have really been there in the first place.
Makes the code so much cleaner!
The third improvement I made was to change rules from defaultdict(list) to defaultdict(set). We don’t care about the order of items in the values of rules and changing it from list to set means our a in rules[b] comparisons become more efficient.