1
\$\begingroup\$

I did this programming challenge. Part C of the challenge, is to find the salary you have to save every month to be able to buy a house in 36 months.

This is my first time using bisection search so I just want to make sure that I did it correctly. I question the efficiency of my program because in test case 2 for part C, the supposed number of guesses is 9, but my program guesses 13 times.

annual_salary = int(input('Enter your annual salary.'))
total_cost = 1000000
semi_annual_raise = .07
portion_down_payment = total_cost * 0.25
current_savings = 0
r = 0.04
guesses = 1
low = 0
high = 1

while abs(portion_down_payment-current_savings) > 100:
    portion_saved = (low + high) / 2
    salary = annual_salary
    current_savings = 0

    for month in range(1, 37):
        if month % 6 == 1 and month != 1:
            salary += salary*semi_annual_raise
        current_savings += current_savings*r/12
        current_savings += salary/12 * portion_saved

    if current_savings >= portion_down_payment:
        high = portion_saved
    elif current_savings < portion_down_payment:
        low = portion_saved

    portion_saved = (low+high)/2
    guesses += 1

print(portion_saved, guesses)
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

I don't think your code is an inefficient bisection search. The example which needed fewer iterations could simply be getting lucky and getting within the $100 terminal condition on one of its earlier steps. That said, here are a couple of implementation pointers:

Don't recalulate salary

The salary used in the loop, increases every six months. But it does not change based on savings rate, so is the same for every guess. Therefore calculate it once before starting the guessing. It could look something like this:

monthly_salary = [annual_salary / 12]
for month in range(2, 37):
    monthly_salary.append(monthly_salary[-1])
    if month % 6 == 1:
        monthly_salary[-1] *= (1 + semi_annual_raise)
        

Or using itertools, something like this:

import itertools as it
import operator
salaries = [annual_salary / 12] + [1 + semi_annual_raise] * 5
monthly_salaries = list(it.chain.from_iterable(
    (x,) * 6 for x in it.accumulate(salaries, operator.mul)))          
    

Consider using itertools.accumulate()

The loop which sums up the savings can be done using itertools.accumulate(). Basically you define a function which is passed the previous total and an element from an iterable. Then returns the next total.

def accum(total, salary):
    return total * (1 + r / 12) + salary * portion_saved

Then the function, and an iterable is passed to accumulate:

*_, current_savings = it.accumulate(monthly_salaries, accum)

Finally the *_, current_savings = ... can be used to gather the last item in an iterable.

The *_ is rather cryptic. The _ is just a variable name that is often used in Python to indicate that it is unneeded. The * is used for variable expansion. See Pep 448 for more details.

Revamped code:

annual_salary = 150000
total_cost = 1000000
semi_annual_raise = .07
portion_down_payment = total_cost * 0.25
current_savings = 0
r = 0.04
guesses = 0
low = 0
high = 1

import itertools as it
import operator
salaries = [annual_salary / 12] + [1 + semi_annual_raise] * 5
monthly_salaries = [0] + list(it.chain.from_iterable(
    (x,) * 6 for x in it.accumulate(salaries, operator.mul)))

portion_saved = (low + high) / 2
while abs(portion_down_payment - current_savings) > 100:

    def accum(total, salary):
        return total * (1 + r / 12) + salary * portion_saved

    *_, current_savings = it.accumulate(monthly_salaries, accum)

    if current_savings >= portion_down_payment:
        high = portion_saved
    else:
        low = portion_saved

    portion_saved = (low + high) / 2
    guesses += 1

print(portion_saved, guesses)
\$\endgroup\$
9
  • \$\begingroup\$ Very well done, I was working on this as well to section C of the instructions, it wants to use 0 to 10000 and then convert back, as well could you make this code without imports? \$\endgroup\$ Sep 2, 2018 at 22:15
  • \$\begingroup\$ The code from the question does not have imports. And it works. Also of the two suggestions in this answer, the first is done two ways, one of which does not use imports. \$\endgroup\$ Sep 2, 2018 at 22:17
  • \$\begingroup\$ Okay I see this, one more question, I understand your code acheives the proper solution, but the question on MIT seems to revolve around finding the best interest rate for a 36 month frame, how does this account for the 36 month time frame, seeing as the solution you get is the desired interest rate for 36 months, how did you account for that ? \$\endgroup\$ Sep 2, 2018 at 22:21
  • \$\begingroup\$ Sorry I just was stumped and want to learn. The bisection search is supposed to revolve around concluding the best interest rate for 36 months, again your solution achieved this, just curious I dont see no mention of 3 years in here or 36 months, thank you \$\endgroup\$ Sep 2, 2018 at 22:23
  • 1
    \$\begingroup\$ 6 * 6 = 36. Suggest stepping through the code in a debugger to better understand the implementation. \$\endgroup\$ Sep 2, 2018 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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