Module aoc::year2022::day13

Distress Signal

One possible approach is to parse the input into a tree, then compare recursively node by node. We’re going to use a much faster and simpler approach by noting an observation about the input data. If the sequence 10 is replaced by any single character greater than 9 then we can compare the 2 packets lexigraphically. We’ll replace all occurences of 10 with A then compare packets character by character.

The rules to compare 2 packets become:

• If both characters are the same then it’s a draw, move onto the next character in each packet.
• If the first packet is ] and the second packet anything else, then the first list is shorter so the packets are in order.
• Conversely if the second packet is ] and the first packet anything else, the packets are not in order.
• If the first packet is an opening [ and the second character anything else, then we’re comparing a number with a list, so push the second character back onto the list to check again along with a closing ] character.
• Do a similar push if the second character is an opening [ and the first anything else.
• Finally compare the 2 characters by value. Since we’ve already covered the equal case, one is guaranteed to be greater or less than the other.

Structs

• Packet 🔒

Functions

• compare 🔒
  Compare 2 packets using the rules listed in the module description.
• parse
• part1
  Count adjacent pairs of packets that are in order.
• part2
  Find the position of [[2]] and [[6]] in linear O(n) time.