This is a fun puzzle to attempt to solve- it has all the right things:

1. Stealing from elves
2. Use of XOR
3. A relatively short amount of code required to solve it
4. A data structure I often don't use

We've stolen a polymer from some elves, but it's volatile and the smaller units react with each other- if the same two letters in opposite cases are adjacent, they destroy each other. The following is taken directly from the website above:

• 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.

{[()]}   The inner '()' is removed.
{[]}     This creates '[]', which is removed.
{}       Now, the squiggles are left, and then removed.

Here is the polymer we are trying to analyze.

We can first check if two adjacent units react with each other. The simplest way I could think was good ol' XOR. I think you could do some stuff with upper and lower case conversions, but this is an eloquent solution. 0x20 == the integer 32. Typing the variables is optional in Julia, but I like to do it because it makes me feel like I understand whats going on.

1
2
3
4
5
6
7

function destroy(a::UInt8, b::UInt8)::Bool
	if xor(a, b) == 0x20
		return true
	else
		return false
	end
end

I used UInt8s in the function instead of characters, because we were given a text document of the polymer, so I'll read it in natively as bytes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function solve()
	s = Stack{UInt8}() 
	file = open("input.txt","r")
	while !eof(file)
	    c = read(file, UInt8)
	    if !isempty(s) && destroy(first(s), c)
	    	pop!(s)
	    else
	    	push!(s, c)
	    end
	end
	close(file)
	return length(s)
end

Pretty slick. 608.000μs run time using a stack on a polymer of length 50,000. I would love to find a solution to this using recursion, but I think the stack works well. Without it, you'd have to iterate over the input multiple times to determine if the collapsing units create new collapsing units.

I suspect the better you get at something, the less able you are to remember how difficult that thing was when you were first learning. I've been diving into C type languages recently, and I have to say- while I do like the idea of the language, certain syntax is so fucking annoying.

int  *ptr; //These are all the same thing?!
int * ptr;
int*  ptr;

Plus, we initialize pointers and dereference them with the same asterisk? int *ptr, ok cool, we have a pointer now. Then we see *ptr and all of a sudden we are dereferencing the pointer? lol. Why not something like deref ptr. It's a lot to type, I get it. But c'mon.