Advent of Code 2018 Day 5: Alchemical Reduction

This post originally appeared on steadbytes.com

Complete solution can be found on GitHub

Part One

Given a puzzle input containing the string representation of the polymer used in Santa's suit, we are asked to find how many units remain after fully reacting the polymer. We are told that reactions take place between adjacent units of the same type but opposite polarity:

• type = letter
• polarity = upper/lower case

aA -> reaction
ab -> no reaction
aB -> no reaction
aa -> no reaction

When a pair of adjacent units react, they are destroyed which may then produce another reaction by the pair of units which are now adjacent, for example:

abBAbA -> aAbA -> bA

Parsing the Input

This is a simple case of reading in the entire input as a single string:

with open("input.txt") as f:
    polymer = f.read().strip() # remove leading/trailing whitespace just in case

Simulating a Reaction

A full reaction can be simulated using a stack to hold the units of the polymer as the reaction progresses:

1. Initialise an empty stack
2. For each unit in the polymer:
   • If the unit doesn't cause a reaction, push it onto the stack
   • Else, pop the previous unit off the stack (destroy the pair)
3. The units remaining in the stack represent the fully reacted polymer

A pair of units will react if they are the same type and opposite polarity. This relationship can be represented using a dictionary which maps from each possible unit to it's corresponding reaction unit:

import string

unit_pairs_map = {
    **{ch: ch.upper() for ch in string.ascii_lowercase},
    **{ch: ch.lower() for ch in string.ascii_uppercase},
}

Given a polymer unit, the required adjacent unit for a reaction to take place can be found by looking it up in unit_pairs_map:

# find required adjacent unit for 'a'
unit_pairs_map['a']
# A

# find required adjacent unit for 'A'
unit_pairs_map['A']
# a

The algorithm above can now be implemented:

def part_1(polymer):
    stack = []
    for unit in polymer:
        # there is a previous unit and it reacts with the current unit
        if stack and unit == unit_pairs_map[stack[-1]]:
            # reaction -> destroy the units
            stack.pop()
        else:
            # no reaction -> unit remains
            stack.append(unit)
    return len(stack)

For my puzzle input, the result is 10496.

Part Two

Next, we are told that a more complete reaction can be reduced if a certain polymer type is removed. We are asked to find the length of the shortest possible polymer by removing all units of exactly one type and fully reacting the result.

1. For each possible unit type
   • Remove all occurrences of the unit from the original polymer
   • Fully react the polymer
   • Measure the length of the reacted polymer
2. Return the shortest length

The sub-tasks for step 1 of the algorithm are actually the same as part 1 of the puzzle. To keep
things DRY, this logic can be extracted out of the part_1 function:

def react_polymer(polymer):
    # reaction logic from part 1
    stack = []
    for unit in polymer:
        if stack and unit == unit_pairs_map[stack[-1]]:
            stack.pop()
        else:
            stack.append(unit)
    return stack

def part_1(polymer):
    return len(react_polymer(polymer))

The solution to part two can now utilise the react_polymer function for the sub-tasks of step 1
in the algorithm:

def part_2(polymer):
    # original polymer length is the shortest so far
    best = len(polymer)
    for ch in string.ascii_lowercase: # unit types = letters of the alphabet
        reacted_polymer = react_polymer(
            # remove all occurrences (both polarities)
            [u for u in polymer if u != ch and u != ch.upper()]
        )
        # keep track of the shortest polymer found so far
        best = min(best, len(reacted_polymer))
    return best

For my puzzle input, the result is 5774.

Resources

• Stacks

- Using Python lists as Stacks