Function aoc::year2022::day13::part2

pub fn part2(input: &[&str]) -> u32

Find the position of [[2]] and [[6]] in linear O(n) time.

One approach would be to insert [[2]] and [[6]] into the list, sort in O(nlogn) time, then find the indices of the 2 values in O(n) time.

A much faster approach is to iterate over the list, comparing each packet first with [[2]]. If the packets are in order, then increment the positions of both [[2]] and [[6]], since [[2]] is less than [[6]].

If the packet and [[2]] are not in order, then also check against [[6]], incrementing only the second index if the 2 packets are in order.

This obtains the relative indices of [[2]] and [[6]] efficiently in fewer than 2n comparisons.