Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment