The Anatomy of a Markov Algorithm: How my solution to Facebook Qualification Round Problem 2 works

Here is my Markov Algorithm solution to the second problem in the Facebook Qualification Round, broken up into sections. The first thing necessary is to run some preprocessing on the input to add a question mark to the end.

SECTION 1. Get rid of the rubbish.

:(->[
:)->]
:->
 ->
a->
b->
c->
d->
e->
f->
g->
h->
i->
j->
k->
l->
m->
n->
o->
p->
q->
r->
s->
t->
u->
v->
w->
x->
y->
z->

Here it takes a string such as "this is a colon (:) and this is three smileys (:):(:))?" and turns all smileys/potential parentheses into square brackets, and then removes all non-parentheses or brackets, giving "(](][[)?". The question is whether some of the square brackets can be turned into parentheses and the other brackets deleted so as to leave a balanced set of parentheses. 

SECTION 2. Duplicate

)?->}?)
]?->?)
(?->{?(
[?->{?
({->{(
){->{)
[{->{[
]{->{]
(}->}(
)}->})
[}->}[
]}->}]
?-><|

This is the clever bit. The first four rules make the question mark run backwards through the string, making two broken copies of the original string: to the right, you get the version if all closed square brackets are turned into closed parentheses and all open square brackets are deleted: in the case above you would be left with "()())". 

To the left, you get what would happen if you deleted all closed square brackets, and turned all open square brackets into open parentheses. To differentiate the left from the right, however, I make them curly brackets. (rules 5-9 here are just to make the curly brackets, destined for the left, pass through the other brackets/parentheses you haven't dealt with yet) So you would get "{{{{}" on the left. Note however, that you are generating these in reverse order, so you would actually end up with "}{{{{".

Finally you change the question mark into a vertical bar. So after going through this section of the algorithm, you end up with "}{{{{|()())".

{<-><)
}<-><(

<->

Now I change the curly brackets back to parentheses. Since they are in reverse order, I reverse the sign of the brackets. The less-than-signs are just to keep the curly brackets and parentheses separated until they are all converted - since section 2 teaches curly brackets and parentheses to go through. So now we are at "())))|()())".

So what have we done?

We have replaced our original bracket/parenthesis encoding of the string with two series of parentheses - one corresponding to turning all of the closed brackets to parentheses and deleting the open brackets, and the other corresponding to turning all of the open brackets to parentheses and deleting the closed brackets (and this second one we have reversed the string and inverted the brackets).

Now, suppose that we have some expression like "(](][[)" that can be made into a valid expression (let's call it VE) by rounding some of the square brackets and removing the others. If you round all of the closed square brackets and remove all of the open square brackets, the effect is the same as taking VE, removing some number (possibly 0) of open brackets and adding some number (possibly 0) of closed brackets. The effect will be to have the end of a valid sequence of parentheses.

Similarly, if we round all of the open square brackets and remove all of the closed square brackets, we must have the start of a valid sequence of parentheses.

It turns out that the converse is true:

A sequence of open/closed square brackets and parentheses can be turned into a valid sequence of brackets and parentheses by rounding some square brackets and removing the rest iff both of the following are true:

When you round all of the open square brackets and remove the closed ones you get the start of a valid sequence of parentheses
When you round all of the closed square brackets and remove the open ones you get the end of a valid sequence of parentheses.


Proof is left to the interested reader.




It follows that we want to respond YES, if both the left expression (which should be the start of a valid sequence of parentheses, inverted and reversed) and the right expression (which should be the end of a valid sequence of parentheses) are the ends of valid sequences of parentheses. Luckily it is easy to check if something is the end of a valid sequence of parentheses with 1 rule:

SECTION 3. Validate

()->

Given a sequence of open and closed parentheses, this rule turns all ends of valid sequences of parentheses into a number (possibly 0) of closed parentheses. All other sequences will still have an open parenthesis left. In our original string, we are at ")))|)"

)|->|
|)->|

So now we soak up all closed brackets adjacent to the vertical bar, leaving our original string at "|". If we had a valid expression, we are now at "|". Otherwise, there is an open bracket next to the vertical bar.

|(->NO
(|->NO
NO(->NO
NO)->NO
(NO->NO
)NO->NO
|->YES

This completes the test, turning all invalid sequences into NO and valid ones into YES.