Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Bob's Financial Planning

Bob lives in Pecunia. It is a small island city completely governed by the Pecunia City Council (PCC). PCC has decided to encourage foreign investments in the city by waiving several taxes for establishing companies. Consequently, the city has attracted several high skilled workers from across the country. The demand for condos has gone up.

During his career, Bob saved some money. He realized that this is the right time to invest in real estate because the demand is soaring. He decided to purchase condos of different sizes and rent them out. He collected data about condos available for purchase from the classified ads in the local newspaper Pecunia Tribune.

PCC has laid out a plan in order to build infrastructure hand in hand with the amount of investment. According to this, the influx of companies to various parts of the city will be carefully controlled for the next few years. Bob used this data to estimate the prices of the condos in the coming years.

An important factor to keep in mind is property taxes. Bob has to pay a tax to PCC at the end of every month for all the properties he owned during that month. It is a fixed percentage of the estimated value of the property on that date. Also, whenever Bob purchases a property, he needs to pay a fixed percentage of its value as registration fee to the government. Bob is confident that the property tax rate and registration fee percentage will not change during his life time.

Bob has a secure job that guarantees a steady stream of income. He is confident of saving a fixed percentage of his monthly salary (after tax) for investments until his retirement. Also, he gets an annual bonus that can completely be used for investments. He wants to invest his current savings, future savings and the rent he would obtain from his properties. He needs your help in coming up with an investment plan such that his estimated net worth at the time of his retirement is maximized. Net worth is defined as the value of all his properties plus any liquid cash.

Your input is a list of lines. The values in each line are separated by spaces. The significance of each line in the input is explained below.

  • Number of years to Bob’s retirement [N]
  • Bob’s current savings [C]
  • Percentage of Bob’s monthly (after tax) salary that he could use towards investing
  • N lines follow with each line containing two numbers – monthly salary for the year (after tax) [Si], annual bonus for the year (after tax) [Bi]. i.e., the first line corresponds to the current year; the next line corresponds to the next year and so on so forth
  • Property tax percentage per month [T]
  • Property registration fee percentage [F]. This is paid only once when Bob purchases a property
  • Number of condos available for purchase [P]
  • Each of the P lines that follow contains the details of a condo available for purchase. On each line, there will be one or more 4-tuples (i.e., a sequence of 4 values). Those 4 values represent: year [Yi]; month [Mi]; estimated rent [Ri]; estimated market value [Vi]. For example, the 4-tuple Y1, M1, R1, V1 states that effective from the year Y1 and (the 1st of) month M1, the estimated rent and market value of the condo are R1 and V1 respectively. The estimated rent and market value of the condo are assumed to remain the same until Y2 and M2. Then on, R2 and V2 will apply. Note that the first tuple will always have with Y1 = 1, M1 = 1, and the tuples are chronologically ordered. i.e., the input always has Yi <= Yi+1and if Yi = Yi+1 then Mi < Mi+1.

Output should contain exactly one line: Bob's estimated worth when he retires rounded to 2 decimal points.

Assumptions

  • Input is valid.
  • All the money is in the same currency. Input numbers are positive floating point values rounded to 2 places after the decimal point. They do not have any formatting (e.g., hundred thousand is input as 100000 or 100000.00 but not as 100,000). Bob's maximum worth at the end of N years is guaranteed to be less than a billion.
  • Today is January 1st 2012.
  • Bob's annual bonus is deposited on the December 31st of each year. Bob wants to retire at the age of 60. He plans to retire on the December 31st (on or after his 60th birthday). Note that he would get a bonus on that day.
  • Bob's salary will remain the same for each month of any given year. It is deposited at the end of each month. His tenants pay each month's rent at the end of it.
  • The condos are on a month-to-month lease. Moving out of a condo can happen only on the last day of a month. Moving into a condo can happen only on the 1st of any month i.e., there is no scope for renting a condo for a part of a month.
  • Assume that all the properties that Bob did not purchase are available for sale at all the time during the next N years.
  • The maximum number of properties available for purchase at any time [P] is less than or equal to 15.
  • The banks in Pecunia do not give any interest for keeping Bob's money with them. Also, he is completely averse to borrowing money from people or organizations.
  • Bob does property transactions (i.e., purchasing and selling) only at the end of a month.

Example

Input

