'''
  October 2016 Puzzle

You are equipped with a single 1, 3, 4, and 6 along with the ability to
combine them using only addition, subtraction, multiplication, and division.

Your goal is to create each of the integers from 16 to 25.

You may use any number of parentheses to control the order of operations
and in each case, you must use all four numbers exactly once.  Additionally,
you are not allowed to multiply or divide by the number 1 (i.e. 1 must
be added or subtracted).

For example:  10 = 6 / 3 * (4 + 1)
'''
from __future__ import print_function
from __future__ import division           #To force float division for Py2.x
import sys
import itertools as i

    
def doeval(s):
  '''
  Evaluate the equation in string s.  If the result is included in the
  answer list, save the result and remove that answer from the answer
  set.  The rules say that you can't multiply or divide by 1 so those
  equations are not evaluated
  '''
  try:
    #For this problem 1 can not be multiplied or divided
    # ignore equations that contain that
    if "/1" in s or "*1" in s or "1/" in s or "1*" in s:
      return
    
    else:
      ans = eval(s)

      #Test to see if the result is very close to an integer so that
      # minor roundoff error doesn't allow us to miss a solution
      roundAns = int(.00001 + ans)          #Add a little to the answer
      if abs(roundAns - ans) < .0001:       # if the int value is close
        ans = roundAns                      # the original, then probably
                                            # just roundoff error
        
      if ans in answers:                    #If it is one of the numbers
                                            # we're looking for?
        solutions[ans] = s                  # save the solution to print later
        answers.remove(ans)                 #Remove the found answer
        
  except ZeroDivisionError:                 #Filter out invalid expressions
    pass
  
  except Exception as e:                    #Display other errors 
    print ("ERROR: " + str(e) + '\n' + s)   # (shouldn't be any)
    print (e)




#####################
#Main
#####################

if __name__ == '__main__':    

  allowedOps = ("+", "-", "*", "/")
  allowedDigits = ("1", "3", "4", "6")

  #Possible arrangements of the parentheses in the equations
  parenCase = []
  parenCase.append(("", "", "", "", "", ""))      #a*b*c*d
  parenCase.append(("(", "", ")", "", "", ""))    #(a*b)*c*d
  parenCase.append(("(", "", "", "", ")", ""))    #(a*b*c)*d
  parenCase.append(("", "(", "", "", ")", ""))    #a*(b*c)*d
  parenCase.append(("", "(", "", "", "", ")"))    #a*(b*c*d)
  parenCase.append(("", "", "", "(", "", ")"))    #a*b*(c*d)
  parenCase.append(("(", "(", "", "", "))", ""))  #(a*(b*c))*d
  parenCase.append(("", "(", "", "(", "", "))"))  #a*(b*(c*d))
  parenCase.append(("((", "", ")", "", ")", ""))  #((a*b)*c)*d
  parenCase.append(("", "((", "", "", ")", ")"))  #a*((b*c)*d)

  #Answers
  answers = list(range(16, 26)) #List of numbers for which to find equations
  solutions = {}                #Set of the first occurrence of each solution

  tries = 0                     #Number of equations evaluated while
                                # looking for the solutions
  try:
    
    #Possible number positions
    digitOrder = i.permutations(allowedDigits, 4) #All 4 digits much be used
    
    for d in digitOrder:                          #Check all digit positions
      
      #Possible operators
      opOrder = i.product(allowedOps, repeat=3)   #Operators can be reused
      
      for o in opOrder:                           #Check all operators
        for p in parenCase:                       #Check all parentheses positions

          #Create the equation as a string
          s = p[0] + d[0] + o[0] + p[1] +\
              d[1] + p[2] + o[1] + p[3] +\
              d[2] + p[4] + o[2] +\
              d[3] + p[5]
          
          doeval(s)                               #Evaluate the equation
          tries += 1
          
          if answers == []:                       #See if all have been found
            raise StopIteration                   # if so, this does a 'break'
                                                  # from nested loops
          
  except StopIteration:
    print ("Solved after " + str(tries) + " tries.")

  #Print the results in order
  ordered = sorted(solutions)               #Makes a list of the sorted keys
  print('\n')
  for n in ordered:
    print (str(n) + "=" + solutions[n])