rhood.py

CACHE = {}

def compute(w, h):

    # Base case, nothing
    if 0 in [w, h]:
        return 1

    try:
        return CACHE[(w, h)]
    except KeyError:
        pass

    results = [0]
    # Check 4x1
    if w >= 4:
        first = compute(w - 4, h)
        second = compute(4, h - 1)
        if first > 0 and second > 0:
            results.append(first + second - 1)

    if h >= 4:
        first = compute(w - 1, 4)
        second = compute(w, h - 4)
        if first > 0 and second > 0:
            results.append(first + second - 1)

    # Check 1x4
    CACHE[(w, h)] = sum(results)
    return CACHE[(w, h)]

def get_prime(total):
    if total is 1:
        return 1
    for num in reversed(xrange(2, total)):
        not_prime = False
        for i in xrange(2, num):
            if num % i == 0:
                not_prime = True
                break
        if not_prime is False:
            return num

if __name__ == '__main__':
    total = compute(1, 4)
    print get_prime(total)