Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import math
- import itertools
- unary_operators = []
- binary_operators = []
- NUMBER = 0
- def iter_rpn(ops, values, value_literal):
- """iterate through all rpn expressions ith `ops` operators and `values` values, all of which are `value_literal`"""
- if ops == 0:
- if values == 1:
- yield (str(value_literal),)
- return
- if values >= 1:
- for operator in unary_operators:
- for expr in iter_rpn(ops-1, values, value_literal):
- yield expr + (operator,)
- if values >= 2:
- for operator in binary_operators:
- for l_ops in range(ops):
- r_ops = ops - l_ops - 1
- for l_values in range(1, values):
- r_values = values - l_values
- for l_expr in iter_rpn(l_ops, l_values, value_literal):
- for r_expr in iter_rpn(r_ops, r_values, value_literal):
- yield l_expr + r_expr + (operator,)
- cache = {} #structured like {args: {evaluated_result: expr}
- def memoize_rpn_generator(f):
- def gen(*args):
- if args not in cache:
- cache[args] = {}
- for expr in f(*args):
- result = eval_rpn(expr)
- if not isinstance(result, int): continue
- cache[args][result] = expr
- return list(cache[args].values())
- return gen
- iter_rpn = memoize_rpn_generator(iter_rpn)
- rpn_callbacks = {}
- def handles(name, num_args):
- [unary_operators, binary_operators][num_args-1].append(name)
- def _handles(f):
- rpn_callbacks[name] = (f, num_args)
- return f
- return _handles
- @handles("square", 1)
- def square(x):
- return x**2
- @handles("sqrt", 1)
- def sqrt(x):
- if x < 0:
- return float("nan")
- result = math.sqrt(x)
- if not result.is_integer():
- return float("nan")
- else:
- return int(result)
- @handles("add", 2)
- def add(a,b):
- return a+b
- @handles("sub", 2)
- def sub(a,b):
- return a-b
- @handles("mul", 2)
- def mul(a,b):
- return a*b
- @handles("fact", 1)
- def factorial(x):
- if not isinstance(x, int):
- return float("nan")
- elif x < 0 or x > 10:
- return float("nan")
- elif x == 0:
- return 1
- else:
- return x*factorial(x-1)
- @handles("div", 2)
- def div(a,b):
- if b == 0:
- return float("nan")
- if a % b != 0:
- return float("nan")
- else:
- return int(a/b)
- def eval_rpn(seq):
- original_seq = list(seq)
- try:
- stack = []
- for item in seq:
- if item.isdigit():
- stack.append(int(item))
- elif item in rpn_callbacks:
- f, num_args = rpn_callbacks[item]
- args = [stack.pop() for _ in range(num_args)]
- args.reverse()
- result = f(*args)
- stack.append(result)
- else:
- raise Exception(f"Instruction {repr(item)} not implemented yet")
- if len(stack) == 1:
- return stack[0]
- else:
- return stack
- except:
- print(f"Exception evaluating rpn {repr(original_seq)}")
- raise
- def find_solution(x):
- """search for a solution to https://puzzling.stackexchange.com/questions/35268/make-11-from-five-identical-digits"""
- for i in itertools.count(4):
- for expr in iter_rpn(i, 5, x):
- result = eval_rpn(expr)
- if result == 11:
- return expr
- for i in range(10):
- expr = find_solution(i)
- print(" ".join(expr), "== 11")
- #result:
- """
- 0 fact 0 fact add 0 fact add square 0 fact add 0 fact add == 11
- 1 1 add 1 add square 1 add 1 add == 11
- 2 2 mul fact 2 add 2 div 2 sub == 11
- 3 3 mul 3 add 3 3 div sub == 11
- 4 4 mul 4 4 div sub 4 sub == 11
- 5 5 add 5 mul 5 add 5 div == 11
- 6 6 add 6 mul 6 sub 6 div == 11
- 7 7 add square 7 div 7 div 7 add == 11
- 8 8 add 8 add 8 div 8 add == 11
- 9 9 mul 9 add 9 add 9 div == 11
- """
Add Comment
Please, Sign In to add comment