Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import time
- from collections import Counter
- from pprint import pprint
- def all_sums(values, threshold, previous_sums=None):
- """
- values must be sorted
- previous_sums is a Counter of previously obtained possible sums
- Returns a Counter of all possible sums of values and the previous sums
- """
- if not previous_sums:
- previous_sums = Counter({0: 1})
- new = Counter()
- for existing_sum, ex_sum_count in sorted(previous_sums.items()):
- for index, val in enumerate(values):
- total = existing_sum + val
- if total < threshold:
- # With the current value, we have found ex_sum_count
- # ways to obtain that total
- new.update({total: ex_sum_count})
- else:
- # We don't need the exact sum, as anything we could
- # later add to it will be over the threshold.
- # We count them under the value = threshold
- # As 'values' is sorted, all subsequent values will also give
- # a sum over the threshold
- values_left = len(values) - index
- new.update({threshold: values_left * ex_sum_count})
- break
- return new
- def count_sums(values, threshold, repeat):
- """
- values must be sorted!
- Recursively calculates the possible sums of 'repeat' values,
- counting together all values over 'threshold'
- """
- if repeat == 1:
- return all_sums(values, threshold, previous_sums=None)
- else:
- return all_sums(values, threshold, previous_sums=count_sums(values, threshold, repeat=repeat - 1))
- if __name__ == '__main__':
- start_time = time.time()
- confs = range(10, 11)
- for i in confs:
- loops = i
- results = [4, 2.75, 2.75, 2.75, 2.75, 1.5, 1.5, 1.5, 1.5, 1.5, 1.5, 0.25, 0.25, 0.25, 0.25, 0]
- threshold = loops * 2
- values = sorted(results)
- sums = count_sums(values, threshold, repeat=loops)
- number_of_sums = len(results) ** loops
- good = sums[threshold]
- bad = number_of_sums - good
- print("Questions: {0}, Result: {1:.6f}%, time elapsed: {2:.2f}s".format(i, 100 * good / (good + bad),
- time.time() - start_time))
- pprint(sums)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement