Introducing the elves to polymer engineering.
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:
- Initialise an empty stack
- 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)
- 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.
- 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
- 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.