Facebook Hacker Cup 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.)