Learning Python with Advent of Code Walkthroughs
Dazbo's Advent of Code solutions, written in Python
Advent of Code 2022 - Day 13
Useful Links
Concepts and Packages Demonstrated
classesrecursionlist comprehensionzipenumerateliteral_eval
Page Navigation
Problem Intro
I enjoyed this one! It took me an an hour.
We’re given input packets, arranged in pairs. They look something like this:
[1,1,3,1,1]
[1,1,5,1,1]
[[1],[2,3,4]]
[[1],4]
[9]
[[8,7,6]]
[[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]
We can see that each packet in the pair represents a list, an int, where the lists can themselves contain either list or int. This is a strong hint that we might need recursion!
We’re given a set of rules for how we can compare the items in each pair, to see which one is smaller.
Part 1
How many pairs are in the right order?
My strategy for this is pretty simple:
- Read in each packet using
ast.literal_eval(). This is a Python standard module function which provides the ability to parse and evaluate any string input data, and - so long as the input data looks like a standard Python data type - then return that data type! Here I’m using it to read in the data aslistorint. - Create a
Packetclass that stores this value, and which implements the less than operator,__lt__(). Overriding this operator is the Python standard approach for comparing one item to another.- The lt() method compares self with other.
- The implementation of this method follows the rules we’ve been given.
- It is recursive: the base case is when we’re comparing
intvalues. Otherwise, we’re either converting aninton one side to alistand comparing, or iterating over alistand comparing.
- Create a
Pairclass to store left and right Packets. To be honest, this is kind of unnecessary, but it makes it all quite readable. - Finally, for each pair, compare and count how many times left is less than right.
Here’s how I read the data:
def get_pairs(data: str) -> list[Pair]:
pairs: list[Pair] = []
blocks = data.split("\n\n") # split into blocks
for block in blocks:
lines = block.splitlines()
pairs.append(Pair(Packet(literal_eval(lines[0])), Packet(literal_eval(lines[1]))))
return pairs
Here’s my Packet class:
class Packet():
""" Sortable. Packet is made up of a value which is either a list or an int.
Lists can contain other lists. """
def __init__(self, value) -> None:
self.value = value
def __lt__(self, other: Packet) -> bool:
# Base case - both are ints
if isinstance(self.value, int) and isinstance(other.value, int):
if self.value < other.value:
return True
if other.value < self.value:
return False
# if one int and one list
if isinstance(self.value, int) and isinstance(other.value, list):
new_item = Packet([self.value]) # convert this int to list
return new_item < other
if isinstance(self.value, list) and isinstance(other.value, int):
new_item = Packet([other.value]) # convert other int to list
return self < new_item
# both are lists
if isinstance(self.value, list) and isinstance(other.value, list):
# take each item and compare it. Zip will stop when it reaches the end of either list
compare_count = 0
for val in zip(self.value, other.value):
compare_count += 1
if val[0] == val[1]:
continue # if the same, continue to next item
return Packet(val[0]) < Packet(val[1])
# If we're here, then the iterator terminated before finding a difference
return len(self.value) < len(other.value)
def __repr__(self) -> str:
return str(self.value)
Notes:
- I only need to implement the
__init__()and__lt__()methods! - The
__lt__()method is how we implement less than. It compares self to other. This is all we need to do in order to implement the<operator, and to make an object sortable. - When we need to compare one
listwith another, I’m using zip in order to zip each pair of packets together. If either list runs out before we’ve finished the comparison of the items, then all we need to do is compare thelistlengths, as required by our rules.
Here’s my Pair class:
class Pair():
""" Contains two items: left and right """
def __init__(self, left: Packet, right: Packet) -> None:
self.left = left
self.right = right
def __repr__(self):
return f"Pair(l={self.left}, r={self.right})"
Nothing much to say about that!
And finally, we can solve the problem:
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read()
# Part 1
pairs = get_pairs(data)
right_order = []
for i, pair in enumerate(pairs, start=1):
print(f"{i}, {pair}")
if pair.left < pair.right:
right_order.append(i)
print(f"Part 1 = {sum(right_order)}")
Part 2
Now we need to ignore pairs, and instead, get all the packets. We’re told we need to:
- Add two special ‘divider’ packets
- Sort the entire list
- Find the locations of the two divider packets, after sorting. Get their product.
Well, this is really easy for us, since we’ve done almost all the work already! Since we’ve made our Packet class sortable already, then we can just pass a list of our packets to sorted(), and we’re done with the sorting!!
First, let’s read in the data again, but ignoring blocks / pairs:
def get_all_packets(data: str) -> list[Packet]:
lines = data.splitlines()
return [Packet(literal_eval(line)) for line in lines if line]
Here I’m using a list comprehension to return a Packet constructed from each line read. But if the line is empty, we ignore it in the comprehension.
And now to solve for Part 2:
# Part 2
all_packets = get_all_packets(data)
div_two, div_six = Packet([[2]]), Packet([[6]]) # Add divider packets
all_packets.append(div_two)
all_packets.append(div_six)
sorted_items = sorted(all_packets)
loc_div_two = sorted_items.index(div_two) + 1 # Our indexes are 1-based, not 0.
loc_div_six = sorted_items.index(div_six) + 1
print(f"Part 2 = {loc_div_two*loc_div_six}")
Phew, that was easy!
Results
Here’s the final code:
from __future__ import annotations
from pathlib import Path
import time
from ast import literal_eval
SCRIPT_DIR = Path(__file__).parent
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
class Packet():
""" Sortable. Packet is made up of a value which is either a list or an int.
Lists can contain other lists. """
def __init__(self, value) -> None:
self.value = value
def __lt__(self, other: Packet) -> bool:
# Base case - both are ints
if isinstance(self.value, int) and isinstance(other.value, int):
if self.value < other.value:
return True
if other.value < self.value:
return False
# if one int and one list
if isinstance(self.value, int) and isinstance(other.value, list):
new_item = Packet([self.value]) # convert this int to list
return new_item < other
if isinstance(self.value, list) and isinstance(other.value, int):
new_item = Packet([other.value]) # convert other int to list
return self < new_item
# both are lists
if isinstance(self.value, list) and isinstance(other.value, list):
# take each item and compare it. Zip will stop when it reaches the end of either list
compare_count = 0
for val in zip(self.value, other.value):
compare_count += 1
if val[0] == val[1]:
continue # if the same, continue to next item
return Packet(val[0]) < Packet(val[1])
# If we're here, then the iterator terminated before finding a difference
return len(self.value) < len(other.value)
def __repr__(self) -> str:
return str(self.value)
class Pair():
""" Contains two items: left and right """
def __init__(self, left: Packet, right: Packet) -> None:
self.left = left
self.right = right
def __repr__(self):
return f"Pair(l={self.left}, r={self.right})"
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read()
# Part 1
pairs = get_pairs(data)
right_order = []
for i, pair in enumerate(pairs, start=1):
if pair.left < pair.right:
right_order.append(i)
print(f"Part 1 = {sum(right_order)}")
# Part 2
all_packets = get_all_packets(data)
# Add divider packets, as required:
div_two, div_six = Packet([[2]]), Packet([[6]])
all_packets.append(div_two)
all_packets.append(div_six)
sorted_items = sorted(all_packets)
loc_div_two = sorted_items.index(div_two) + 1
loc_div_six = sorted_items.index(div_six) + 1
print(f"Part 2 = {loc_div_two*loc_div_six}")
def get_pairs(data: str) -> list[Pair]:
pairs: list[Pair] = []
blocks = data.split("\n\n") # split into blocks
for block in blocks:
lines = block.splitlines()
pairs.append(Pair(Packet(literal_eval(lines[0])), Packet(literal_eval(lines[1]))))
return pairs
def get_all_packets(data: str) -> list[Packet]:
lines = data.splitlines()
return [Packet(literal_eval(line)) for line in lines if line]
if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"Execution time: {t2 - t1:0.4f} seconds")
And here’s the output:
Part 1 = 5588
Part 2 = 23958
Execution time: 0.0336 seconds
Sweet!