Today was not a good day. I've struggled with the solution for Day 14 , particularly Part 2.

We need to produce new material to reinforce our submarine. Luckily, there's some polymerization equipment onboard that we can use. We even have the manual. The manual contains a polymer template and some insertion rules:

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

The first line is the template, the rest is the insertion rules. For example CH -> B means that when our template contains C and H right next to eachother, we should insert B between them. All insertions happens in steps, and all insertions for a single step happens at the same time, so any new pairs that are formed does not count until the next step. Also, pairs overlap. So the example template above, NNCB, contains 3 pairs: NN, NC and CB.

For Part 1 we need to apply 10 steps of insertion, and then find the most common and least common element. Subtract the count of least common from the count of most common to get the answer.

For starters, lets parse our input to get our template and insertion rules:

var input = File.ReadAllLines("input.txt");

var template = input[0];
var insertionRules = input.Skip(2).ToDictionary(x => x.Split("->")[0].Trim(), x => x.Split("->")[1].Trim());

Part 1 wasn't that difficult, although it did take me longer than I would have liked:

private static void Part1(string template, Dictionary<string, string> rules, int steps)
{
    for (var i = 0; i < steps; i++)
    {
        var newTemplate = template[0].ToString();
        for (var j = 1; j < template.Length; j++)
        {
            var pair = template.Substring(j - 1, 2);

            newTemplate += rules[pair]; 
            newTemplate += template[j];
        }

        template = newTemplate;
    }

    var elements = template.GroupBy(x => x).ToList();
    Console.WriteLine($"Part 1: {elements.Max(x => x.Count()) - elements.Min(x => x.Count())}");
}

We create a new template, starting with the first char of the original template. Then, go through the template, checking the current pair and get the matching element from our insertion rules. We add the element to our new template, add the second part of the original pair and so on, until we've worked through the original template. Then we replace the orignal template with the new one, and go to the next step.

Finally we can count the elements in the template by grouping them, and get the min and max values that we need.

This not an optimal solution, but fast enough for Part 1. For Part 2, we are doing the same thing but for 40 steps instead. Since the template string is growing alot for each step, this method will take to long and probably run out of memory at some point.

So instead of actually creating the template string over and over, we can just count the amount of times each pair occurs in the template. While we're at it, we should also count the amount of times each letter occurs in the template along the way.

private static void Part2(string template, Dictionary<string, string> rules, int steps)
{
    var pairCount = new Dictionary<string, long>();
    var letterCounts = new Dictionary<string, long>();

    foreach (var pair in template.ToPairs().ToList())
    {
        pairCount[pair] = pairCount.GetValueOrDefault(pair, 0) + 1;
    }

    foreach (var element in template.Select(c => c.ToString()))
    {
        letterCounts[element] = letterCounts.GetValueOrDefault(element, 0) + 1;
    }

    for (var i = 0; i < steps; i++)
    {
        var newPairCount = new Dictionary<string, long>();
        foreach (var pair in pairCount.Keys)
        {
            var currentCount = pairCount[pair];
            var added = rules[pair];

            var newPairs = new List<string> { pair[0] + added, added + pair[1] };
            newPairs.ForEach(x => newPairCount[x] = newPairCount.GetValueOrDefault(x, 0) + currentCount);

            letterCounts[added] = letterCounts.GetValueOrDefault(added, 0) + currentCount;
        }

        pairCount = newPairCount.ToDictionary(x => x.Key, x => x.Value);
    }

    Console.WriteLine($"Part 2: {letterCounts.Max(x => x.Value) - letterCounts.Min(x => x.Value)}");
}

First, we're setting up our initial counts from the original template. Then, we start stepping. We go through each existing pair key, keeping track of the current count, add our new pairs created using our insertion rules, and keep track of the new count in a new dictionary. We also update the letter counts at the end. Finally we replace our old pair counts with the new one. Getting the answer will then be very easy, using the letter counts. The ToPairs() method used above is a simple extension method that I threw together quite quickly. It works for this use case, where we want complete, overlapping pairs:

public static IEnumerable<string> ToPairs(this string s)
{
    for (var i = 0; i < s.Length; i++)
    {
        if (s.Length - i >= 2)
        {
            yield return s.Substring(i, 2);
        }
    }
}