Download the file
  1. DIGITS = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}
  2. ZERO = {"0"}
  3. OPERATORS = {"+", "-", "*", "/"}
  4. EQUAL = {'='}
  5.  
  6. CORRECT = "c"
  7. INCORRECT = "i"
  8. ABSENT = "a"
  9.  
  10. class Solver:
  11. def __init__(self, digits=DIGITS, operators=OPERATORS):
  12. self.digits = digits.copy()
  13. self.operators = operators.copy()
  14. self.corrects = [None] * 8
  15. self.incorrects = [set() for _ in range(8)]
  16. self.unused = digits | operators
  17.  
  18. def all_absent(self, char, expr, result):
  19. res = True
  20. for e,r in zip(list(expr), list(result)):
  21. if e == char:
  22. res &= (r == ABSENT)
  23. return res
  24.  
  25. def record(self, last_expr, last_result):
  26. for i,(e,r) in enumerate(zip(list(last_expr), list(last_result))):
  27. self.unused -= {e}
  28. if r == CORRECT:
  29. self.corrects[i] = e
  30. elif r == ABSENT:
  31. self.incorrects[i].add(e)
  32. if self.all_absent(e, last_expr, last_result):
  33. if e in self.digits:
  34. self.digits -= {e}
  35. elif e in self.operators:
  36. self.operators -= {e}
  37. elif r == INCORRECT:
  38. self.incorrects[i].add(e)
  39. else:
  40. # do something about typo
  41. pass
  42.  
  43. def next_set(self, expr, element=[]):
  44. if len(expr) == 0:
  45. return self.digits - ZERO
  46. elif len(expr) == 1:
  47. return self.digits | self.operators
  48. elif set(expr) & EQUAL == EQUAL:
  49. return self.digits
  50. elif len(expr) == 6 and expr[-1] not in EQUAL:
  51. return EQUAL
  52. elif set(expr) & OPERATORS != set() and expr[-1] not in OPERATORS:
  53. return self.digits | self.operators | EQUAL
  54. else:
  55. if expr[-1] in OPERATORS:
  56. return self.digits - ZERO
  57. elif len(expr) > 2 and set(expr[-3:]) - DIGITS == set():
  58. return self.operators
  59. else:
  60. return self.digits | self.operators
  61.  
  62. def validate(self, expr, res):
  63. if self.unused == set() and (self.digits | self.operators) - set(expr) != set():
  64. return False
  65. if set(expr) & EQUAL == set():
  66. return False
  67. if not set(res) <= self.digits:
  68. return False
  69. for i,e in enumerate(res):
  70. pos = len(expr) - len(res) + i
  71. if self.corrects[pos] is not None and e != self.corrects[pos]:
  72. return False
  73. elif e in self.incorrects[pos]:
  74. return False
  75. return True
  76.  
  77. def score(self, expr):
  78. # Favour experessions that use many different symbols and use many yet-unused symbols.
  79. return -(len(self.unused | set(expr)) + len(set(expr)))
  80.  
  81. def evaluate(self, expr, solutions):
  82. try:
  83. res = eval("".join(expr[:-1]))
  84. except:
  85. pass
  86. else:
  87. if res >= 0 and int(res) == res:
  88. res = list(str(int(res)))
  89. if len(expr) + len(res) == 8:
  90. expr += res
  91. if self.validate(expr, res):
  92. solutions.add("".join(expr))
  93.  
  94. def _solve(self, solutions, expr=[]):
  95. pos = len(expr)
  96. if pos > 0 and expr[-1] in EQUAL:
  97. self.evaluate(expr, solutions)
  98. else:
  99. next_set = self.next_set(expr) - self.incorrects[pos]
  100. if self.corrects[pos] is not None:
  101. next_set &= {self.corrects[pos]}
  102. for e in next_set:
  103. self._solve(solutions, expr + [e])
  104.  
  105. def _solutions(self):
  106. solutions = set()
  107. self._solve(solutions)
  108. return {(self.score(e), e) for e in solutions}
  109.  
  110. def solve(self):
  111. solutions = list(self._solutions())
  112. return (sorted(solutions)[0], len(solutions))
  113.  
  114. def input(self, prompt=""):
  115. while True:
  116. s = input(prompt).strip()
  117. if len(s) == 8 and set(s) <= { CORRECT, INCORRECT, ABSENT }:
  118. return s
  119. else:
  120. print("Invalid input")
  121.  
  122. def run(self, expr="8+7*6=50", count=2562890625):
  123. if count == 2562890625:
  124. print("([c]orrect [i]ncorrect [a]bsent")
  125. if count > 1:
  126. self.record(expr, self.input(f"{expr} > ").strip())
  127. try:
  128. (score, expr), count = self.solve()
  129. except:
  130. print("Failed to find a suitable solution")
  131. else:
  132. self.run(expr, count)
  133. else:
  134. print(expr)
  135.  
  136.  
  137. if __name__ == '__main__':
  138. Solver().run()
  139.