Skip to content

Instantly share code, notes, and snippets.

@hackerb9
Created August 30, 2018 11:46
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hackerb9/dfce5c08f358697240c24867491d1776 to your computer and use it in GitHub Desktop.
Save hackerb9/dfce5c08f358697240c24867491d1776 to your computer and use it in GitHub Desktop.
Sum of Factors (brainteaser)
#!/usr/bin/python3
# Sum of Factors. hackerb9 2018.
# This is a generalization of a certain type of numeric logic puzzle
# that gives you a hint by telling you that the previous hints were
# insufficient: that is, you now know that the answer is one that
# could be arrived at two different ways. Here's an example, as told
# by Jim Fixx in the 1970's:
############################################
# #
# A census taker asks a housewife how many #
# people live in her house and what their #
# ages are. The woman tells him that her #
# three daughters live in the house and #
# that the product of their ages is #
# thirty-six, and that the sum of their #
# ages is the number of the house next #
# door. The census taker goes next door #
# and looks at the number of the house. #
# When he returns he tells the woman that #
# the information she gave him is not #
# sufficient, whereupon the woman tells #
# him, "My oldest daughter is sleeping #
# upstairs." The census taker thanks her #
# and promptly figures out the daughters' #
# ages. What are they and how does he #
# know? #
# #
############################################
# If you want to solve the puzzle, don't keep reading.
# This problem is based on the fact that the number 36 has two
# different (non-prime) ways of factoring it that both add up to
# the same thing.
#
# In particular:
# 2 x 2 x 9 == 36 2 + 2 + 9 == 13
# 1 x 6 x 6 == 36 1 + 6 + 6 == 13
# But how common is it for a number to have factors like that? Is 36
# unique? It certainly could be given that I've seen several other
# puzzles and brain teasers that use 36 for that reason. And I can
# tell you I've check and no number under 36 has that property.
# Are there other such numbers that puzzle makers can use? Or are they
# doomed to use 36 as the answer forever more? Run this program and
# find out!
####
# Note: I'm using the GNU factor program because it is robust and
# stable and pre-installed on all the machines I use. There are plenty
# of python factoring implementations, but a surprising number of them
# are buggy or too complicated or both.
####
from pprint import pprint as pp
import os
from functools import reduce
def product(a):
if (a):
return reduce( (lambda x, y: x * y) , a)
else:
return 0
def printproductandsum(z):
'''
Given a set containing tuples of numbers, such as:
{(3, 3, 10), (2, 5, 9), (3, 5, 6), (2, 3, 15)}
print out what's going on in human readable format.
For example,
3x3x10=90 3+3+10=16
2x5x9=90 2+5+9=16
3x5x6=90 3+5+6=14
2x3x15=90 2+3+15=20
'''
if (len(z) == 1):
return
seen = set()
for partition in z:
print (*partition, sep=' x ', end='')
print (" = ", end='')
print (product(partition), end='')
print ("\t\t", end='')
print (*partition, sep=' + ', end='')
print (" = ", end='')
s=sum(partition)
print (s, end='')
if (s in seen):
print("\t\t*** we have a match! ***", end='')
print ("")
seen.add(s)
print ("")
def __main__():
for i in range(4,100):
x=os.popen("factor %d" % i).read().split()[1:]
x=[int(c) for c in x]
# print("")
# print(i)
# pp(x)
y3=sorted_k_partitions(x, 3) # k == 3 partitions
y2=sorted_k_partitions(x, 2)
y1=sorted_k_partitions(x, 1)
y2=[ x+[(1,)] for x in y2 ] # Can always multiply by 1
y1=[ x+[(1,),(1,)] for x in y1 ] # Even twice!
y=y1+y2+y3
# Oops, our routine returns results with too few partitions.
y = filter( lambda x: len(x)==3, y)
# print("number of partitions: %d" % len(y))
# pp(list(y))
# print("subproducts of factors")
z = [ [ product(f) for f in grouping ] for grouping in y ]
z = set([tuple(x) for x in z])
printproductandsum(z)
######################################################################
# [ This routine taken verbatim from
# https://stackoverflow.com/questions/39192777/ ]
def sorted_k_partitions(seq, k):
"""Returns a list of all unique k-partitions of `seq`.
Each partition is a list of parts, and each part is a tuple.
The parts in each individual partition will be sorted in shortlex
order (i.e., by length first, then lexicographically).
The overall list of partitions will then be sorted by the length
of their first part, the length of their second part, ...,
the length of their last part, and then lexicographically.
"""
n = len(seq)
groups = [] # a list of lists, currently empty
def generate_partitions(i):
if i >= n:
yield list(map(tuple, groups))
else:
if n - i > k - len(groups):
for group in groups:
group.append(seq[i])
yield from generate_partitions(i + 1)
group.pop()
if len(groups) < k:
groups.append([seq[i]])
yield from generate_partitions(i + 1)
groups.pop()
# result = generate_partitions(0)
# uniquify. (Python sets can hash tuples, but not lists.)
result = set([tuple(x) for x in generate_partitions(0)])
# Sort the parts in each partition in shortlex order
result = [sorted(ps, key = lambda p: (len(p), p)) for ps in result]
# Sort partitions by the length of each part, then lexicographically.
result = sorted(result, key = lambda ps: (*map(len, ps), ps))
return result
__main__()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment