Balanced Smileys @ Facebook hacker cup 2013 qualification round

balanced_smileys.php

<?php
/**
 * Facebook Hacker Cup 2013 Qualification Round
 *
 * Balanced Smileys
 *
 * @author Alfonsas Cirtautas
 */

// Read data
$raw = file('balanced_smileys.txt');
$cnt = reset($raw);
$rez = '';

// Check if strings are balanced.
for ($i=1; $i<=$cnt; $i++) {
    $s = $raw[$i];
    $b = balance($s)?'YES':'NO';
    $rez.= "Case #{$i}: {$b}".PHP_EOL;
}

// Save results
file_put_contents('balanced_smileys_answers.txt', $rez);

// Where the magic happens ;)
function balance($s) {
    $s = cleanup($s);
    $c = substr_count($s, ':');

    // This code can not handle too much smiles :(
    if($c>16) {
        $c = 16;
    }

    $b = pow(2, $c);
    $w = array();
    for ($i=0; $i<$b; $i++) {
        $x = str_pad(decbin($i), $c, '0', STR_PAD_LEFT);
        $y = replace($s, $x);
        $z = reduce($y);
        $w[] = strlen($z);
        if(strlen($z)==0) continue;
    }

    return min($w) == 0;
}

// Replace some smileys
function replace($s, $x)
{
    $n = strlen($x);
    for ($i = 0; $i<$n; $i++) {
        $p = strpos($s, ':');
        if ($p !== FALSE) {
            if ($x[$i] == '0') {
                $s[$p] = ' ';
            } else {
                $s[$p] = ' ';
                $s[$p+1] = ' ';
            }
        }
    }
    $s = str_replace(' ', '', $s);
    return $s;
}

// Reduce parenthesis
function reduce($s) {
    $l = strlen($s);
    for ($i=0;$i<$l;$i++) {
        if (strlen($s) == 0) continue;
        $s = str_replace('()','',$s);
    }
    return $s;
}

// Leave only characters that really matters.
function cleanup($s) {
    $s = trim($s);
    $l = strlen($s);
    $t = '';
    for ($i=0;$i<$l;$i++) {
        $x = $s[$i];
        $y = $i?$s[$i-1]:'';
        if ($x == '(' || $x == ')') {
            if ($y == ':') {
                $t.=$y;
            }
            $t.=$x;
        }
    }

    return $t;
}

balanced_smileys.txt

20
(:)())()a()(()::(():())(:))):((:(a:())()()a)((()(a))()(:a()a:((:)a(())(:)(()())))())(a)))()
:)aa((:)aa)aa)(((:((a(a)):(())))a:(:(()):a)):))((a()))a()(:(()a()()a):)a((()())):aa:)a()aa
aa(()())((a))(:((()a:()())(a):)())a():(:)))(:):a):)()(((a((()a(a()((aa(:)))a)((aa((a))(a)))))))
a((aa)(:a()a())()(()((()((a:(a)()aaa()(:::(a()):((:())(()))(((aa:(:a)):):(():)))((a()(()(())))
():)((()():(:())))::aa((((:(((:)))::a:(:))()a)):(a):::((()a((a(aa(():))(():())((::a)a)):)()
:)(a):)(a)(a()(()(()):a()(a))(a(a))a(a:)))a((:aa::()()()aa)):):((():)):(::a:a)()a()):):)()
:((
::((:))(((:)(aaa)(a())()(a:)(:)(:)()):)a())aa)())(():a):()::):)a()())a()):):(:a)a):()(a)(a)
hacker cup: started :):)
(:)())a(:():)((a:a()()()(())((:a:(:():())):):(:((aa)()(:(:)a))a:(:):a)):()((())()a::::()(:)
a()(())(())(:)(:((:aa)()(a(():()()a)a()():(((:))()(()(a:(:aa)())))(:::()((::aa)))))(:)(((()())
(a())(::)(a))():(((a(()(:))a(:)))(:(:(:((():)(a))(:))(a)():(:(()aa):)(a((())a)a((a):)()(:(
()((:a(a()()a))())((:a(:a)(()a((((a((a(()(:aa()()()))):)(():):)(:(a))():(())(():()):):(()a))
a(:(((()a)()()a(()()aa(a(a:::aaa(:):)a(a:a((a(())((()((:))))(a()(())():()()(a(()()a)((:)(a))))))))
)(
aa:((:((a()(()()a(:)::)(:)a)(()a((a(aa((((((()aaa)):()aa):))))()()(((a))))()a)(()()))a())()
(:)
(:a))
i am sick today (:()
(()(:a():)))()aa(:)((:(a(::a))())()(())))aa:)()()::a(((((a()):()(:()(((:)()a()(((a()(a:()))))))))

balanced_smileys_answers.txt

Case #1: YES
Case #2: YES
Case #3: NO
Case #4: NO
Case #5: YES
Case #6: YES
Case #7: NO
Case #8: YES
Case #9: YES
Case #10: YES
Case #11: NO
Case #12: NO
Case #13: YES
Case #14: NO
Case #15: NO
Case #16: YES
Case #17: YES
Case #18: NO
Case #19: YES
Case #20: YES

balanced_smileys_test.txt

5
:((
i am sick today (:()
(:)
hacker cup: started :):)
)(

balanced_smileys_test_answers.txt

Case #1: NO
Case #2: YES
Case #3: YES
Case #4: YES
Case #5: NO

All solution can be found on http://www.facebook.com/notes/facebook-hacker-cup/qualification-round-solutions/598486173500621