'''
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)