Skip to content

Instantly share code, notes, and snippets.

@altaurog
Last active August 29, 2015 14:27
Show Gist options
  • Save altaurog/d0ac37f80aff1f37c290 to your computer and use it in GitHub Desktop.
Save altaurog/d0ac37f80aff1f37c290 to your computer and use it in GitHub Desktop.
Find set S of 7 numbers such that the set of all sums s1, s1 + s2, s1 + s2 + s3 for s1, s2, and s3 in S contains the set of positive integers [1, 70]
import multiprocessing
import sys
def rsetgen(count, floor, ceiling):
"""
Recursively generate all possible sets of
count unique numbers between floor and ceiling
"""
if 1 == count:
for i in xrange(floor, ceiling):
yield [i]
else:
for i in xrange(floor, ceiling):
for s in rsetgen(count - 1, i + 1, ceiling):
yield [i] + s
def pick(count, numbers):
"""
Recursively generate all possible combinations
of count items selected from the set numbers
"""
if 1 == count:
for i in numbers:
yield [i]
else:
for i in numbers:
for s in pick(count - 1, numbers):
yield [i] + s
def worker(top, in_queue, out_queue):
"""
Get sets of numbers on in_queue, test them
for coverage in the target range and put the
set with the missing count onto out_queue
"""
target = set(range(1, top + 1))
while True:
numberset = in_queue.get()
if numberset is None:
out_queue.put(None)
break
result = set()
for taken in pick(3, numberset):
result.add(sum(taken))
missing = len(target - result)
out_queue.put((missing, numberset))
def driver(top, in_queue, worker_count):
"""
Put sets for testing (generated by rsetgen) onto in_queue
A quit signal (None) is put on the queue for each worker
"""
for i in range(2, 5):
for s in rsetgen(5, i + 1, top - 1):
in_queue.put([0, 1, i] + s)
for i in range(worker_count):
in_queue.put(None)
def main(top, worker_count):
# set up the queues
in_queue = multiprocessing.Queue(worker_count * 4)
out_queue = multiprocessing.Queue()
# start the worker processes to test sets
print("running on %d workers" % worker_count)
for i in range(worker_count):
p = multiprocessing.Process(target=worker, args=(top, in_queue, out_queue))
p.daemon = True
p.start()
# start the driver process to generate sets as input to workers
p = multiprocessing.Process(target=driver, args=(top, in_queue, worker_count))
p.daemon = True
p.start()
# now process items from worker processes on out_queue
done = 0
missing = top
soln = None
while done < worker_count:
result = out_queue.get()
if result is None:
done += 1
else:
m, numberset = result
if 0 == m:
return result
if m < missing:
soln = numberset
return missing, soln
if __name__ == '__main__':
worker_count = multiprocessing.cpu_count() - 2
result = main(int(sys.argv[1]), worker_count)
print repr(result)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment