'''
April 2016 Puzzle
Dave Vogel - dvogel003@monroecc.edu
4/7/16
Tim is a mathematician with two rather intelligent children,
Matthew and Kristen. One day, he offers them the following challenge.
He tells them that he has a triangle whose side lengths are all
integers. He tells only Matthew that the perimeter is 11 and
tells only Kristen the area. Each is asked to independently
determine the three side lengths of the triangle and each is
intelligent enough to do so if they are given sufficient
information.
After a few minutes Tim asks each of the children if they
have come up with the answer and each indicates that it is
impossible to determine with certainty. At that point,
Matthew thinks for a moment and with no further information
says that he now knows the answer with certainty. At that point,
Kristen then thinks for a moment and indicates that she now
knows with certainty.
What were the lengths of the three sides of the triangle?
*You must show sufficient work to support your answer
'''
from __future__ import print_function
import itertools as it
class Triangle:
'''
Create a triangle with sides of integral length x, y, z. The values of
x, y, and z must be set appropriately to make a triangle (must pass
function isTriangle below). The area and perimeter is also calculated.
'''
def __init__(self, x, y, z):
self.x = x #Triangle sides
self.y = y #
self.z = z #
self.area = self.calcArea() #Area of triangle
self.perimeter = x + y + z #Perimeter of triangle
def calcArea(self):
'''
Calculate the area of a triangle from the sides
'''
s = 0.5*(self.x + self.y + self.z)
return (s * (s-self.x) * (s-self.y) * (s-self.z))**0.5
def __repr__(self):
'''
Provide a readable representation of a Triangle
'''
return "Triangle(side lengths = %i, %i, %i;\t perimeter=%i, area=%f)" % \
(self.x, self.y, self.z, self.perimeter, self.area)
def __hash__(self):
'''
Generate some kind of hash, needed for the generating sets of
Triangles (so 'equal' Triangles don't have separate entries in
the set)
'''
return hash(self.area*self.perimeter)
def __eq__(self, other):
'''
Equal Triangles are Triangles with same side lengths (order doesn't
matter). Triangle(2,3,4) is 'equal' to Triangle(4,3,2).
'''
selfSides = set([self.x, self.y, self.z])
otherSides = set([other.x, other.y, other.z])
if isinstance(other, Triangle):
return selfSides == otherSides
else:
return False
#end class Triangle
def isTriangle(m, n, o):
'''
Confirm the side lengths can make a triangle. Make sure each side is
shorter than the sum of the other 2 sides.
'''
return (o < n + m) and (n < o + m) and (m < n + o)
#####Main
if __name__ == '__main__':
#print("April 2016 Puzzler of the Month")
#print(" Dave Vogel - dvogel003@monroecc.edu\n\n")
#Make all possible combinations of 3 integers from 1->10
possibleTriangles = it.combinations_with_replacement(range(1,11),3)
#Create triangles from the above list
triangles = []
for n in possibleTriangles:
if isTriangle(n[0], n[1], n[2]): #Insure a valid triangle
newTriangle = Triangle(n[0], n[1], n[2]) #Create it
# print(newTriangle)
triangles.append(newTriangle) #Add to the list
#Create a set of Triangles whose areas match other triangles
sameArea = set()
sortedTriangles = sorted(triangles, key=lambda triangle:triangle.area)
for n in range(len(sortedTriangles)-1):
if sortedTriangles[n].area == sortedTriangles[n+1].area:
sameArea.add(sortedTriangles[n])
sameArea.add(sortedTriangles[n+1])
#Print them in order by area
print('Set of all triangles whose sides are integer values and\n' +\
'(arbitrarily) less than 11 and whose areas match another triangle.')
print('Sorted by area')
for n in sorted(sameArea, key=lambda triangle:triangle.area):
print(n)
## #Print them in order by perimeter
## print('\n\nDitto \nsorted by perimeter')
## for n in sorted(sameArea, key=lambda triangle:triangle.perimeter):
## print(n)
#Find Triangles from the sameArea set whose perimeters are 11
answer = []
for n in sameArea:
if n.perimeter == 11:
answer.append(n)
if len(answer) != 1:
raise ValueError('Number of solutions not equal to one!')
#Find Triangles from the sameArea set whose area = the area of the
#above
otherAnswer = []
for n in sameArea:
if n.area == answer[0].area and not n.__eq__(answer[0]):
otherAnswer.append(n)
if len(otherAnswer) != 1:
raise ValueError('Number of extra triangles with the area is not equal to one!')
text = """
Since Matthew knows that the perimeter = 11 and that Kristen
is unable to solve it initially, the solution must be in the set of
triangles (above) that have an area equivalent to another triangle.
The only integral triangle that has an area in common with another
and a perimeter of 11 is:\n
"""
print(text + str(answer[0]))
text = """
Hence, this is the solution. Since Kristen knows the area,
she initially knows the solution must be either:\n
"""
print(text + str(answer[0]) + " or\n " + str(otherAnswer[0]))
text = """
Once Matthew declares he knows the answer after learning that
Kristen also couldn't initially determine it, Kristen can now deduce
the solution because, of her 2 choices with the given area, perimeters
of 11 and 15 in the above set, there is a single triangle with a
perimeter of 11 but 2 with a 15 perimeter. She realizes that if the
perimeter was 15 Matthew couldn't declare he knew the answer. Hence
now she is also sure of the solutions.\n
"""
print(text)