[Update@2012-01-24] I made a little mistake in a if...else... statement.

Facebook started Facebook Hacker Cup 2012 from January 20 at 4:00pm PST, and until January 23 at 4:00pm PST, the event is closed to receive submission.

There are three questions, when I learned the event, the event is already started and left me only near 16 hours to take some challenge.

I picked “Billboard problem”.

The original question

Billboards

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 350×100″ 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.

Input

The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case in the form “W H S”. W and H are the width and height in inches of the available space. S is the text to be written.

Output

Output T lines, one for each test case. For each case, output “Case #t: s”, where t is the test case number (starting from 1) and s is the maximum font size, in inches per character, we can use. The size must be an integral number of inches. If the text does not fit when printed at a size of 1″, then output 0.

Constraints

• 1 ≤ T ≤ 20
• 1 ≤ W, H ≤ 1000

The text will contain only lower-case letters a-z, upper-case letters A-Z, digits 0-9 and the space character. The text will not start or end with the space character, and will never contain two adjacent space characters. The text in each case contains at most 1000 characters

Example input

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

Example output

Case #1: 3
Case #2: 10
Case #3: 2
Case #4: 8
Case #5: 7

My Solution

I used Objective-C to resolve this problem. I created a Mac app project. Later I think it’s completely unnecessary. I will try to use maybe pure C or Cocoa Console later.

Here is the my solution on github

The key idea behind my solution is divide and conquer.

1. Find the possible max font size

1. Assume the billboard only show one line or one column, the MIN(width, height) will give the first guess of the max font size.
2. Assume all the characters without space will be layout on the billboard one by one, the biggest font to whole all characters will be our possible max font size. Because if we add any space or non-hyphenation constraints to layout, we must shrink the font to hold these extra constraints.

Here I used the D&C to find the possible max font size:

- (NSInteger)maxFontSizeForText:(NSString *)text 
                withTextInArray:(NSArray *)textInArray 
               constraintToArea:(NSInteger)rectArea 
                     withBounds:(NSDictionary *)bounds
{
  NSParameterAssert(text);
  NSParameterAssert(textInArray);
  NSParameterAssert(bounds);

  NSInteger upperSize = [[bounds objectForKey:UPPER_BOUND_KEY] integerValue];
  NSInteger lowerSize = [[bounds objectForKey:LOWER_BOUND_KEY] integerValue];
//  NSLog(@"*** finding max size between %4ld...%ld", lowerSize, upperSize);

  NSInteger upperArea = upperSize * upperSize * ([text length] - ([textInArray count] - 1));
  NSInteger lowerArea = lowerSize * ([text length] - ([textInArray count] - 1));

  // No need to go further, there will be one size suitable for rectArea
  if (1 >= (upperSize - lowerSize)) { // there could be a case of 0
    if (upperArea <= rectArea) {
      return upperSize;
    }else if (lowerArea <= rectArea){
      return lowerSize;
    }else {
      return 0;
    }
  }

  // Otherwise, we need to go recursive routine to find the max size in lower...upper
  NSInteger middleSize = lowerSize + ((upperSize - lowerSize) >> 1);
  NSInteger middleArea = middleSize * middleSize * ([text length] - ([textInArray count] - 1));
  if (middleArea > rectArea) {
    NSDictionary *boundsDict = [NSDictionary dictionaryWithObjectsAndKeys:
                                [bounds objectForKey:LOWER_BOUND_KEY], LOWER_BOUND_KEY,
                                [NSNumber numberWithInteger:middleSize], UPPER_BOUND_KEY,
                                nil];
    return [self maxFontSizeForText:text withTextInArray:textInArray constraintToArea:rectArea withBounds:boundsDict];
  }else {
    NSDictionary *boundsDict = [NSDictionary dictionaryWithObjectsAndKeys:
                                [NSNumber numberWithInteger:middleSize], LOWER_BOUND_KEY,
                                [bounds objectForKey:UPPER_BOUND_KEY], UPPER_BOUND_KEY,
                                nil];
    return [self maxFontSizeForText:text withTextInArray:textInArray constraintToArea:rectArea withBounds:boundsDict];
  }
}

