AoC 2018 Day 5: Alchemical Reduction
Tags: aoc2018, python, puzzle, challenge
Published: 2019-05-02 17:29:21

---
title: "AoC 2018 Day 5: Alchemical Reduction"
tags: ["aoc2018", "python", "puzzle", "challenge"]
published: true
categories: ["Advent of Code 2018"]
description: Introducing the elves to polymer engineering.
---
> This post originally appeared on [steadbytes.com](https://steadbytes.com/blog/advent-of-code-2018/05/)

> Complete solution can be found on [GitHub](https://github.com/SteadBytes/advent-of-code-2018/blob/f1842d04abab5c3fc5d1cb966d9da8b0ffa0ac29/05/solution.py)

## Part One

Given a [puzzle input](https://github.com/SteadBytes/advent-of-code-2018/blob/f1842d04abab5c3fc5d1cb966d9da8b0ffa0ac29/05/input.txt) 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:

```python
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](<https://en.wikipedia.org/wiki/Stack_(abstract_data_type)>) 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:

```python
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`:

```python
# 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:

```python
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:

```python
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:

```python
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](https://en.wikipedia.org/wiki/Stack_(abstract_data_type))
- [Using Python lists as Stacks](https://docs.python.org/3.1/tutorial/datastructures.html#using-lists-as-stacks)
-