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()