SRM483 - div2 - level two

srm483_div2_level2.py

#! /usr/bin/env python
# -*- coding: utf-8 -*-

"""SRM483 - div2 - level two

Elly and some of her friends (possibly none) are going 
to the movies. Their company consists of numFriends people, 
including Elly. Since they don't want to be spread across 
the entire hall, they decided to sit either in the same 
row or in the same column (though not necessarily next 
to one another).

Your are given a String[] hall representing the layout 
of seats in the theater that are already taken. The j-th 
character of the i-th element of hall will be '#' if the 
seat at row i, column j is already taken and '.' if it 
is empty.

Return the number of different ways for Elly and her friends 
to choose numFriends different empty seats so that their 
seating requirement is fulfilled. Two ways are considered 
different if there exists a person in their company that 
will sit in different seats in these two ways.

Definition:
    Class: MovieSeating
    Method: getSeatings
    Parameters: int, String[]
    Returns: long
    Method signature: long getSeatings(int numFriends, String[] hall)
"""

class MovieSeating(object):
    """The Boring Store Div Two

    Constraints:
        - numFriends will be between 1 and 8, inclusive.
        - hall will contain between 1 and 50 elements, inclusive.
        - Each element of hall will contain between 1 and 50 characters, inclusive.
        - All elements of hall will contain the same number of characters.
        - Each character in hall will be either '.' or '#'.

    >>> seating = MovieSeating()
    >>> print seating.getSeatings(2, [".#..", ".##.", "....", ])
    34
    >>> print seating.getSeatings(2, ["..#", ".##", "...", ])
    16
    >>> print seating.getSeatings(5, ["..####..", ".###.##.", ".######.", "#.#.#.#.", ])
    0
    >>> print seating.getSeatings(8, ["........", ])
    40320
    >>> print seating.getSeatings(1, ["........", ])
    8
    """

    def __init__(self):
        pass

    def getSeatings(self, numFriends, hall):
        def get_seats(num, empty):
            res = 1
            for n in range(1, num+1):
                res *= empty
                empty -= 1
            return res

        res = 0

        # Check rows
        for r in hall:
            empty = len([c for c in r if c=='.'])
            if empty >= numFriends:
                res += get_seats(numFriends, empty)

        # Return if numFriends == 1
        if numFriends == 1:
            return res

        # Check cols
        for c in range(len(hall[0])):
            empty = len([r[c] for r in hall if r[c]=='.'])
            if empty >= numFriends:
                res += get_seats(numFriends, empty)
        return res

if __name__ == '__main__':
    import doctest
    doctest.testmod()