# Learning Python with Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python # Advent of Code 2022 - Day 13

## 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]

[,[2,3,4]]
[,4]


[[8,7,6]]

[[4,4],4,4]
[[4,4],4,4,4]

[7,7,7,7]
[7,7,7]

[]


[[[]]]
[[]]

[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:

1. 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 as `list` or `int`.
2. Create a `Packet` class 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 `int` values. Otherwise, we’re either converting an `int` on one side to a `list` and comparing, or iterating over a `list` and comparing.
3. Create a `Pair` class to store left and right Packets. To be honest, this is kind of unnecessary, but it makes it all quite readable.
4. 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)), Packet(literal_eval(lines))))

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 == val:
continue # if the same, continue to next item

return Packet(val) < Packet(val)

# 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 `list` with 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 the `list` lengths, 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:

# 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([]), Packet([])  # 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 == val:
continue # if the same, continue to next item

return Packet(val) < Packet(val)

# 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:

# 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([]), Packet([])

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)), Packet(literal_eval(lines))))

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!