Solving https://adventofcode.com/2022/day/13 without a custom comparator or cmp_to_key

aoc-2022-13.py

import json

# Determine the maximum number of layers of nesting an integer or list has.
# That is, the maximum number of lists any particular integer is directly or
# indirectly inside. 1 is depth 0, [1] is depth 1, [[1]] is depth 2, etc.
def compute_depth(x):
    if isinstance(x, int): return 0
    assert isinstance(x, list)
    if not x: return 1
    return 1 + max(map(compute_depth, x))

# Convert an integer or list that's nested at most d layers deep so that every
# integer is nested exactly d layers deep. Python's built-in comparison
# naturally correctly handles two lists converted to the same depth this way!
def convert_to_depth(d, x):
    if d == 0:
        assert isinstance(x, int)
        return x
    if isinstance(x, int):
        return [convert_to_depth(d - 1, x)]
    assert isinstance(x, list)
    return [convert_to_depth(d - 1, e) for e in x]

max_depth = 0
pairs = []
with open('p13.in') as infile:
    for pair in infile.read().split('\n\n'):
        left, right = map(json.loads, pair.strip().split('\n'))
        max_depth = max(max_depth, compute_depth(left), compute_depth(right))
        pairs.append([left, right])

packets = []
part1_answer = 0
for i, (left, right) in enumerate(pairs):
    left = convert_to_depth(max_depth, left)
    right = convert_to_depth(max_depth, right)
    if left < right:
        part1_answer += i + 1
    packets.extend([left, right])

print("Part 1:", part1_answer)

sentinels = [convert_to_depth(max_depth, 2), convert_to_depth(max_depth, 6)]
packets.extend(sentinels)
packets.sort()

print("Part 2:", (packets.index(sentinels[0]) + 1) * (packets.index(sentinels[1]) + 1))