Discussion on: AoC Day 5: Alchemical Reduction

View post

Dumb order of operations mistake got me to this point 🙃was missing the parens around the last half of the conditional since like 12:20. This mirrors the classic stack match parentheses problem.

My solution is kinda pretty though:

with open('input.txt', 'r') as f:
    text = ''
    for line in f:
        text += line.strip()

def react(text):
    stack = []
    for letter in text:
        last = stack[-1] if stack else None
        if letter != last and (last == letter.upper() or last == letter.lower()):
            stack.pop()
        else:
            stack.append(letter)
    return len(stack)

# A1
print(react(text))

# A2
possibilities = set(text.lower())
print(min(react(text.replace(p, '').replace(p.upper(), '')) for p in possibilities))

Dane Hillard • Dec 6 '18

Wow, I did not see the stack-based solution in there at all. I tried the recursive approach and then one similar to @thejessleigh and stopped there! At least I enjoyed this one more than Day 4!

jess unrein • Dec 5 '18 • Edited

My first inclination was to do this recursively. Had to fudge it a bit because doing a truly recursive solution exceeds the max recursive depth :(

Here's my Python for part 1. It's very slow. Gonna look into refactoring to a regex or list comprehension solution for part 2. Kind of ready to move out of string manipulation land either way!

def polymer_compression(polymer):
    components = list(polymer)
    compressed_polymer, changes = find_sets(components)
    while changes is True:
        compressed_polymer, changes = find_sets(compressed_polymer)

    return len(compressed_polymer)

def find_sets(components):
    prev_val = None
    prev_case = None
    changes = False
    for index, component in enumerate(components):
        current_val = ord(component.lower())
        current_case = component.istitle()
        if current_val == prev_val and current_case != prev_case:
            components.pop(index)
            components.pop(index - 1)
            changes = True
            break
        prev_val = current_val
        prev_case = current_case
    return components, changes

print(polymer_compression(open('input.txt', 'r').read()))

Russ Hammett • Dec 5 '18

Wow, that stack thing is clever! It didn't even occur to me that you could evaluate as you go in a single pass through the polymer. Implementing the stack in c# (from the impl i posted below) went from ~2:50 => 268ms :O

Ali Spittel • Dec 5 '18

Cool! Yeah -- it's kind of a play on this classic problem, which is how I recognized it!

Bjarne Magnussen • Dec 5 '18 • Edited

Very slick solution!

Maybe most already know... But, parsing the polymer string as a string and using str.replace twice as you do is still much faster than using polymer as a list and using a list-comprehension to remove units (35% slower).

E.g.

# Faster:
print(min(react(text.replace(p, '').replace(p.upper(), '')) for p in possibilities))

# Slower:
text = list(text)
print(min(react([unit for unit in text if unit not in (p, p.upper())]) for p in possibilities))