How to solve Advent of Code 2022 - Day 13 with Python
If you missed any previous days, click here for all my content about that: Advent of Code, if you want to know why you should participate and try to code the solution for yourself, click here: Advent Of Code 2022 – 7 Reasons why you should participate. If you're here to see the solution of Day 13, continue reading ;)
GitHub Repository
https://github.com/GalaxyInfernoCodes/Advent_Of_Code_2022
I will upload all of my solutions there - in the form of Python (or Scala alternatives) notebooks. You have to use your own input for the "input.txt" since everyone gets their own and everyone needs to provide a different solution based on their input.
Day 13 Puzzle
On day 13 of Advent of Code, we had to order/compare lists of lists of lists of lists... you get the idea. Here are some examples from the type of input we could expect. Honestly, this is cursed. I can't imagine a scenario where I would need to code this aside from this puzzle. But okay, let's get started.
[1,1,3,1,1]
[1,1,5,1,1]
[[1],[2,3,4]]
[[1],4]
[[4,4],4,4]
[[4,4],4,4,4]
[7,7,7,7]
[7,7,7]
[]
[3]
[[[]]]
[[]]
[1,[2,[3,[4,[5,6,7]]]],8,9]
[1,[2,[3,[4,[5,6,0]]]],8,9]
As always, I read in all lines:
with open('input.txt', 'r') as f:
lines = f.readlines()
lines = [entry.strip() for entry in lines]
The rules
This seems to me like one of the puzzles where understanding the rules and all their details (made up by our best friends, the elves) is 80% of the solution. So let's take some time here.
Goal: decide if list_a < list_b. But "smaller" is very carefully defined.
- we always compare just one value of each list, starting at the first
- if that is already smaller, list_a is smaller than list_b
[1,...] < [2,...] # no matter what comes after
Conversions:
If we would need to compare a list with an integer, we convert the integer to a list:
[1,...] < [[2, 3],...]
# will be converted to
[[1],...] <[2, 3],...]
If both first entries are a list, we now apply the same rules to these nested lists. I solved this recursively (but remember, you can rewrite every recursive algorithm to an iterative one if you don't like recursion).
If both entries are integers, we just compare the integers.
- if they are different, we have our answer
- if they are the same however, we need to take the next entries of the current lists we're looking at and start fresh with those
If one lists runs out of entries first, then that is the "smaller" one.
Note: this is the final comparison needed, there are apparently no pairs in the puzzle that are completely the same. One will always be smaller than the other.
The comparison function
What can this look like in code?
I remove an entry from each list with .pop(0), which returns the first entry in the list and removes it from the list at the same time. For that to work neither of the two lists can be empty, so that's my loop-condition.
Then we go over the 4 cases:
- int and int (compare numbers directly and return result unless they are the same - we'll deal with this later)
- list and list (recursively call the function with those sub-lists and use that result, again return it if one list is smaller as we have our answer then)
- list and int OR int and list. In that case convert the int into a list and then call the function recursively like in the case above
If we get the answer that the entries are the same, we progress to the next entry. This means running the loop again, where we will pop an entry from the front of each list.
If that fails and our while condition is false, then at least one list is empty. The list that is empty first will be the "smaller" one by this comparison, so we can return an answer. In comparison within some list of lists deep inside, the entries can be the same. Our final outer function call should never return 0 however.
"""Note: my function returns -1 if the first list is bigger, 1 if the second list is bigger, 0 if they are the same (in the case of recursions this can happen, but not on the final outer comparison)"""
def compare_lists(first, second):
#print('compare lists')
while len(first) > 0 and len(second) > 0:
left = first.pop(0)
right = second.pop(0)
#print(f"{left=}, {right=}")
if type(left) == int and type(right) == int:
if left < right:
return 1
elif left > right:
return -1
if type(left) == list and type(right) == list:
sub_comparison = compare_lists(left, right)
if sub_comparison != 0:
return sub_comparison
if type(left) == int and type(right) == list:
sub_comparison = compare_lists(list([left]), right)
if sub_comparison != 0:
return sub_comparison
if type(left) == list and type(right) == int:
sub_comparison = compare_lists(left, list([right]))
if sub_comparison != 0:
return sub_comparison
#print('compare lengths', f"{first=}, {second=}")
if len(first) < len(second):
return 1
elif len(first) > len(second):
return -1
else:
return 0
Part 1
This is fairly simple now using the above function. We go through the lines and and always take out two (plus the following empty line, except for the last iteration possibly) to compare those two.
The only nice trick is using eval. Eval is a built-in Python function that accepts a string and turns it into code and interprets it as such. For example:
eval("sorted([1, 3, 2])") # returns: [1, 2, 3]
We use this here to get lists returned for each line. But be careful with this eval command! If you don't carefully monitor your inputs, your script will run all sorts of malicious stuff that you read in. Here is a cautionary meme about this from reddit.
Anways, we then compare with our function and track all the indices of pairs were the first list is smaller than the second (our function returns 1 for that). Then simply add those indices together.
def solve1(file):
with open(file, 'r') as f:
lines = f.readlines()
lines = [entry.strip() for entry in lines]
index = 1
indices = []
while len(lines) > 0:
list_a = eval(lines.pop(0))
list_b = eval(lines.pop(0))
if len(lines) > 0:
lines.pop(0)
comparison = compare_lists(list_a, list_b)
if comparison == 1:
indices.append(index)
index += 1
print(indices)
print(sum(indices))
Part 2
Here we don't compare the pairs, instead we need to decide the position of [[2]] and [[6]] within all our inputs (no longer grouped as pairs, but each on its own).
Note: you don't need to sort all the values, you just need to know the position of [[2]] an [[6]] within the sorted list. That is the same as counting, how many entries are smaller than [[2]] (+ 1 to get the index of [[2]], which for some reason starts counting at 1). Same for [[6]] except + 2, because [[2]] is smaller than [[6]] as well, but we don't compare them directly.
So that's what I did. Go through the lines one by one, if it's empty just go to the next line. If it's a proper line, see if it's smaller than [[2]] and/or smaller than [[6]] and if yes, increase a counter.
The only thing that tripped me up was that my .pop(0) in the comparison function changes my list, so if I want to use it again in the second comparison with [[6]], I need to make a deepcopy of the list beforehand.
def solve2(file):
with open(file, 'r') as f:
lines = f.readlines()
lines = [entry.strip() for entry in lines]
smaller_than_2 = 0
smaller_than_6 = 0
while len(lines) > 0:
line = lines.pop(0)
if len(line) == 0:
continue
list_from_file = eval(line)
if compare_lists(deepcopy(list_from_file), [[2]]) == 1:
smaller_than_2 += 1
if compare_lists(deepcopy(list_from_file), [[6]]) == 1:
smaller_than_6 += 1
position_of_2 = smaller_than_2 + 1
position_of_6 = smaller_than_6 + 2
print(f"{position_of_2=}, {position_of_6=}")
print(position_of_2 * position_of_6)
For the solution, multiply those two indices together.
Conclusion
Like I said, this is cursed.
If you need practice in reading definitions carefully, fine, this puzzle will give you that.
I learned some things about lists though. For example, you can't turn an integer into a list like this:
list(5) # won't work!!
list([5]) # this gives you [5] though as desired
So I guess it wasn't completely in vain. Did I enjoy it though? No. :D