re: AoC Day 5: Alchemical Reduction VIEW POST

VIEW FULL DISCUSSION
 

this one was easy (to me!) in comparison to yesterdays, might even be the easiest thus far. All that being said, DAMNNNNNN is part 2 slow, at least with my current impl.

00:07 run time for part 1
02:50 run time for part 2 :OOOOO

public class AlchemicalReduction
    {
        public string ReducePolymer(string polymer)
        {
            while (true)
            {
                StringBuilder sb = new StringBuilder();
                var previousChar = "";

                for (int i = 0; i < polymer.Length; i++)
                {
                    string currentChar = new string(new[] { polymer[i] });

                    // Same letter
                    if (currentChar.Equals(previousChar, StringComparison.OrdinalIgnoreCase))
                    {
                        // different case
                        if (!currentChar.Equals(previousChar, StringComparison.Ordinal))
                        {
                            // Remove the last character from the builder, don't add this character
                            sb.Remove(i - 1, 1);
                            // Add the remaining characters to the builder
                            sb.Append(polymer.Substring(i + 1, polymer.Length - i - 1));
                            // reset the previous char for next entry into for loop
                            previousChar = "";
                            break;
                        }
                    }

                    // Record new previous char, append the current char to the builder
                    previousChar = currentChar;
                    sb.Append(currentChar);
                }

                // Completed for loo pass, build the string
                var newString = sb.ToString();

                // break out of while loop if they're the same string (has been reduced by maximum amount)
                if (polymer == newString)
                {
                    break;
                }

                // Work with the newly modified string within the for loop
                polymer = newString;
            }

            return polymer;
        }

        public string FullyReducePolymerByEliminatingSingleUnit(string polymer)
        {
            var originalPolymer = polymer;
            var normalizedPolymer = originalPolymer.ToUpper();

            // get the individual "types" within the polymer
            var groupsOfTypes = normalizedPolymer
                .GroupBy(gb => gb)
                .Select(s => s.Key);

            // builds new list of potential polymers, removing a single type from the chain in each run
            List<string> newPotentialPolymers = new List<string>();
            foreach (var s in groupsOfTypes)
            {
                // Removes a single type from the potential polymer
                var charToRemove = new string(new[] { s });
                var regex = new Regex(charToRemove, RegexOptions.IgnoreCase);

                newPotentialPolymers.Add(regex.Replace(originalPolymer, ""));
            }

            // Run the new potential polymers
            List<string> reducedPolymers = new List<string>();
            foreach (var potentialPolymer in newPotentialPolymers)
            {
                reducedPolymers.Add(ReducePolymer(potentialPolymer));
            }

            // return the smallest one
            var minLengthPolymer = reducedPolymers.Min(m => m.Length);
            return reducedPolymers.Where(w => w.Length == minLengthPolymer).First();
        }
    }

Didn't think about the stack approach til seeing other's solutions, wow so much faster! Didn't really occur to me you could accomplish the whole reduction in a single pass through the polymer.

Part 1 went from 00:07 -> 12ms
Part 2 went from 02:50 -> 269ms

public string ReducePolymer(string polymer)
        {
            // Refactored to stack with input from others solutions at: 
            // https://dev.to/rpalo/aoc-day-5-alchemical-reduction-5b2f/comments

            Stack<string> stack = new Stack<string>();
            foreach (var c in polymer)
            {
                var s = new string(new[] { c });

                // the top item in the stack (or empty string if we haven't yet added to stack)
                var top = stack.Count == 0 ? string.Empty : stack.Peek();

                // if the top item is the same letter, 
                // but different case than the currently evaluated character,
                // remove the top item from the stack, and don't add the current character.
                if (top != "" && top.ToLower() == s.ToLower() && top != s)
                {
                    stack.Pop();
                }
                // No match, add the character to the stack
                else
                {
                    stack.Push(s);
                }
            }

            // Is there a better way to project the stack back into a contiguous string?
            var sb = new StringBuilder();
            while(stack.Count > 0)
            {
                sb.Append(stack.Pop());
            }

            return sb.ToString();
        }
code of conduct - report abuse