'''
  October 2015 Math Puzzle

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

  Your job is to create the following integers: 47, 48, 49, 53, 64, 65, 66,
  67, 68, 90, 91, 92, 93, 94, and 95

  You may use any number of parentheses to control the order of operations
  and each of the five numbers (1 - 5) must be used exactly once in creating
  each number above.

  For example: 30 = (5 - 3)*(4^2 - 1)

  Note:  Modified to find formulas for all numbers 0 -> 99
'''
from __future__ import print_function
from __future__ import division           #To force float division
import itertools as i
import sets

allowedOps = ("+","-","*","/","**")
allowedDigits = ("1","2","3","4","5")
answers = [47, 48, 49, 53, 64, 65, 66, 67, 68, \
           90, 91, 92, 93, 94, 95]
##answers = range(500)
otherAnswers = sets.Set()
solutions = {}                            #The first occurrence of each solution

o = i.product(allowedOps, repeat=4)       #Operations can be reused


def doeval(s):
  '''
  Evaluate s.  If the result is included in the answer list, save
  the result and remove that answer from the answer list.
  '''
  try:
    ans = eval(s)
    if ans in answers:
      solutions[ans] = s                  #Save the solution to print later
      answers.remove(ans)                 #A solution found, don't look for a another
  except:                                 #Filter out anything that isn't a valid expression
    pass
    #print "ERROR:", n, m, s


def findExp(s):
  '''
  Return True if s contains an element of "**"
  '''
  return s == "**"


#####################3
#Main
if __name__ == '__main__':
  signal = ['-', '+']
  for n in range(5**4):                     #5^4 = 625 possibilities of operations
    if answers == []:                       #Quit if found them all
      break
    if n%20 == 0:
      print()
    print('.', end='')                      #Show we are doing something
    ops = o.next()                          #Next set of operators
    if len(filter(findExp, ops)) > 1:       #Don't calc if multiple exponetiation
      continue                              # (numbers get way too big!  Bogs down python)
    d = i.permutations(allowedDigits, 5)    #All 5 digits much be used
    
    for m in range(5*4*3*2):                #5! = 325 possibilities with the digits
      digs = d.next()
      
      lp = "("                              #Do evaluations with and without
      rp = ")"                              # one set of parentheses
      s = digs[0] + ops[0] + digs[1] + \
          ops[1] + digs[2] + ops[2]  + \
          digs[3] + ops[3] + digs[4]
      doeval(s)
      
      s = lp + digs[0] + ops[0] + digs[1] + rp + \
      ops[1] + digs[2] + ops[2]  + \
      digs[3] + ops[3] + digs[4]    
      doeval(s)

      s = lp + digs[0] + ops[0] + digs[1] + \
          ops[1] + digs[2] + rp + ops[2]  + \
          digs[3] + ops[3] + digs[4]    
      doeval(s)

      s = lp + digs[0] + ops[0] + digs[1] + \
          ops[1] + digs[2] + ops[2]  + \
          digs[3] + rp + ops[3] + digs[4]    
      doeval(s)

      s = digs[0] + ops[0] + lp + digs[1] + \
          ops[1] + digs[2]+ rp + ops[2]  + \
          digs[3] + ops[3] + digs[4]    
      doeval(s)

      s = digs[0] + ops[0]+ lp + digs[1] + \
          ops[1] + digs[2] + ops[2]  + \
          digs[3]+ rp + ops[3] + digs[4]    
      doeval(s)

      s = digs[0] + ops[0] + lp + digs[1] + \
          ops[1] + digs[2] + ops[2]  + \
          digs[3] + ops[3] + digs[4] + rp 
      doeval(s)

      s = digs[0] + ops[0] + digs[1] + \
          ops[1] + lp + digs[2] + ops[2]  + \
          digs[3] + rp + ops[3] + digs[4]    
      doeval(s)

      s = digs[0] + ops[0] + digs[1] + \
          ops[1] + lp + digs[2] + ops[2]  + \
          digs[3] + ops[3] + digs[4] + rp    
      doeval(s)

      s = digs[0] + ops[0] + digs[1] + \
          ops[1] + digs[2] + ops[2]  + \
          lp + digs[3] + ops[3] + digs[4] + rp   
      doeval(s)


  ordered = sorted(solutions)
  print()
  print()
  m=1
  for n in ordered:
    print(str(m) + ")", n, "=", solutions[n])
    m+=1