'''
March 2017 Math Puzzler

http://web.monroecc.edu/MathPuzzler/March17puzzle

Place the numbers 1 - 12 in the circles below, so that
the sum of the four numbers along each of the six
straight lines is the same.

        0
        
11   8     1    9

   7         2
   
6    5     4    3

        10

The "circles" are denoted by the numbers above (0->11).  The
star points are locations (0, 9, 3, 10, 6, 11).  The cross
locations are (1, 2, 4, 5, 7, 8).
'''

from __future__ import print_function   #so this will work with Py 2.7
import itertools as it
import time

solutions = []          #A list of solution tuples
solutionHashes = []     #A list of solution hashes
numSolutions = 0        #Total number of solutions
                        # (including rotations/reflections)
uniqueSolutions = 0     #Number of unique solution
                        # (excluding rotations/reflections)
                        

def point(value):
  '''
    Convert a star POINT number to an uppercase letter for
    the hash: 0 -> 'A', 1 -> 'B', ...
    Returns the letter
  '''
  return chr(value + ord('A'))


def cross(value):
  '''
    Convert a star CROSS (intersection) point number 
    to a lowercase letter for the hash: 0 -> 'a', 1 -> 'b', ...
    Returns the letter
  '''
  return chr(value + ord('a'))


def isSolution(b):
  '''
    Test for the sum of all the 4 numbers in each of the 6 star
    lines add to the same number.  Return True if it is a
    solution, otherwise False
  '''
  return \
    b[0] + b[1] + b[2] + b[3] == b[3] + b[4] + b[5] + b[6] ==\
    b[6] + b[7] + b[8] + b[0] == b[9] + b[2] + b[4] + b[10] ==\
    b[10] + b[5] + b[7] + b[11] == b[11] + b[8] + b[1] + b[9]


def makeHash(b):
  '''
    The hash is a string of upper and lowercase letters that
    represent a possible solution (b).  Upper case letters denote
    star point values, lower case letters denote intersection
    point values.  The hash starts at the top point and goes
    around the periphery of the star clockwise from point to
    intersection to point....
    
    Returns a tuple of a hash of this star and this star's
    reflection.
  '''
  #This star's hash:
  aHash =\
    point(b[0]) + cross(b[1]) + point(b[9]) + cross(b[2]) + \
    point(b[3]) + cross(b[4]) + point(b[10]) + cross(b[5]) + \
    point(b[6]) + cross(b[7]) + point(b[11]) + cross(b[8])

  #The hash of this star's reflection:               
  refHash =\
    point(b[0]) + cross(b[8]) + point(b[11]) + cross(b[7]) + \
    point(b[6]) + cross(b[5]) + point(b[10]) +  cross(b[4]) + \
    point(b[3]) + cross(b[2]) + point(b[9]) + cross(b[1])

  return (aHash, refHash)


def isIncluded(soln, hashes):
  '''
    Create a hash of the proposed solution and its reflection.
    See if either is already included as a solution.  Since the
    solution hashes have point sequence included twice,
    rotations will also be excluded.

    Return True if found, False if not found.
  '''
  (aHash, refHash) = makeHash(soln)

  found = False
  for eachHash in hashes:                         #For each hash in the already found solutions
    if aHash in eachHash or refHash in eachHash:  # see if this proposed solution, its rotation,
                                                  # or reflection is already there
      found = True
      break
  return found


  
if __name__ == '__main__':

  print('Star point locations:')       
  print('        a')
  print()       
  print('l    i     b    j')
  print()
  print('   h         c')
  print()   
  print('g    f     e    d')
  print()
  print('         k')

  print('Please be patient, it takes several minutes to test')
  print('all the possibilities.')
  print()
  print('The solution tuples have the following format:')
  print('(a, b, c, d, e, f, g, h, i, j, k, l)')
  print('\nWhat I have found so far:')
  
  start = time.time()

  #Create an iterator of all the possible ways the 12
  # numbers can be positioned on the star
  possibilities = it.permutations((1,2,3,4,5,6,7,8,9,10,11,12))

  #Now, test them all
  for soln in possibilities:
    if isSolution(soln):                          #Test to see if this possibility
                                                  # satisfies the requirements
      numSolutions += 1                           # If so, count it

      #Now test if this solution is just a reflection or rotation of one we have
      # already found
      if not isIncluded(soln, solutionHashes):    #If not already included
        solutions.append(soln)                    # then include the solution
        aHash = makeHash(soln)[0]                 #Create its hash
        aHash += aHash                            #Dup it for wrap around (for rotation test)
        solutionHashes.append(aHash)              #Add to the list of solution hashes
        uniqueSolutions += 1                      #Count as an "unique solution"
        print(soln)


  print()
  print("The time spent solving: ", end='')
  print(time.time() - start, end='')
  print(" seconds.")
  print()
  print("The total number of solutions (not excluding rotations/reflections): ", end='')
  print(numSolutions)
  print("The number of unique soltuions (excluding rotations/reflections): ", end='')
  print(uniqueSolutions)