Function advent_of_code_2021::day_14::intersperse

fn intersperse(
    polymer: &HashMap<(char, char), usize>, 
    mapping: &HashMap<(char, char), Vec<(char, char)>>
) -> HashMap<(char, char), usize>

The name is a legacy from the naive solution where this was mapping each pair to the new pairs and building the full polymer in order which failed as the final polymer had ~21 trillion characters. This takes all the existing pairs and adds their counts to the pair(s) they map to when the mapped character is inserted.

Consider the seed BABABA, in the internal representation this becomes BA => 3, AB => 2. With the mapping AB -> A and BA -> A this would become BAAABAAABAA or BA => 3, AA => 5, AB => 2. Because each pair mapping is independent, we can view the mapping as AB => AA, AB, BA => BA, AA. So applying intersperse to the BA => 3, AB => 2 polymer:

• BA => 3 becomes BA => 3, AA => 3.
• The new map is empty so both are inserted with a count of 3.
• AB => 2 becomes AA => 2, AB => 2.
• AA already exists with a count of 3, so these two are added to give AA =>5.
• AB isn’t in the map, so it is inserted with a count of 2.
• This gives the expected BA => 3, AA => 5, AB => 2 Polymer.