Guest User

Untitled

a guest
Oct 29th, 2020
19
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.  
  63. @handles("add", 2)
  64. def add(a,b):
  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. """
  132. 0 fact 0 fact add 0 fact add square 0 fact add 0 fact add == 11
  133. 1 1 add 1 add square 1 add 1 add == 11
  134. 2 2 mul fact 2 add 2 div 2 sub == 11
  135. 3 3 mul 3 add 3 3 div sub == 11
  136. 4 4 mul 4 4 div sub 4 sub == 11
  137. 5 5 add 5 mul 5 add 5 div == 11
  138. 6 6 add 6 mul 6 sub 6 div == 11
  139. 7 7 add square 7 div 7 div 7 add == 11
  140. 8 8 add 8 add 8 div 8 add == 11
  141. 9 9 mul 9 add 9 add 9 div == 11
  142. """
RAW Paste Data