### re: 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))


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!

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))


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


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