1
651.70
59
12.29 103.89
0.42
2
4
1 1 72.62 741.97 1 6 67.66 646.20 1 7 58.83 563.79 1 10 57.95 526.55 1 12 62.73 656.49 
1 1 80.65 832.35 1 11 92.79 951.74 1 12 102.73 975.86 
1 1 111.34 976.17 1 3 105.85 895.93 1 7 110.76 920.65 1 10 102.63 887.31 1 11 104.72 1094.79 1 12 94.91 898.43 
1 1 67.15 564.28 1 11 65.47 553.74 1 12 52.53 530.26 

Output

2248.64

Input

4
272.01
11
12.22 101.46
13.72 105.20
14.20 107.20
15.31 108.27
0.75
3
3
1 1 99.86 864.66 1 6 93.59 677.42 3 12 73.30 515.47 4 11 89.02 550.38 4 12 68.55 509.27
1 1 65.54 806.77 4 12 80.03 986.16
1 1 69.38 592.65 4 7 53.67 533.91 4 11 50.11 520.79 4 12 50.19 640.42

Output

2145.52

Goal

Compute the answer as fast as possible

Details

This was a question from a programming contest I was recently part of. I would prefer code written in C/C++, Java, Python, ie common languages but any language is fine. I made an implementation too which I added as an answer.

share|improve this question
add comment

1 Answer 1

Python 2

numYears = int(raw_input())
initialWealth = float(raw_input())
pctMonthly = float(raw_input())/100
monthlyPay = []
yearlyBonus = [0]
for i in xrange(numYears):
    data = raw_input().split()
    monthlyPay.append(float(data[0]))
    yearlyBonus.append(float(data[1]))
propTax = float(raw_input())/100
propReg = float(raw_input())/100
numCondos = int(raw_input())
condoData = dict()
for i in xrange(numCondos):
    data = raw_input().split()
    data = [(i, 12*(int(data[4*j])-1)+int(data[4*j+1])-1,
        float(data[4*j+2]), float(data[4*j+3])) for j in xrange(len(data)/4)]
    j = 1
    while j < len(data):
        k = data[j-1][1]
        while k < data[j][1]:
            condoData[(i, k)] = data[j-1][2:]
            k += 1
        j += 1
    j -= 1
    k = data[j][1]
    while k < 12*numYears:
        condoData[(i, k)] = data[j][2:]
        k += 1

res = 0
def visit(state):
    if state[0] == 12*numYears:
        global res
        res = max(res, state[1]+yearlyBonus[numYears])
    else:
        owned = list(state[2])
        avail = [x for x in xrange(numCondos) if x not in owned]
        baseValue = state[1]+monthlyPay[state[0]/12]*pctMonthly # collect monthly
        if state[0] % 12 == 0:
            baseValue += yearlyBonus[state[0]/12] # collect bonus
        for c in owned:
            baseValue += condoData[(c, state[0])][0] # collect rent
            baseValue -= condoData[(c, state[0])][1]*propTax # pay prop tax
        for n in xrange(2**numCondos):
            bitmask = bin(n)[2:].zfill(numCondos)
            maskOwned = [x == "1" for x in bitmask[:len(owned)]] # T = sell
            maskAvail = [x == "1" for x in bitmask[len(owned):]] # T = buy
            nextCondos = list(state[2])
            nextValue = baseValue
            for i in xrange(len(owned)):
                if maskOwned[i]: # sell condo
                    nextCondos.remove(owned[i])
                    nextValue += condoData[(owned[i], state[0])][1]
            totalCost = 0
            for i in xrange(len(avail)):
                if maskAvail[i]: # buy condo
                    nextCondos.append(avail[i])
                    totalCost += condoData[(avail[i], state[0])][1]*(1+propReg)
            if totalCost <= nextValue:
                nextValue -= totalCost
                nextState = (state[0]+1, nextValue, tuple(nextCondos))
                visit(nextState)

initialState = (0, initialWealth, ())
visit(initialState)
print res

My implementation basically visualizes the data as a tree where each edge is a decision to buy and/or sell some subset of the condos. I use a depth-first-search styled approach to visit every state and follow each path to the end to avoid storing the entire tree in memory (which would take up exponential amount of space depending on the number of condos).

My code computes the solution to the input in about 2 minutes on my pc.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.