24 Solver

24-solver.py

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')