+1 (315) 557-6473 

Program To Perform A Coffee Search Problem In Python Assignment Solution.


Instructions

Objective
Write a program to perform a coffee search problem in python.

Requirements and Specifications

Vyasa has to complete a python assignment overnight. He has to write n lines of code before morning. He is dead tired and he tries drinking some black coffee to keep him awake. But each time he drinks a cup of coffee he stays awake for a short amount of time but his productivity goes down by a constant factor k.
This is how he plans to write the program. He will write the first v lines of code, then drink his first cup of coffee. Since his productivity has gone down by a factor of k he will write v // k lines of code. He will have another cup of coffee and then write v // k**2 lines of code. He will have another cup of coffee and write v // k**3 lines of code and so on. He will collapse and fall asleep when v // k ** p becomes 0.
Now Vyasa does want to complete his assignment and maximise on his sleep. So he wants to figure out the minimum allowable value of v for a given productivity factor that will allow him to write at least n lines of code before he falls asleep.
Source Code
import time
# Input: v an integer representing the minimum lines of code and
# k an integer representing the productivity factor
# Output: computes the sum of the series (v + v // k + v // k**2 + ...)
# returns the sum of the series
def sum_series (v, k):
    sum = 0
    curr = v
    while curr > 0:
      sum += curr
      curr = int(curr / k)
    return sum
# Input: n an integer representing the total number of lines of code
# k an integer representing the productivity factor
# Output: returns v the minimum lines of code to write using linear search
def linear_search(n, k):
    curr = 1
    while sum_series(curr, k) < n:
      curr += 1
    return curr
# Input: n an integer representing the total number of lines of code
# k an integer representing the productivity factor
# Output: returns v the minimum lines of code to write using binary search
def binary_search(n, k):
    top = n
    bottom = 1
    while top - bottom > 1:
      middle = int((top + bottom)/2)
      result = sum_series(middle, k)
      if result < n:
        bottom = middle
      else:
        top = middle
    return top
# Input: no input
# Output: a string denoting all test cases have passed
def test_cases():
    # write your own test cases
    ns = [511, 365]
    ks = [2, 3]
    sols = [256, 244]
    for i in range(0, len(ns)):
        linear = linear_search(ns[i], ks[i])
        binary = binary_search(ns[i], ks[i])
        assert sols[i] == linear
        assert sols[i] == binary
    return "all test cases passed"
def main():
    test_cases()
    in_file = open("work.in", "r")
    out_file = open("work.out", "w")
    num_cases = int((in_file.readline()).strip())
    for i in range(num_cases):
        inp = (in_file.readline()).split()
        n = int(inp[0])
        k = int(inp[1])
        start = time.time()
        out_file.write("Binary Search: " + str(binary_search(n, k)) + '\n')
        finish = time.time()
        out_file.write("Time: " + str(finish - start) + '\n')
        out_file.write('\n')
        start = time.time()
        out_file.write("Linear Search: " + str(linear_search(n, k)) + '\n')
        finish = time.time()
        out_file.write("Time: " + str(finish - start) + '\n')
        out_file.write('\n')
        out_file.write('\n')
if __name__ == "__main__":
    main()