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 + integers[-1]) < -10000: integers = integers[1:] while (integers + integers[-1]) > 10000: integers = integers[:-1]
This did not make much of a difference