<?php

[$template, $rules] = explode("\n\n", file_get_contents('./input.txt'));

$template = str_split($template);

$pair_insertion_rules = [];
foreach (explode("\n", $rules) as $rule) {
    [$key, $value] = explode(' -> ', $rule);
    $pair_insertion_rules[$key] = $value;
}

for ($i = 0; $i < 40; $i++) {
    $tmp = [];
    foreach ($template as $i_char => $char) {
        if (array_key_exists($i_char+1, $template)) {
            $tmp[] = $char;
            $pair = $char . $template[$i_char + 1];
            if (array_key_exists($pair, $pair_insertion_rules)) {
                $tmp[] = $pair_insertion_rules[$pair];
            }
        }
    }
    $tmp[] = array_pop($template);
    $template = $tmp;
    echo $i."\n";
}

$count_char = array_count_values($template);
echo max($count_char) - min($count_char);