Facebook Billboard Problem

billboard.py

#!/usr/bin/env python
#
# BillBoard problem solution
# Vishesh Yadav
#
# Note: Lot many easy optimizations can be made, but for the sake of 
#       clarity, let it be.
#

from math import sqrt

def line_combinations(width, height, dim, words):
    if dim is 0 or len(words) is 0:
        return True
    elif len(words) is 1 and width < dim * len(words[0]):
        return False
    elif height < dim:
        return False
    elif width > dim * len(" ".join(words)): # not really needed, still
        return True

    fit_first_line_till = -1
    for i in range(len(words)):
        if width < dim * len(" ".join(words[0:i+1])):
            if fit_first_line_till is -1:
                return False
            else:
                break
        fit_first_line_till = i

    line = words[0:fit_first_line_till+1]
    restline = words[fit_first_line_till+1:]

    return line_combinations(width, height - dim, dim, restline)


def billboard(width, height, text):
    words = text.split()
    area = width * height
    avg_dim = int(sqrt(area/(len(text) - len(text.split(' ')) - 1)))

    for w in words:
        if avg_dim * len(w) > width:
            avg_dim = avg_dim - 1

    while not line_combinations(width, height, avg_dim, words):
        avg_dim = avg_dim - 1

    return avg_dim


x = int(raw_input())

for i in range(x):
    line = raw_input().split()
    w = int(line[0])
    h = int(line[1])
    t = " ".join(line[2:])
    print "Case #%i: %i" % (i + 1, billboard(w, h, t))