2
\$\begingroup\$

I have been working on a quiz that I came across within a job application. I am not applying for the job, but I wanted to have a go at the problem.

An input file contains integers, both positive and negative (there might be some duplicates). Each line on the file has one integer.

Compute the number of y values within the range -10000 ≤ y ≤ 10000 such that there are distinct numbers a, b in the file where a + b = y.

You can download the file from http://s3.amazonaws.com/spacebalcony/cases.tar.bz2 (57MB). There are two test cases there for you to verify your program. Check the README file for the answers.

I came up with a solution using itertools but it is very slow.

from itertools import combinations, imap

with open('test1.txt', 'rU') as f:
    integers = sorted(list(set([int(item) for item in f])))

def check_item(x):
    item_total = sum(x)
    if all([item_total >= -10000, item_total <= 10000]):
        return True
    return False

print sum(imap(check_item, combinations(integers, 2)))

Does anyone have any suggestions to speed up the code?

For example, I have tried removing the largest and smallest numbers that could never be brought down within the range:

while (integers[0] + integers[-1]) < -10000:
    integers = integers[1:]

while (integers[0] + integers[-1]) > 10000:
    integers = integers[:-1]

This did not make much of a difference

\$\endgroup\$
3
\$\begingroup\$

The problem with the solution posted in the question is that it goes through all the possible combinations of two elements in the array when this is not really needed.

The pseudocode for a more efficient strategy would be as follows:

  • Read and sort the integers
  • For each integer (a), calculate the lowest and highest values of (b) that satisfy the inequality
  • Look for the position in the array for those values (take advantage of the values being ordered, use binary search)
  • Note that all the numbers between the two positions found satisfy the inequality since they are ordered

In python code, it should be something like this:

import bisect

MIN_SUM_VALUE = -10000
MAX_SUM_VALUE = 10000

with open('large.txt', 'rU') as f:
    integers = sorted(set(int(item) for item in f))

count = 0
for index, a in enumerate(integers):
    # Low and high values of b that still satisfy the inequality
    b_low = MIN_SUM_VALUE - a
    b_high = MAX_SUM_VALUE - a

    # Look for the index in the array for the values above
    b_low_index = bisect.bisect_left(integers, b_low, index + 1)
    b_high_index = bisect.bisect_right(integers, b_high, index + 1)

    # Increment count by the number of values found
    count += b_high_index - b_low_index

print count

Note that the way to avoid repetitions is to restrict the binary search to look for b values whose position is after the a values in the array (that's the index + 1 parameter).

Edit: To get the actual sums printed the following snippet can be used:

for b_index in range(b_low_index, b_high_index):
    b = integers[b_index]
    print a, b, a + b
\$\endgroup\$
  • \$\begingroup\$ Fantastic. The README file says that test1.txt should have 12 but I find 14. If its changed to -10000 < y < 10000 then I get 12. Do you think this is an error? \$\endgroup\$ – tomwalker Aug 6 '14 at 11:48
  • \$\begingroup\$ I added to the response a few lines to print the sums and checked the output for test1.txt and the 14 sums look good to me, so it might be an error on their side. \$\endgroup\$ – jcollado Aug 6 '14 at 11:56
1
\$\begingroup\$
  • To process large file, open function will load all content of the file into memory. instead, fileinput module only load content line by line.

fileinput:

import fileinput
for line in fileinput.input(['myfile']):
    do_something(line)
fileinput.close()
  • You may want to sort unique numbers yourself, and then only get part combinations. for example, for a large integer like 1658530724461, you can start from negative integers and stop when the a+b>1000 (work from two ends of sorted line to middle)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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