## Saturday, March 31, 2012

I was going to post this a while back (you know, back when it was still relevant) but I never got around to it and I've recently had my wisdom teeth out, which has given me a lot of free time.

Facebook held their second annual Hacker Cup this past January and I was fortunate enough to see that the qualification round was being held over a free weekend. That Saturday, I spent a few hours at the grindstone cranking out solutions to two of the three problems (only one correct solution was needed to progress.)

The first challenge I tried was "Alphabet Soup." Basically, Facebook provided you with a string of random characters and you had to determine the number of times you could spell "HACKERCUP" with the given letters. My solution was written early in the morning (for a high school student) in C#, and oh god, is it ugly. Not only is it ugly, but it didn't even work! I'm inclined to believe it had something to do with line endings and/or my complete inability to efficiently code in C#. But I'll just blame Windows line endings.

The only other problem I was able to do was "Billboards." Facebook gave you a string with the width, height, and text for a hypothetical billboard to be printed in a monospace font. You were to find the maximum size the font could be to fill the billboard. My solution was a perl script that took me a good 5 hours to perfect (can't wait to get formal training in this kind of thing!). I'll provide it here:

```#!/usr/bin/perl

use strict;
use warnings;
use integer;

my \$filename = \$ARGV[0];
my \$file;

open \$file, \$filename or die \$!;

my @lines = <\$file>;

close \$file;

my \$cases = \$lines[0];

for(my \$c = 1; \$c <= \$#lines; \$c++) {
my \$space1 = index(\$lines[\$c], ' ');
my \$space2 = index(\$lines[\$c], ' ', \$space1 + 1);

my \$width = substr(\$lines[\$c], 0, \$space1);
my \$height = substr(\$lines[\$c], \$space1 + 1, \$space2 - \$space1);
my \$s = substr(\$lines[\$c], \$space2 + 1);

chomp(\$s);

my \$size = 0;
my \$currentRow = 0;
my @rows;
my @words = split(/ /, \$s);

W: while((\$currentRow + 1) * \$size <= \$height) {
\$currentRow = 0;
\$size++;
@rows = ();

for(my \$w = 0; \$w <= \$#words; \$w++) {

my \$test;
if( !defined(\$rows[\$currentRow]) ) {
\$test = \$words[\$w];
} else {
\$test = \$rows[\$currentRow] . ' ' . \$words[\$w];
}

if( (length(\$test) * \$size) <= \$width) {

\$rows[\$currentRow] = \$test;

} else {

if(defined(\$rows[\$currentRow])) {

\$currentRow++;
redo;

} else {
last W;
}
}
}

# strictly for diagnostic purposes!
# print join("\n", @rows) . "\n\n";
}

print "Case #" . \$c . ": " . (\$size-1)  . "\n";

}

```
I acknowledge that this is pretty ugly. Actually, it's quite a bit uglier than I remember it being (I'm looking at you, "`last W;`"!)
Believe it or not, this one got me a correct solution, which means I made it on to Round One. I didn't get any further than that, but hey! It's something.

(Facebook has posted overviews of the qualification round problems and potential solutions on their Hacker Cup page, if you're interested.)