Solves 538 Riddler Classic for Feb 22 2019

538_count_bridge_bids.py

counts = {}
enable_doubling = False  # change to true for extra credit

def count_possible_bids(current_bid, n_passes, n_doubles):
    if (n_passes == 3 and current_bid != -1) or n_passes == 4:
        return 1
    if (current_bid, n_passes, n_doubles) in counts:
        return counts[(current_bid, n_passes, n_doubles)]
    result = 0
    for n in range(current_bid + 1, 28):
        result += count_possible_bids(n, 0, 0)  # increase the bid
    result += count_possible_bids(current_bid, n_passes + 1, n_doubles)  # pass
    if enable_doubling:
        if (n_passes == 0 or n_passes == 2) and n_doubles == 0 and current_bid != -1:
            result += count_possible_bids(current_bid, 0, 1)  # double
        if (n_passes == 0 or n_passes == 2) and n_doubles == 1 and current_bid != -1:
            result += count_possible_bids(current_bid, 0, 2)  # redouble
    counts[(current_bid, n_passes, n_doubles)] = result
    return result

print count_possible_bids(-1, 0, 0)