Skip to content

Instantly share code, notes, and snippets.

@acirtautas
Created February 7, 2013 07:15
Show Gist options
  • Save acirtautas/4729137 to your computer and use it in GitHub Desktop.
Save acirtautas/4729137 to your computer and use it in GitHub Desktop.
Balanced Smileys @ Facebook hacker cup 2013 qualification round
<?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;
}
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:()))))))))
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
5
:((
i am sick today (:()
(:)
hacker cup: started :):)
)(
Case #1: NO
Case #2: YES
Case #3: YES
Case #4: YES
Case #5: NO
@acirtautas
Copy link
Author

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment