Sean McLemon | Advent of Code

2021-12-14 - Extended Polymerization

(original .ipynb)

Day 14 puzzle input is a description of a "polymer" (a string) and a number of transforms (a pair of polymer elements, and a new element that would be inserted between them after it is applied to the polymer) - mine is here. Part 1 involves transforming the polymer 10 times, finding the most and least common elements and subtracting them. Part 2 involves the same but 40 times.

from collections import defaultdict

test_input_str = """NNCB

CH -> B
HH -> N
CB -> H
NH -> C
HB -> C
HC -> B
HN -> C
NN -> C
BH -> H
NC -> B
NB -> B
BN -> B
BB -> N
BC -> B
CC -> N
CN -> C"""

# Apply 10 steps of pair insertion to the polymer template and find the most and least
# common elements in the result. What do you get if you take the quantity of the most
# common element and subtract the quantity of the least common element?

def parse_input(input_str):
polymer, rules_str = input_str.split("\n\n")
rules = {
k:v
for k,v
in [r.split(" -> ") for r in rules_str.split("\n")]
}

return polymer, rules

def apply_rules(polymer, rules):
a = polymer
new_polymer = [a]

for i in range(1, len(polymer)):
b = polymer[i]
new_polymer.append(rules[a+b])
new_polymer.append(b)
a = b

return new_polymer

def count_elements(polymer):
count = defaultdict(lambda:0)
for element in polymer:
count[element] += 1

sorted_count = sorted(count.keys(), key=lambda e:count[e])
least, most = sorted_count, sorted_count[-1]

return count[least], count[most]

def part_one(input_str, steps = 10):
polymer, rules = parse_input(input_str)

while steps > 0:
polymer = apply_rules(polymer, rules)
steps -= 1

least, most = count_elements(polymer)

return most - least

assert 1588 == part_one(test_input_str)
print("part one:", part_one(puzzle_input_str))
part one: 2975
def get_pairs(polymer):
for i in range(0, len(polymer)):
result = polymer[i:i + 2]
# yuck
if len(result) == 2:
yield result

def part_two(input_str, steps = 40):
polymer_template, rules = parse_input(input_str)

counts = defaultdict(lambda:0)
for p in get_pairs(polymer_template):
counts[p] += 1

while steps > 0:
new_counts = defaultdict(lambda:0)
for pair in counts:
a, b = pair
c = rules[a+b]
new_counts[a+c] += counts[pair]
new_counts[c+b] += counts[pair]

counts = new_counts
steps -= 1

totals = defaultdict(lambda:0)

for pair in counts:
a,b = pair
totals[a] += counts[pair]
totals[b] += counts[pair]

sorted_totals = sorted(totals.keys(), key=lambda e:totals[e])
least, most = sorted_totals, sorted_totals[-1]

# lol
import math
return int(math.ceil(totals[most]/2)) - int(math.ceil(totals[least]/2))

part_two(test_input_str, 40)
print("part two:", part_two(puzzle_input_str))
part two: 3015383850689