Extended Polymerization - Advent of Code 2021 Day 14

 

An almost deserted Union St Subway station on the morning of the NYC Marathon

Union St Subway Station, Brooklyn

Some coding problems call for an intermediate solution that is used to compute the final problem. However, it is important to recognize when this may not be necessary. Today's Advent of Code problem is one such problem. The full problem can be found here.

We are presented with a String template, along with a set of rules. Based on these rules we can insert a character in between the characters in the template. This results in a new extended template

Each pair of characters that are eligible for insertion will overlap. The creation of a new template signals the completion of a step. We need to complete 10 steps (for part 1) and 40 steps (for part 2) and find the difference between the most and least occurrent characters.

For the first part of the problem (10 steps) a recursive function that expands the template using the rules works fine. 

However, eventually the exponential expansion of the template catches up and the code slows down. The introduction of a memo (and prebuilt memo) to cut down on steps only helps a little.

A re-evaluation of the problem statement made me realize that we only need a count of the final set of characters in order solve the problem . Therefore, rather than trying to create new expanded template on each step -

• We can just keep track of the count of characters, 
• whilst operating on a pair of characters in each recursion.
• The counts can be memo-ized too. 

In the following function, I do just that -

def findPolymerizationCount(template,steps):

    if steps == 0:
        return Counter(template)

    ret = Counter()
    for i in range(0,len(template)-1):

        k = "".join(template[i:i+2])

        (found,s) = findNearestMemo(k,steps)
     
        if s==steps:
            ret += found
            ret -= Counter([template[i+1]])
        elif k in insertionRules:

            toInsert = insertionRules[k]
            ret += findPolymerizationCount([ template[i] , toInsert ],steps-1) 
           
            if steps > 1:
                ret += findPolymerizationCount([ toInsert, template[i+1] ],steps-1)
                ret -= Counter([toInsert,template[i+1]])
            
        else:
            ret += template[i]

    ret += Counter( template[len(template)-1] )

    return ret

The full source code can be found here -

https://github.com/jasoncoelho/adventOfCode2021/blob/main/14/run.py