Advent of Code, Day 5

I approached this like a parsing problem. My base react function takes a stream of characters, and collapses them as reactions are found. Basically, I keep a stack of characters as I read them, then compare the latest character to the top of the stack. If they're a match, I pop off the stack and keep going. Otherwise, I push the new character onto the stack.

def react(stream):
    last = stream.read(1)
    result = '' + last
    current = stream.read(1)

    while len(current) > 0:
        if result != '':
            if last.upper() == current.upper() and last != current:
                result = result[:-1]
                if result != '':
                    last = result[-1]
            else:
                last = current
                result += last
        else:
            last = current
            result += last
        current = stream.read(1)

    return result

For the second part, I created a set of all the characters in the uppercased string. For each character in this set, I remove all occurrences of it (both upper and lowercase), then react. I kept a map of removed base -> size of the result, and return the minimum of this map.

def reactall(s):
    results = {}
    x = set(s.upper())
    for base in x:
        s2 = s.replace(base, '')
        s2 = s2.replace(base.lower(), '')
        result = react(io.StringIO(s2))
        results[base] = len(result)
    return min(results.items(), key=operator.itemgetter(1))

In all, it took about a half-second to run.

~/code/aoc/2018/05
(0) <hephaestus:kyle> $ time ./polymer.py polymer.txt
self check OK
polymer.txt: 11152
polymer.txt: shortest chain 6136 by removing W
./polymer.py polymer.txt  0.46s user 0.01s system 99% cpu 0.473 total

Tags: