#!/usr/bin/python

import operator
import time
from math import ceil,fabs

def combinations(size, values):
  if size == 1:
    return [[i] for i in values]
  
  half = combinations(size - 1, values)
  result = []
  for value in values:
    for row in half:
      result.append([value] + row)
  return result

def expressions():
  # There are two versions of each term and operation - the pretty version,
  # to be shown to the user, and the version to be evaluated by Python

  all_terms = [
    ('4', 4.0),
    ('sqrt(4)', 2.0),
    ('4!', 24.0),
    ('.4', 0.4),
    ('.4bar', 4.0 / 9.0),
    ('sqrt(.4bar)', 2.0 / 3.0)
  ]

  all_operators = [
    ('+', '+'),
    ('-', '-'),
    ('*', '*'),
    ('/', '/'),
    ('^', '**')
  ]

  expression_combos = [
    '(%s %s %s) %s (%s %s %s)',  # ( A x B ) x ( C x D )
    '( (%s %s %s) %s %s) %s %s', # ( ( A x B ) x C ) x D
    '%s %s (%s %s %s) %s %s',    # A x ( B x C ) x D
    '%s %s (%s %s (%s %s %s))'   # A x ( B x ( C x D ) )
  ]

  for association in expression_combos:

    # Four slots for values
    for terms in combinations(4, all_terms):

      # Three slots for operators
      for operations in combinations(3, all_operators):

        # To be shown to the user
        values = (
          terms[0][0],
          operations[0][0],
          terms[1][0],
          operations[1][0],
          terms[2][0],
          operations[2][0],
          terms[3][0]
        )

        # To be executed by Python
        py_values = (
          terms[0][1],
          operations[0][1],
          terms[1][1],
          operations[1][1],
          terms[2][1],
          operations[2][1],
          terms[3][1]
        )

        yield (association % values, association % py_values)

def main():
  results = [None for i in range (0, 101)]

  start_time = time.time()
  iterations = 0

  for expression, py_expression in expressions():
    iterations = iterations + 1
    try:
      result = eval(py_expression)

      # Check that the result is in the correct range
      if result > 0 and result <= 100:
        int_result = int(ceil(result))

        # Check that the result is an integer
        if fabs(int_result - result) < 0.0000001:

          # Check this value has not already been found
          if results[int_result] == None:
            results[int_result] = expression

    except ZeroDivisionError:
      pass

    # Numerical result out of range
    except OverflowError:
      pass

    # negative number cannot be raised to a fractional power
    except ValueError:
      pass

  for ii, expression in enumerate(results):
    if ii > 0:
      print ii,'=',expression

  print "Done. (%d loop iterations)" % iterations
  print "Elapsed time: ", (time.time() - start_time), " seconds"


if __name__ == "__main__":
    main()