2. Find the correct max font size

Try to fit the text start with possible max font, then shrink the font size to meet the constraints.

This is simple but have some complex if...else... statements.

[Update 2012-01-24] Thanks to Chong, the following algorithm failed to find the correct font size for Case #7, it should be 9 instead of 8, to fix this, I need to modify 2 places, change realFontSize = width/[aWord length]; to realFontSize--; and change realFontSize = height/(currentLineIndex + 1); to realFontSize--;

// Another core algorithm that will try and shrink the font size to fit the billboard
- (NSInteger)correctMaxFontSizeForNoHyphenationFor:(NSArray *)textInArray 
                                      constraintTo:(NSInteger)possibleMaxFontSize 
                                        boardWidth:(NSInteger)width 
                                       boardHeight:(NSInteger)height
{
  NSParameterAssert(textInArray);

  if (possibleMaxFontSize == 0) {
    return 0;
  }

  NSInteger realFontSize = possibleMaxFontSize;
  BOOL finished = NO;
  do {
    NSInteger currentLineWidth = 0;
    NSInteger currentLineIndex = 0;

    for (int idx= 0; idx < [textInArray count]; idx++) {
      NSString *aWord = [textInArray objectAtIndex:idx];
      NSInteger wordLengthAppliedFontSize = [aWord length]*realFontSize;
      // width is not enough for a single word
      if (wordLengthAppliedFontSize > width) {
        realFontSize = width/[aWord length];
        currentLineIndex = 0;
        currentLineWidth = 0;
        break;
      }

      // current word is safe for at least one line, see if it is safe to add to current line.
      if (currentLineWidth + wordLengthAppliedFontSize > width) {
        // need a new line
        currentLineIndex++;
        currentLineWidth = wordLengthAppliedFontSize;

      }else{
        currentLineWidth += wordLengthAppliedFontSize;
      }

      if (currentLineWidth + realFontSize < width) {
        // current line is safe for one more space.
        currentLineWidth += realFontSize;
      //}else{   //<- Here cause the case #1 failed
      }else if (idx != ([textInArray count] -1)){
        // need a new line
        currentLineIndex++;
        currentLineWidth = 0;
      }

      // height is not enough for the whole text
      if ((currentLineIndex + 1) * realFontSize > height){
        realFontSize = height/(currentLineIndex + 1);
        currentLineIndex = 0;
        currentLineWidth = 0;
        break;
      }
      // done.
      if (idx == [textInArray count] -1) {
        // last line
        finished = YES;
      }

    }

  } while (realFontSize > 0 && !finished);

  return realFontSize;
}

3. Verify it

I created some test cases to test on it. It includes some extra test cases that need to be omitted when read in the file.

Download my test cases

Meanwhile, Facebook has an input file, you can also download it.

Output

Here is my output, what’s yours? Whose one is correct?

Case #1: 30 //<- Wrong, should be 60
Case #2: 5
Case #3: 31
Case #4: 6
Case #5: 30
Case #6: 83
Case #7: 8      //<- Wrong, should be 9
Case #8: 80
Case #9: 21
Case #10: 4
Case #11: 31
Case #12: 21
Case #13: 30
Case #14: 21
Case #15: 30
Case #16: 21
Case #17: 4
Case #18: 21
Case #19: 4
Case #20: 4

After modified step2, I think the following result is correct:

Case #1: 60 
Case #2: 5 
Case #3: 31 
Case #4: 6 
Case #5: 30 
Case #6: 83 
Case #7: 9 
Case #8: 80 
Case #9: 21 
Case #10: 4 
Case #11: 31 
Case #12: 21 
Case #13: 30 
Case #14: 21 
Case #15: 30 
Case #16: 21 
Case #17: 4 
Case #18: 21 
Case #19: 4 
Case #20: 4 

It’s fun, I’m no longer qualified for next round now, good luck, my friends. (hope I can enter the qualification round. And so do you.)