xs = list(combinations([i for i in range(1, 10)], 4)) # list of all possible combinations of 4 nums in [1..9]
sums = [sum(i) for i in xs] #list of the sum of each tuple in xs
candidate_sums = {i for i in sums if sums.count(i) >= 3} #set of sums that appear atleast 3 times: potential solutions

dct = {} #empty dict to hold solution
for i in candidate_sums:
    test_space = [set(j) for j in xs if sum(j) == i] # list of sets in xs which sum up to i
    triplets = combinations(test_space, 3) #every combination of 3 sides from test_space note this is a generator
    for triple in triplets:
        if not set.intersection(triple[0], triple[1], triple[2]): #lines 11 - 14: test the set conditions
            if 1 == len(set.intersection(triple[0], triple[1]))\
                == len(set.intersection(triple[0], triple[2]))\
                == len(set.intersection(triple[1], triple[2])):
                    if str(i) not in dct:
                        dct[str(i)] = [] #initialise list to hold solution in dct
                    dct[str(i)].append(triple) #append solution to dct

for key, value in dct.items():
    print("************************************************************")
    print("* Sum = {}, # Solutions = {}, Solutions:\t\t\t   *".format(key, len(value)))
    print("*----------------------------------------------------------*")
    for i, v in enumerate(value):
        print("* solution {}: {}   *".format(i+1, v))
    print("************************************************************")
    print("\n")

"""
Explanation: Upshot
There are 18 basis solutions to the puzzle. Every other solution is obtained by either:

rearranging non vertex elements on one side of a solution
Rotating a solution
A combination (and or repition) of 1 and 2

Solution walk through:
One side of the triangle has 4 elements, so we can start by generating every possible side of a triangle:
1. Generate a list xs of every combination of 4 numbers between 1 and 9 inclusive. xs = [c1..c126]
* The number of possible sides are:$\binom 9 4 = 126 $

From the original question, every triangle that satisfies the criteria has the property: 
$\sum side_1 = \sum side_2 = \sum side_3$. 
We can exploit this by creating a list containing the sums of the elements of xs and picking only thoes ones that appear at least 3 times:

sums = [sum(c1)..sum(c126)]
candidate sums = ${$sum($c_i$) | sum($c_i$) appears at least 3 times in sums$}$

* There are 15 candidate sums
Another key observation we can make from the puzzle criteria is that each side of the triangle will share
1 unique vertex with with each other side:
Let the sides of the triangle be A B C where A, B, C are sets.
Side A will share a vertex with side B and another with side C.
The element common to side A and side B i.e. $A \cap B$ is not common to C. The same holds for sides A and C
as well as sides B and C. Simply:
condition 1: $$A \cap B \cap C = \emptyset $$
condition 2: $$|A \cap B| = |A \cap C| = |B \cap C| = 1$$
With the information concerning the set properties of the sides of the triangle, for each candidate sum, 
* we pick every set in xs which sums up to candidate sum. This forms our current test space
* generate every combination of 3 sets from test space. $triplets :=$ every combo of 3 sets in test space
* The elements of triplets that satisfy the set conditions are solutions
The solutions are stored in a dictionary (aka hash table, hash map, hash array, e.t.c.) for efficient lookup
Take note of the liberal use of comprehensions, generators and filters: vive la programmation functionnel!
End of explanation
"""


def set_conditions(triple):
    """(tuple of sets) -> bool
    Given a tuple containing 3 sets A, B, C
    Return true if and only if 
        A intersection B intersection C = \emptyset
        and
        len(A intersection  B) = len(A intersection  C) = len(B intersection  C) = 1
    
    The entire function is in the return statement.
    The function is simple enough to understand so I have opted to 
    save computational resources (time and memory)
    time by avoiding the overhead of creating then later accessing variables
    """    
#    cond1 = not set.intersection(triple[0], triple[1], triple[2])
#    cond2 = 1 == len(set.intersection(triple[0], triple[1]))\
#            == len(set.intersection(triple[0], triple[2]))\
#            == len(set.intersection(triple[1], triple[2]))
#    return cond1 and cond2
    return not set.intersection(triple[0], triple[1], triple[2]) and\
            1 == len(set.intersection(triple[0], triple[1]))\
                == len(set.intersection(triple[0], triple[2]))\
                == len(set.intersection(triple[1], triple[2]))

xs = list(combinations([i for i in range(1, 10)], 4))
sums = [sum(i) for i in xs]
candidate_sums = set(filter(lambda x: sums.count(x) > 2, sums))

d2 = {}
for i in candidate_sums:
    test_space = [set(j) for j in xs if sum(j) == i]
    triplets = combinations(test_space, 3)
    sol = list(filter(set_conditions, triplets)) # filter solutions from triplets
    if sol:
        d2[str(i)] = sol #put solution in dict

for key, value in d2.items():
    print("************************************************************")
    print("* Sum = {}, # Solutions = {}, Solutions:\t\t\t   *".format(key, len(value)))
    print("*----------------------------------------------------------*")
    for i, v in enumerate(value):
        print("* solution {}: {}   *".format(i+1, v))
    print("************************************************************")
    print("\n")

"""
Explanation: Same algorithm, written in a more functional style
Here I define a function set_conditions to test the set conditions defined earlier:
condition 1: $$A \cap B \cap C = \emptyset \$$
condition 2: $$|A \cap B| = |A \cap C| = |B \cap C| = 1$$
One can simply filter the triangles under consideration to get those which satisfy the set_conditions.
The end product: a more comprehensible implementation
End of explanation
"""


