Advent of Code 2018 - Day 5

Day 5: Alchemical Reduction

Useful Links

‹›

• 2018 Main Page
• My solution code

Concepts and Packages Demonstrated

Stack

Problem Intro

We are given a polymer, which is a long string of characters. The polymer is formed by smaller units which react with each other. Two adjacent units of the same type and opposite polarity are destroyed. Units’ types are represented by letters; units’ polarity is represented by capitalization. For instance, r and R are units with the same type but opposite polarity, whereas r and s are entirely different types and do not react.

For example:

• In aA, a and A react, leaving nothing behind.
• In abBA, bB destroys itself, leaving aA. As above, this then destroys itself, leaving nothing.
• In abAB, no two adjacent units are of the same type, and so nothing happens.
• In aabAAB, even though aa and AA are of the same type, their polarities match, and so nothing happens.

Consider a larger example, dabAcCaCBAcCcaDA:

dabAcCcaCBAcCcaDA  The first 'cC' is removed.
dabAaCBAcCcaDA    This creates 'Aa', which is removed.
dabCBAcaDA        Either 'cC' or 'Cc' are removed (the result is the same).
dabCBAcaDA        No further actions can be taken.

After all possible reactions, the resulting polymer contains 10 units.

Part 1

How many units remain after fully reacting the polymer you scanned?

My initial thought was to repeatedly iterate through the string, finding adjacent reacting pairs and removing them, until no more reactions occur. However, string manipulation like this (creating new strings repeatedly) can be slow, especially with Python’s immutable strings.

A much more efficient approach is to use a stack. We iterate through the polymer one character at a time:

1. If the stack is empty, push the current character.
2. If the current character reacts with the character at the top of the stack (same type, different case), we pop the top character from the stack (they destroy each other).
3. Otherwise, we push the current character onto the stack.

This allows us to process the polymer in a single pass, $O(N)$.

def react_polymer(polymer):
    """
    Fully react the polymer using a stack-based approach.
    Iterates through the polymer, removing adjacent units of the same type but opposite polarity.
    Returns the remaining polymer.
    """
    stack = []
    
    for char in polymer:
        if stack and char != stack[-1] and char.lower() == stack[-1].lower():
            # Same letter, different case (e.g. 'a' and 'A') -> React!
            stack.pop()
        else:
            # No reaction, add to stack
            stack.append(char)
    
    return stack

For Part 1, we just need the length of the resulting stack:

def part1(polymer: str):
    """
    Returns the length of the remaining polymer.
    """
    stack = react_polymer(polymer)     
    return len(stack)

Part 2

One of the unit types is causing problems. The goal is to remove all units of exactly one type (both lowercase and uppercase) from the original polymer, and then fully react the remaining polymer. What is the length of the shortest polymer you can produce?

Here, we need to try removing each unit type (a/A, b/B, c/C, etc.) from the original polymer, react the modified polymer, and find the minimum resulting length.

We can iterate through string.ascii_lowercase - just a string constant of all lowercase letters - to get all unit types. For each type, we remove it (both lower and upper case) from the original string, run our react_polymer function, and store the length.

import string

def part2(polymer: str):
    """
    Returns the length of the remaining polymer after removing all units of a single type.
    """
    polymers = {}
    for char in string.ascii_lowercase: # iterate over all lowercase letters
        # Remove both lowercase and uppercase versions of the unit
        new_polymer = polymer.replace(char, "").replace(char.upper(), "")
        stack = react_polymer(new_polymer)
        polymers[char] = len(stack)
    
    return min(polymers.values())

This approach reuses our efficient stack-based reaction logic. Since there are only 26 unit types, running the O(N) reaction 26 times is still very fast.

Results

Part 1 soln=10888
Part 2 soln=6952

‹›