Facebook Hacker Cup 2012 - Qualification

The Facebook Hackercup 2, electric boogaloo. Last year Facebook hosted their first
programming competition. Despite a few technical flaws early on, overall it was pretty
good. I think I made it to the third round last year. At the time I had just started
college and programming, so I felt pretty good with how far I got. Hopefully this time
around I'll be able to get at least a bit further. The qualification round ended on
Monday and I'm fairly confident that I got two out of the three problems correct (you
only need one correct answer to move on to the next round). I'll present and talk a bit
about my solutions here.

Alphabet Soup

This problem was probably the easiest of the three. Paraphrasing
the problem statement, essentially you need to determine how many times you can form the
word "HACKERCUP" from a given string. The example input file is given as

5
WELCOME TO FACEBOOK HACKERCUP
CUP WITH LABEL HACKERCUP BELONGS TO HACKER
QUICK CUTE BROWN FOX JUMPS OVER THE LAZY DOG
MOVE FAST BE BOLD
HACK THE HACKERCUP

and your output file should look like:

Case #1: 1
Case #2: 2
Case #3: 1
Case #4: 0
Case #5: 1

For this round I decided to use Python. It's what I've used to solve many Project Euler
questions, so I can comfortable solving problems with it. So first, processing the input
is fairly straightforward.

def process_input(file_path):
    with open(file_path, 'r') as input:
        # first line is number of cases
        num_cases = int(input.readline().rstrip())
        # each remaining line represents a case
        cases = list(case.rstrip() for case in input.readlines())
    return cases

Open the file and grab the cases, stripping off newline characters. Now to actually deal
with a case. Forewarning, my algorithm is terrible. The runtime is fine, but my
implementation is so roundabout that when I read it now I cringe. I'll mention a much
better way to do this after I present my solution. So here's the code:

def eval_case(case):
    word = list('HACKERCUP!')
    word_list = [list('HACKERCUP!')]
    for char in case:
        if char in word:
            for chance in word_list:
                if char in chance:
                    chance.remove(char)
                    flag = True
                    break
                if flag:
                    word_list.append(list('HACKERCUP!'))
    count = 0
    for word in word_list:
        if word == ['!']: 
            count += 1
    return count

word is just a list of the characters in the string
"HACKERCUP!". word_list is a running list of "HACKERCUP!" strings that may have
some characters removed. My algorithm is something like this:

1. Look at each character in the case.
2. If that character is in word then look
   at word_list
3. If that character is in a word in word_list remove it
   from that word and add a new "HACKERCUP!" string to the list
4. Once all the characters have been looked at, the number of
   "!"'s left in word_list are the number of complete words
   that were formed

Wow. Wow wow wow wow. This is why I'm glad I've started this blog. I knew that this
algorithm was stupid, but I did not realize just how stupid until I just wrote this
out. What I meant to implement was a list of strings that kept track of how many partial
"HACKERCUP" strings could be formed. When a character matched the string but was NOT
found in the list, that's when the list should grow. For some reason I wrote it as
WHENEVER the char is found in the list, the list grows. Luckily this didn't affect the
output of the program, but it did make it way more memory intensive. I really do not want
to talk about this piece of not good stuff anymore. But anyway, here's how I tie it
together:

# import was at top of file, of course
import sys

def solve(file):
    cases = map(lambda case: eval_case(case), process_input(file))
    with open('output.txt', 'w') as out:
        for idx, val in enumerate(cases):
            out.write("Case #%i: %i\n" % (idx+1, val))
        
solve('./' + sys.argv[1])

So to solve my case I just put the input file into the same folder as my script and
run python alphabet_soup.py input.txt and the output file output.txt is
generated for submission. The one thing I had to look up for this snippet was the
line for idx, val in enumerate(cases):, which gets me both the index and the
value for my for loop.


What was the good solution, you ask? Luckily I live with
two other EECS students who are much more experienced. They have and continue to teach me
a lot. Their solution was so much nicer. Essentially you make a dictionary mapping
characters that occur in "HACKERCUP" to the number of times they occur in the case. Scale
the value for 'c' by 1/2 (to account for the fact that there are two 'c's in "HACKERCUP")
and take the min of all of the values in the dictionary. Much nicer. Linear time,
constant memory. Ah well, we all managed to get it right in the end.

Conclusion

I am writing this conclusion on Febuary 29th. More than a month after I meant to post
this. I don't really have anything more to say, I just wanted to wrap it up and post
this. I'll post my upcoming plans for blogging soon.