Skip to content

Instantly share code, notes, and snippets.

@Wowfunhappy
Created June 14, 2023 22:29
Show Gist options
  • Save Wowfunhappy/5a8c794ffc1a3c221aa4d20040abb541 to your computer and use it in GitHub Desktop.
Save Wowfunhappy/5a8c794ffc1a3c221aa4d20040abb541 to your computer and use it in GitHub Desktop.
24 Solver
import itertools
import random
import time
import re
MAX_EXPONENT = 5
solutionList = []
#Based on https://theconfused.me/blog/solving-the-24-game/
def solve(numbers, expr=[]):
if expr == []:
expr = [str(n) for n in numbers]
if len(numbers) == 1:
if numbers[0] == goal:
return numbers[0]
else:
return False
if len(numbers) == 2:
answers, answer_exps = combinetwo(numbers[0], numbers[1])
for i,answer in enumerate(answers):
if answer == goal:
global solutionList
solutionList.append(remove_redundant_brackets(convert_expr_to_string(expr[0], expr[1], answer_exps[i])));
return False
pairs = set(itertools.combinations(numbers, 2))
for pair in pairs:
possible_values, possible_expr = combinetwo(*pair)
for counter, value in enumerate(possible_values):
expression = possible_expr[counter]
a_index = numbers.index(pair[0])
b_index = numbers.index(pair[1])
if a_index == b_index:
b_index = numbers.index(pair[1], a_index + 1);
expr_string = convert_expr_to_string(expr[a_index], expr[b_index], expression)
newlist = numbers[:]
newexpr = expr[:]
# replace the two numbers with the combined result
a_index = newlist.index(pair[0])
newlist.pop(a_index)
b_index = newlist.index(pair[1])
newlist.pop(b_index)
newlist.append(value)
# order matters
newexpr.pop(a_index)
newexpr.pop(b_index)
newexpr.append(expr_string)
result = solve(newlist, newexpr)
if result:
return remove_redundant_brackets(result)
else:
continue
def convert_expr_to_string(a, b, expr):
if expr == "removedB":
return a
elif expr == "removedA":
return b
else:
temp = [a, b]
result = '(' + str(temp[expr[0]]) + ')' + str(expr[1]) + '(' + str(temp[expr[2]]) + ')'
return result
def combinetwo(a, b):
result = []
expr = []
if not mustUseAll:
result.append(a)
expr.append("removedB")
result.append(b)
expr.append("removedA")
if allowAddition:
result.append(a + b)
expr.append((0, '+', 1))
if allowSubtraction:
if b > a:
result.append(b-a)
expr.append((1, '-', 0))
else:
result.append(a-b)
expr.append((0, '-', 1))
if allowMultiplication:
if (a != 1 and b != 1) or mustUseAll:
result.append(a * b)
expr.append((0, '*', 1))
if allowDivision:
if b != 0:
result.append(a / b)
expr.append((0, '/', 1))
if a != 0:
result.append(b / a)
expr.append((1, '/', 0))
if allowExponents:
if (a > 1 and b > 1) or mustUseAll:
if b <= MAX_EXPONENT:
result.append(a ** b)
expr.append((0, '^', 1))
if a <= MAX_EXPONENT:
result.append(b ** a)
expr.append((1, '^', 0))
return result, expr
def remove_redundant_brackets(expr):
stack = []
# indices to be deleted6 /
indices = []
for i, ch in enumerate(expr):
if ch == '(':
stack.append(i)
if ch == ')':
last_bracket_index = stack.pop()
enclosed = expr[last_bracket_index + 1:i]
if enclosed.isdigit():
indices.append(i)
indices.append(last_bracket_index)
return "".join([char for idx, char in enumerate(expr) if idx not in indices])
#Functions to remove duplicate expressions. ChatGPT wrote this code.
def _count_items(expr):
count = {}
for c in expr:
if c.isdigit() or c in "+-*/()":
count[c] = count.get(c, 0) + 1
return count
def remove_duplicate_expressions(expressions):
unique_expr = []
for expr in expressions:
count_expr = _count_items(expr)
if not any(_count_items(uexpr) == count_expr for uexpr in unique_expr):
unique_expr.append(expr)
return unique_expr
goal = 24
mustUseAll = False
allowAddition = True
allowSubtraction = True
allowMultiplication = True
allowDivision = True
allowExponents = True
solve([6, 4, 7, 6])
solutionList = remove_duplicate_expressions(solutionList)
if solutionList == []:
print("No solutions!")
else:
print(*solutionList, sep='\n')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment