Expand description
§Alchemical Reduction
§Part One
This problem is similar to checking if a parentheses expression is balanced or not. We use a similar approach, maintaining a stack of unreacted polymer units. Each unit from the polymer is compared to the head of the stack using bitwise logic. Lowercase and uppercase ASCII codes for the same lettter are always are 32 apart, which can be checked very quickly using bitwise XOR. For example:
A = 65 = 01000001
a = 97 = 01100001
A ^ a = 32 = 00100000
If two units are the same type but opposite polarity then they are popped from the stack.
§Part Two
An important optimization is to use the already reacted polymer from part one. This is approximately 20% of the size of the raw input. Then this smaller polymer is filtered further for each of the 26 kinds of unit.
Functions§
- collapse 🔒