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

puzzle_input_str = open("puzzle_input/day14.txt").read()

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[0]
    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[0], 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[0], 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