Created
April 3, 2013 08:00
-
-
Save yasyf/5299301 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python | |
""" | |
Yasyf Mohamedali (http://www.yasyf.com) | |
First published at https://gist.github.com/yasyf/5299301 | |
A quick python script to solve the math riddle involving an insurance broker and a woman's daughters. | |
This script will take a variable amount of daughters, whose ages multiply to any number, and present you with all possible solutions, if any. | |
Quickstart: | |
To run, save the script, make sure you have python installed, and simply run the following from the command line: | |
python 'Mr. Warner.py' | |
""" | |
import math, itertools, collections | |
def get_int(prompt): | |
print prompt | |
return input("> ") | |
def find_factors(n): | |
sqrt = math.sqrt(n) | |
i = 1 | |
factors = [] | |
while i <= sqrt: | |
if n % i == 0: | |
factors.append(i) | |
if i != sqrt: | |
factors.append(n/i) | |
i += 1 | |
return sorted(factors) | |
def product_combination(combination): | |
product = 1 | |
for i in range(0,len(combination)): | |
product *= combination[i] | |
return product | |
def sum_combination(combination): | |
sum = 0 | |
for i in range(0,len(combination)): | |
sum += combination[i] | |
return sum | |
def possible_combinations(n,product,factors): | |
return [x for x in itertools.combinations_with_replacement(factors, n) if product_combination(x) == product] | |
def combinations_with_repeated_sums(combinations): | |
sums = dict(zip([x for x in combinations],[sum_combination(x) for x in combinations])) | |
repeated_sums = [x for x,y in collections.Counter(sums.values()).items() if y > 1] | |
return [x for x in sums.keys() if sums[x] in repeated_sums] | |
def filter_single_oldest(combinations): | |
return [x for x in combinations if x[-1] != x[-2]] | |
def format_children(combination): | |
response = "The ages of the %s children are " % len(combination) | |
for x in combination: | |
if x == 1: | |
addition = "1 year old" | |
else: | |
addition = "%s years old" % x | |
if x == combination[len(combination)-1]: | |
response += "and %s." % addition | |
else: | |
response += "%s, " % addition | |
return response | |
def print_answers(combinations): | |
if len(combinations) == 0: | |
print "There is no solution to this question." | |
elif len(combinations) == 1: | |
print format_children(combinations[0]) | |
else: | |
print "There are %s possible answers:" % len(combinations) | |
for x in combinations: | |
print format_children(x) | |
def run(number_children=None,age_product=None): | |
if number_children is None: | |
number_children = get_int("How Many Children?") | |
if age_product is None: | |
age_product = get_int("What Is The Product Of Their Ages?") | |
#each age must be a factor of (the product of the ages) | |
#find all the factors of (the product of the ages) | |
factors = find_factors(age_product) | |
#find every possible combination of choosing the a certain number of ages (the number of children) from all the factors of (the product of the ages) | |
#for example, if there are three children, find all the possible combinations of choosing three ages from the list of all the factors | |
combinations = possible_combinations(number_children,age_product,factors) | |
#since the man didn't have enough information after the first clue, there must be multiple combinations that add up to the same number (the house next door) | |
#for each combination, sum up the ages, and find the combinations that correspond with sums that are repeated at least twice | |
repeats = combinations_with_repeated_sums(combinations) | |
#since there is only one eldest child, the two eldest children cannot have the same age | |
#filter out any answers where the two eldest children have the same age | |
valid_answers = filter_single_oldest(repeats) | |
#print the answers, if any | |
print_answers(valid_answers) | |
return len(valid_answers) | |
def find_result(n,strict=True,x=1,y=1): | |
#find numbers that give n results | |
found = False | |
while found is False: | |
if x >= 5: | |
x = 1 | |
y += 1 | |
else: | |
x += 1 | |
print "Testing with %s children whose ages multiply to %s." % (x,y) | |
result = run(x,y) | |
if (result == n) or (result > n and strict is False): | |
print "There are %s solutions with %s children whose ages multiply to %s." % (result,x,y) | |
found = True | |
def main(): | |
run() | |
#find_result(3) | |
if __name__ == '__main__': | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Related Blog Post: A Welcome Back Challenge