24game.py

import random

def evaluate(expr):
  stack = []
  for el in expr:
    if isinstance(el, (int, long)):
      stack.append(el)
    elif el == '+':
      y, x = stack.pop(), stack.pop()
      stack.append(x + y)
    elif el == '-':
      y, x = stack.pop(), stack.pop()
      stack.append(x - y)
    elif el == '*':
      y, x = stack.pop(), stack.pop()
      stack.append(x * y)
    elif el == '/':
      y, x = stack.pop(), stack.pop()
      if y == 0:
        return float('inf')
      stack.append(1.*x / y)
  assert len(stack) == 1
  return stack[0]

def enumOps(nums, i, curExpr, stack_size):
  if stack_size == 1 and i >= len(nums):
    yield curExpr
    return
  
  if stack_size <= 1:
    if i < len(nums):
      for x in enumOps(nums, i + 1, curExpr + [nums[i]], stack_size + 1):
        yield x
  else:
    for op in ['+', '-', '*', '/']:
      for x in enumOps(nums, i, curExpr + [op], stack_size - 1):
        yield x
    if i < len(nums):
      for x in enumOps(nums, i + 1, curExpr + [nums[i]], stack_size + 1):
        yield x
    
def test(nums):
  good = []
  for expr in enumOps(nums, 0, [], 0):
    val = evaluate(expr)
    if val == 24:
      good.append(expr)
  return good
    
def to_tree(expr):
  stack = []
  for el in expr:
    if isinstance(el, (int, long)):
      stack.append(el)
    elif el == '+':
      x, y = stack.pop(), stack.pop()
      stack.append([y, x, '+', 1])
    elif el == '-':
      x, y = stack.pop(), stack.pop()
      stack.append([y, x, '-', 1])
    elif el == '*':
      x, y = stack.pop(), stack.pop()
      stack.append([y, x, '*', 2])
    elif el == '/':
      x, y = stack.pop(), stack.pop()
      stack.append([y, x, '/', 2])
  assert len(stack) == 1
  return stack[0]
  
def needLparen(expr):
  left, _, _, prec = tuple(expr)
  if isinstance(left, list):
    lPrec = left[3]
    return lPrec < prec
  return False
  
def needRparen(expr):
  _, right, op, prec = tuple(expr)
  if not isinstance(right, list):
    return False
  rPrec = right[3]
  if op in {'+', '*'}:
    return rPrec < prec
  return rPrec <= prec
  
def to_infix_tree(tree):
  if not isinstance(tree, list):
    return str(tree)
  
  left, right, op, _ = tuple(tree)
  left = to_infix_tree(left)
  right = to_infix_tree(right)
  
  if needLparen(tree):
    left = '(' + left + ')'
    
  if needRparen(tree):
    right = '(' + right + ')'
    
  return "{} {} {}".format(left, op, right)
  
def to_infix(expr):
  return to_infix_tree(to_tree(expr))
    
while True:
  nums = [random.randint(2,10) for i in range(4)]
  if len(set(nums)) != len(nums):
    continue
  
  twentyFours = test(nums)
  twentyFours = set(to_infix(x) for x in twentyFours)
  
  if len(twentyFours) >= 10:
    print nums
    for witness in twentyFours:
      print witness
    break