"24 point game algorithm" Code Answer's

24 point game algorithm

By Faithful Fly on Oct 09, 2020

import itertools

def solve(numbers, goal=24, 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:
                return 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, goal, newexpr)
            if result:
                return remove_redundant_brackets(result)
            else:
                continue

def convert_expr_to_string(a, b, expr):
    temp = [a, b]
    result = '(' + str(temp[expr[0]]) + ')' + str(expr[1]) + '(' + str(temp[expr[2]]) + ')'
    return result

def combinetwo(a, b):
    result = [a + b, a * b]
    expr = [(0, '+', 1), (0, '*', 1)]
    if b > a:
        result.append(b-a)
        expr.append((1, '-', 0))
    else:
        result.append(a-b)
        expr.append((0, '-', 1))
    if b != 0:
        result.append(a / b)
        expr.append((0, '/', 1))
    if a != 0:
        result.append(b / a)
        expr.append((1, '/', 0))
    return result, expr

def remove_redundant_brackets(expr):
    stack = []
    # indices to be deleted
    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])

Source: theconfused.me

Add Comment