# Untitled

a guest
Oct 29th, 2020
38
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import math
2. import itertools
3.
4. unary_operators = []
5. binary_operators = []
6. NUMBER = 0
7.
8. def iter_rpn(ops, values, value_literal):
9. """iterate through all rpn expressions ith `ops` operators and `values` values, all of which are `value_literal`"""
10. if ops == 0:
11. if values == 1:
12. yield (str(value_literal),)
13. return
14. if values >= 1:
15. for operator in unary_operators:
16. for expr in iter_rpn(ops-1, values, value_literal):
17. yield expr + (operator,)
18. if values >= 2:
19. for operator in binary_operators:
20. for l_ops in range(ops):
21. r_ops = ops - l_ops - 1
22. for l_values in range(1, values):
23. r_values = values - l_values
24. for l_expr in iter_rpn(l_ops, l_values, value_literal):
25. for r_expr in iter_rpn(r_ops, r_values, value_literal):
26. yield l_expr + r_expr + (operator,)
27.
28. cache = {} #structured like {args: {evaluated_result: expr}
29. def memoize_rpn_generator(f):
30. def gen(*args):
31. if args not in cache:
32. cache[args] = {}
33. for expr in f(*args):
34. result = eval_rpn(expr)
35. if not isinstance(result, int): continue
36. cache[args][result] = expr
37. return list(cache[args].values())
38. return gen
39. iter_rpn = memoize_rpn_generator(iter_rpn)
40.
41. rpn_callbacks = {}
42. def handles(name, num_args):
43. [unary_operators, binary_operators][num_args-1].append(name)
44. def _handles(f):
45. rpn_callbacks[name] = (f, num_args)
46. return f
47. return _handles
48.
49. @handles("square", 1)
50. def square(x):
51. return x**2
52.
53. @handles("sqrt", 1)
54. def sqrt(x):
55. if x < 0:
56. return float("nan")
57. result = math.sqrt(x)
58. if not result.is_integer():
59. return float("nan")
60. else:
61. return int(result)
62.
65. return a+b
66.
67. @handles("sub", 2)
68. def sub(a,b):
69. return a-b
70.
71. @handles("mul", 2)
72. def mul(a,b):
73. return a*b
74.
75. @handles("fact", 1)
76. def factorial(x):
77. if not isinstance(x, int):
78. return float("nan")
79. elif x < 0 or x > 10:
80. return float("nan")
81. elif x == 0:
82. return 1
83. else:
84. return x*factorial(x-1)
85.
86. @handles("div", 2)
87. def div(a,b):
88. if b == 0:
89. return float("nan")
90. if a % b != 0:
91. return float("nan")
92. else:
93. return int(a/b)
94.
95. def eval_rpn(seq):
96. original_seq = list(seq)
97. try:
98. stack = []
99. for item in seq:
100. if item.isdigit():
101. stack.append(int(item))
102. elif item in rpn_callbacks:
103. f, num_args = rpn_callbacks[item]
104. args = [stack.pop() for _ in range(num_args)]
105. args.reverse()
106. result = f(*args)
107. stack.append(result)
108. else:
109. raise Exception(f"Instruction {repr(item)} not implemented yet")
110. if len(stack) == 1:
111. return stack[0]
112. else:
113. return stack
114. except:
115. print(f"Exception evaluating rpn {repr(original_seq)}")
116. raise
117.
118. def find_solution(x):
119. """search for a solution to https://puzzling.stackexchange.com/questions/35268/make-11-from-five-identical-digits"""
120. for i in itertools.count(4):
121. for expr in iter_rpn(i, 5, x):
122. result = eval_rpn(expr)
123. if result == 11:
124. return expr
125.
126. for i in range(10):
127. expr = find_solution(i)
128. print(" ".join(expr), "== 11")
129.
130. #result:
131. """