Created
February 5, 2018 08:07
-
-
Save alexreinking/94dc9e92ad4daac28249f99b30389878 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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