facebook Hacker Cup 2012 Qualification - solution for billboards

by Christian Harms on Wed, 01/25/2012 - 19:50

The second problem from this year facebook hackercup sound like the classic knapsack problem. But the solution is much easier (words are in fixed sort order). Feel free to find a smarter algorithm or comment my python solution.

problem description

We are starting preparations for Hacker Cup 2013 really early. Our first step is to prepare billboards to advertise the contest. We have text for hundreds of billboards, but we need your help to design them.

The billboards are of different sizes, but are all rectangular. The billboard widths and heights are all integers. We will supply you with the size in inches and the text we want printed. We want you to tell us how large we can print the text, such that it fits on the billboard without splitting any words across lines. Since this is to attract hackers like yourself, we will use a monospace font, meaning that all characters are of the same width (e.g.. 'l' and 'm' take up the same horizontal space, as do space characters). The characters in our font are of equal width and height, and there will be no additional spacing between adjacent characters or adjacent rows. If you print a word on one line and print the next word on the next line, you do not need to print a space between them.

Let's say we want to print the text "Facebook Hacker Cup 2013" on a 350x100" billboard. If we use a font size of 33" per character, then we can print "Facebook" on the first line, "Hacker Cup" on the second and "2013" on the third. The widest of the three lines is "Hacker Cup", which is 330" wide. There are three lines, so the total height is 99". We cannot go any larger.

my python solution

My first step was to decide the starting fontsize. I choosed the largest word with little help of the map function and calculated the fontsize. Words will not wrapped so the largest word has to fit in the billboard width.

Then I started to put the words into the billboard. If the word does not fit into the actual line, I increased the rowCount. If all all words fit into the billboard border the fontsize is the result. If not I decreased the fontsize by 1 and started again. This sounds not optimal but solved the input set in 0.1 second.

import sys
 
input = file(sys.argv[1])
 
for case in range(int(input.readline())):
    words = input.readline().strip().split()
    width = int(words.pop(0))
    height = int(words.pop(0))
 
    # find starting size
    fontsize = width/max(map(len, words))
 
    # iterate over fontsize until a result or fontsize=0
    while fontsize:
        col = len(words[0])
        row = 0
        for word in words[1:]:
            if col+1+len(word) > width/fontsize:
                row += 1
                col = len(word)
                if row >= height/fontsize:
                    break
            else:
                col += 1+len(word)
        #word check loop ended - does it fit?
        if row >= height/fontsize:
            fontsize -= 1  
        else:
            break
    #while
    print "Case #%d: %d" % (case+1, fontsize)
input.close()

Here the test data to try the solution with python.

input data	result data
5 20 6 hacker cup 100 20 hacker cup 2013 10 20 MUST BE ABLE TO HACK 55 25 Can you hack 100 20 Hack your way to the cup/pre>	Case #1: 3 Case #2: 10 Case #3: 2 Case #4: 8 Case #5: 7

top score java solution

The c++ solutions in the top 10 of the hackercup scroreboard are long and (for non-active C++ coder) not easy to read. I choosed the nr.10 entry with a java solution. He had coded many helper functions for reading input data but the solve-method looks simular my algorithm. The only change is starting with fontsize 0 and running until the words dont fit into the billboard. It depends on the fontsize and if billboard are higher than wider.

public void solve() throws Exception {
        int tests = iread();
        for (int ntest = 1; ntest <= tests; ntest++) {
                int w = iread(), h = iread();
                String[] s = in.readLine().split(" ");
                int ans = 0;
                for (int size = 1; size <= 1000; size++) {
                        int ww = w / size, hh = h / size;
                        int pos = -1, line = 0, cur = 0;
                        while (cur < s.length && line < hh) {
                                if (pos + 1 + s[cur].length() <= ww) {
                                        pos += 1 + s[cur].length();
                                        cur++;
                                } else {
                                        line++;
                                        pos = -1;
                                }
                        }
                        if (cur < s.length)
                                break;
                        ans = size;
                }
                out.write("Case #"+ntest+": "+ans + "\n");
        }
}

third problem auction ...

Ok - the third problem will not be a blogpost on united-coders.com. I was trying to solve this problem - but I missed it. And only 22 people (of 5947 qualified coder) had submitted correct answers for all three problems and 28 correct solutions for the auction problem! You can read the solution text (not code) for this problem in an post on facebook.