Python’s json.loads() and functools.cmp_to_key() were quite helpful.
Python Solution
def read_file(file: TextIO):
"""Read packets from the `file`."""
lines = (line.rstrip() for line in file)
return [json.loads(line) for line in lines if line]
def cmp_packets(left_packet, right_packet):
"""Compare two packets recursively, return -1/0/+1."""
for left, right in itertools.zip_longest(left_packet, right_packet):
if left is None:
return -1
if right is None:
return 1
if isinstance(left, int) and isinstance(right, int):
if left < right:
return -1
if left > right:
return 1
elif isinstance(left, list) and isinstance(right, list):
res = cmp_packets(left, right)
if res != 0:
return res
elif isinstance(left, int):
res = cmp_packets([left], right)
if res != 0:
return res
elif isinstance(right, int):
res = cmp_packets(left, [right])
if res != 0:
return res
return 0
def part1(file: TextIO) -> int:
"""Solve the first part of the puzzle."""
packets = read_file(file)
pairs = zip(packets[::2], packets[1::2])
return sum(i for i, pair in enumerate(pairs, 1) if cmp_packets(*pair) < 1)
def part2(file: TextIO) -> int:
"""Solve the second part of the puzzle."""
packets = read_file(file)
extra_packet1, extra_packet2 = [[2]], [[6]]
packets.extend([extra_packet1, extra_packet2])
packets.sort(key=functools.cmp_to_key(cmp_packets))
extra_packet1_index = packets.index(extra_packet1) + 1
extra_packet2_index = packets.index(extra_packet2) + 1
return extra_packet1_index * extra_packet2_index
Part one went really well for me. My parsing lib was quite helpful. In my current iteration, I have a single line in my Day 13 for parsing: INPUT_PARSER = aoc.ParseBlocks([aoc.ParseOneWordPerLine(json.loads)]). (I did initially just use eval().)
match case has type checking which was fun for part 1.
When I saw part two, I realized I needed to use sort(key=func) which is supposed to return True when a < b. To make that happen, I (incorrectly) attempted to switch all my return <x> to return <x> == 1 (negating the logic). I then didn’t know how to make this work with cmp and a single value, but I thankfully found sort(key=cmp_to_key) which takes a cmp(a, b) function. I switch to using sort(key=cmp_to_key(cmp)) … but forgot to revert from bool to -1 | 0 | 1. I then spent 20-25 minutes trying to understand why sort() was not changing the list order, and trying to write a bubble sort (with the incorrect bool logic). Once I realized that cmp_to_key() expects -1 | 0 | 1, the solution came quickly.
I wish I took the time to double check what cmp_to_key() handles and took a minute to think through the data types.
This got me wondering how cmp_to_key() even works and how I’m supposed to sort things. I looks up the cmp_to_key() source and it’s much simpler than I expected! The “Sorting HOW TO” also suggests a Decorate-Sort-Undecorate pattern.
def int_cmp(a: int, b: int) -> int:
if a < b:
return -1
if a > b:
return +1
return 0
def cmp(first: Any, second: Any) -> int:
"""Compare two values and return -1|0|1."""
match [first, second]:
case [int(), int()]:
return int_cmp(first, second)
case [list(), list()]:
for i, j in zip(first, second):
result = cmp(i, j)
if result:
return result
return int_cmp(len(first), len(second))
case [list(), int()]:
return cmp(first, [second])
case [int(), list()]:
return cmp([first], second)
raise ValueError(f"Umatched {first} {second}")
I took advantage of Ruby’s dynamic nature to customize array sorting and just used the JSON parser to parse the arrays:
Ruby Solution
require 'json'
class Array
def <=>(right)
case [self, right]
in [[], []] then 0
in [[], Array] then -1
in [Array, []] then 1
in [[Integer => a, *as], [Array => b, *bs]] then [[a], *as] <=> [b, *bs]
in [[Array => a, *as], [Integer => b, *bs]] then [a, *as] <=> [[b], *bs]
in [[a, *as], [b, *bs]] then
head_comparison = a <=> b
head_comparison.zero? ? as <=> bs : head_comparison
end
end
end
packets = File.readlines('inputs/13.txt', chomp: true).reject(&:empty?).map { JSON.parse(_1) }
divider_packets = [[[2]], [[6]]]
a = packets.each_slice(2).with_index(1).sum { |pair, idx| pair == pair.sort ? idx : 0 }
b = packets.push(*divider_packets).sort.then { |sorted_packets| divider_packets.map { sorted_packets.index(_1) + 1 }.inject(:*) }
require 'minitest/autorun'
describe 'day 13' do
it 'part a' do assert_equal 5_806, a end
it 'part b' do assert_equal 23_600, b end
end