[Advent Of Code 2022] Day 13: Distress Signal [SPOILERS]

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])
    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.

Code: Get It Working Latest

Python Solution
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

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