Code organisation
Instead of building cases
, then use it to build credits
and items
then use them to fix the problem, you could do things in a more straightforward way with less temporary containers.
with open(sys.argv[1]) as file_:
next(file_)
for i, case in enumerate(zip(*[file_]*3)):
credit = int(case[0])
prices = [int(item) for item in case[2].split()]
for tow_items in combinations(prices, 2):
if sum(tow_items) == credit:
print("Case #{}:".format(i+1), end=' ')
print(' '.join([str(i+1) for i, price in enumerate(prices) if price in tow_items]))
Also, it would probably make sense to split your code into multiple functions : you could write a function handling input/ouput and a function to handle the algorithmic part of the problem.
def get_indices_with_sum(prices, credit):
for tow_items in combinations(prices, 2):
if sum(tow_items) == credit:
return [i for i, price in enumerate(prices) if price in tow_items]
assert False # Is not suppose to happen
def run_on_file(filename):
with open(filename) as file_:
next(file_)
for i, case in enumerate(zip(*[file_]*3)):
credit = int(case[0])
prices = [int(item) for item in case[2].split()]
j, k = get_indices_with_sum(prices, credit)
print("Case #{}: {} {}".format(i+1, j+1, k+1))
run_on_file(sys.argv[1])
Now, different great things are easily doable :
- you can your call to run_on_file
behind an if __name__ == "__main__":
guard to have reusable code on one hand (you could need the get_indices_with_sum
function to solve other problems) and code actually doing something on the other hand.
- you can write tests to check your code automatically. The great thing is that the problem description gives you a few examples.
def unit_tests():
j, k = get_indices_with_sum([5, 75, 25], 100)
assert (j, k) == (1, 2)
j, k = get_indices_with_sum([150, 24, 79, 50, 88, 345, 3], 200)
assert (j, k) == (0, 3)
j, k = get_indices_with_sum([2, 1, 9, 4, 4, 56, 90, 3], 8)
assert (j, k) == (3, 4)
if __name__ == "__main__":
unit_tests()
# run_on_file(sys.argv[1])
At this step, your code is already better but we haven't improved performance. We've only make improvements easier to write and to test.
Algorithm
In order to write a faster algorithm, I am assuming we are interested in the case when we are given a store with a huge number of elements n
(called I
in the problem description).
At the moment, you (potentially) iterate over all combinations and there are n * (n-1)/2
. Assuming you always find what you are looking for, we may assume that you go through n * (n-1) / 4
combinations in average. Then, when the solution is found, your iterate once more over prices
so you roughly perform n + n * (n-1) / 4
operations. We usually keep only the asymptotic behavior of the program and remove the constant factor and say that your program is 'O(n^2)'.
You could try to run your program with bigger and bigger inputs and see the time it takes. Usually when you take a input twice as big, your algorithm will take 4 times as much time.
If you want to give it a try, I've tweaked the original test to add the following cases (adding elements costing 101
in the store doesn't change what you can get with 100 dollars):
nb_added_elements = 10000
j, k = get_indices_with_sum([101] * nb_added_elements + [5, 75, 25], 100)
assert (j, k) == (nb_added_elements + 1, nb_added_elements + 2)
j, k = get_indices_with_sum([5, 75, 25] + [101] * nb_added_elements, 100)
assert (j, k) == (1, 2)
The problem you are trying to solve is pretty common and has a O(n) solution on a sorted array (you'll find explanations looking for "array find pair sum" in our favorite search engine).
Your case is slightly more complicated because the array is not sorted and sorting it would cause a mess in the indices.
Many solutions are possible : either build an array with value and index before sorting it by value and/or keep a copy of the unsorted array so that you can find its initial position back at the end.
The resulting solution is likely to be O(n*log(n)) because of the sorting (other operations such as lookup/copy and obviously the proper algorithm are only O(n) and as such considered negligeable).
Other details
count
and enumerate
can be given a starting position (defaulting to 0
) so that you don't have to add 1 yourself if you want to count from 0.