5.md

Day 5: Polymer Reactions - Part1 and Part2

Polymer is formed by smaller units which, when triggered, react with each other such that two adjacent units of the same type and opposite polarity are destroyed. Units' types are represented by letters; units' polarity is represented by capitalization. For instance, r and R are units with the same type but opposite polarity, whereas r and s are entirely different types and do not react.

For example:

• In aA, a and A react, leaving nothing behind.
• In abBA, bB destroys itself, leaving aA. As above, this then destroys itself, leaving nothing.
• In abAB, no two adjacent units are of the same type, and so nothing happens.
• In aabAAB, even though aa and AA are of the same type, their polarities match, and so nothing happens.

Now, consider a larger example, dabAcCaCBAcCcaDA:

dabAcCaCBAcCcaDA  The first 'cC' is removed.
dabAaCBAcCcaDA    This creates 'Aa', which is removed.
dabCBAcCcaDA      Either 'cC' or 'Cc' are removed (the result is the same).
dabCBAcaDA        No further actions can be taken.

After all possible reactions, the resulting polymer contains 10 units.

Part 1

How many units remain after fully reacting the polymer you scanned?

Part 2

One of the unit types is causing problems; it's preventing the polymer from collapsing as much as it should. Your goal is to figure out which unit type is causing the most problems, remove all instances of it (regardless of polarity), fully react the remaining polymer, and measure its length.

For example, again using the polymer dabAcCaCBAcCcaDA from above:

• Removing all A/a units produces dbcCCBcCcD. Fully reacting this polymer produces dbCBcD, which has length 6.
• Removing all B/b units produces daAcCaCAcCcaDA. Fully reacting this polymer produces daCAcaDA, which has length 8.
• Removing all C/c units produces dabAaBAaDA. Fully reacting this polymer produces daDA, which has length 4.
• Removing all D/d units produces abAcCaCBAcCcaA. Fully reacting this polymer produces abCBAc, which has length 6.

In this example, removing all C/c units was best, producing the answer 4.

What is the length of the shortest polymer you can produce by removing all units of exactly one type and fully reacting the result?

Solution

There are two ways of solving this, a slow way and a fast way.

Both solutions rely on this function:

// 'a' and 'A', and any other letter with opposite casing,
// will always have a diff of 32.
export const willReact = (c1: string, c2: string) =>
    Math.abs(c2.charCodeAt(0) - c1.charCodeAt(0)) === 32;

Let's look at the suboptimal solution first.

Suboptimal Solution

export const destroy =
    (polymer: string) =>
    (index: number) =>
        polymer.substring(0, index - 1) + polymer.substring(index + 1);

const react = (polymer: string) => {
    let result = polymer,
        index = 1;
    while (index < result.length) {
        if (willReact(result.charAt(index), result.charAt(index - 1))) {
            result = destroy(result)(index);
            index--;
        }
        else {
            index++;
        }
    }
    return result;
};

This solution goes and recreates a new string every time, which takes O(n) time, and so doing that n times gives you a O(n^2) solution. On my input for part 2, this solution has a runtime of 4 seconds.

Optimal Solution

A better solution is to use a stack. If the last element in the stack will react with the current element in the polymer, pop() the stack.

const react2 = (polymer: string) => {
    const result = [''];
    let index = 0;
    while (index < polymer.length) {
        const char = polymer.charAt(index);
        if (willReact(last(result), char))
            result.pop();
        else
            result.push(char);
        index++;
    }
    // -1 because we added an empty string ('') in the
    // beginning so that last(result) doesn't return undefined
    return result.length - 1;
};

This has a time complexity of O(n). On my input for part 2, this solution has a runtime of 100ms.

Part 2

Just repeatedly do part 1 while also doing an exclusion check.

One awesome optimization is to first do part 1 to get a smallerPolymer, and then when looping through the alphabets, use this new smallerPolymer.

Doesn't call react() first (100ms runtime)

const react = (polymer: string) => (exclude: string) => {
    const result = [''];
    let index = 0;
    while (index < polymer.length) {
        const char = polymer.charAt(index);
        if (willReact(last(result), char))
            result.pop();
        else if (char.toUpperCase() !== exclude)
            result.push(char);
        index++;
    }
    return result.length - 1;
};

const reactWithImprovements = (polymer: string) => {
    const begin = 'A'.charCodeAt(0);
    const end = 'Z'.charCodeAt(0);
    let shortestPolymer = Infinity;
    for (let i = begin; i <= end; i++)
        shortestPolymer = Math.min(
            shortestPolymer,
            react(polymer)(String.fromCharCode(i))
        );
    return shortestPolymer;
};

Calls react() first (40ms runtime)

const react = (polymer: string) => (exclude: string) => {
    const result: string[] = [];
    let index = 0;
    while (index < polymer.length) {
        const char = polymer.charAt(index);
        if (willReact(last(result) ?? '', char))
            result.pop();
        else if (char.toUpperCase() !== exclude)
            result.push(char);
        index++;
    }
    return result;
};

const reactWithImprovements = (polymer: string) => {
    const begin = 'A'.charCodeAt(0);
    const end = 'Z'.charCodeAt(0);
    let shortestPolymer = Infinity;

    const smallerPolymer = react(polymer)('').join('');
    for (let i = begin; i <= end; i++)
        shortestPolymer = Math.min(
            shortestPolymer,
            react(smallerPolymer)(String.fromCharCode(i)).length
        );
    return shortestPolymer;
};