+#!/bin/bash
+
+set -u
+
+filename="${1:-example.txt}"
+exec 3<"$filename"
+
+read -u 3 template
+read -u 3 blank
+
+declare -A inserts=()
+
+while read -u 3 poly; do
+ left="${poly% -> *}"
+ right="${poly#* -> }"
+ inserts[$left]="$right"
+done
+
+declare -A pair_result=()
+for k in "${!inserts[@]}"; do
+ char="${inserts[$k]}"
+ pair_result[$k]="${k:0:1}${char} ${char}${k:1:1}"
+done
+
+declare -A pairs=()
+for (( a=0; a<$((${#template} - 1)); a++ )); do
+ lookup="${template:$a:2}"
+ if [ "${pairs[$lookup]+abc}" ]; then
+ ((pairs[$lookup]+=1))
+ else
+ pairs[$lookup]=1
+ fi
+done
+
+do_next_step() {
+ declare -A new_pairs=()
+ for pair in "${!pairs[@]}"; do
+ count=${pairs[$pair]}
+ for new_pair in ${pair_result[$pair]}; do
+ if [ "${new_pairs[$new_pair]+abc}" ]; then
+ ((new_pairs[$new_pair]+=$count))
+ else
+ new_pairs[$new_pair]=$count
+ fi
+ done
+ done
+ unset pairs
+ declare -g -A pairs=()
+ for k in "${!new_pairs[@]}"; do
+ pairs[$k]=${new_pairs[$k]}
+ done
+}
+
+get_diff() {
+ declare -A char_counts=()
+ for k in "${!pairs[@]}"; do
+ for (( a=0; a<2; a++ )); do
+ char=${k:$a:1}
+ if [ "${char_counts[$char]+abc}" ]; then
+ ((char_counts[$char]+=${pairs[$k]}))
+ else
+ char_counts[$char]=${pairs[$k]}
+ fi
+ done
+ done
+
+ for char in ${template:0:1} ${template: -1:1}; do # start and end of template get lost from the original count
+ if [ "${char_counts[$char]+abc}" ]; then
+ ((char_counts[$char]+=1))
+ else
+ char_counts[$char]=1
+ fi
+ done
+
+ declare -a hl=()
+ for v in "${char_counts[@]}"; do
+ hl[$v]=1
+ done
+
+ declare -a vals=("${!hl[@]}")
+ h=${vals[-1]}
+ l=${vals[0]}
+
+ diff=$((h - $l))
+ diff=$((diff / 2)) # because the parts are in pairs, our counts are going to be double what they should be
+
+ echo $diff
+}
+
+for (( a=1; a<=10; a++ )); do
+ do_next_step
+done
+
+echo "Part 1: $(get_diff)"
+
+for (( a=11; a<=40; a++ )); do
+ do_next_step
+done
+
+echo "Part 2: $(get_diff)"