【Dison夏令营 Day 17】使用 Python Turtle 的 24 游戏求解器

24 点 是一个数学谜题，用基本算术运算符（+、-、×、÷）将 4 个数字运算成 24。例如，给定 4 个数字 1,5,5,5，我们可以得到表达式 (5-(1÷5))×5，等于 24。

我们可以用 Python 程序暴力解决这个问题。最多有 24×5×4×4×4 = 7,680 个不同的表达式可以用 4 个数字组成。这对我们来说似乎很难，但对计算机程序来说应该很容易解决。下面是这个项目的源代码：

import turtle
screen = turtle.Screen()
screen.setup(500,500)
screen.title("24 Game Solver - PythonTurtle.Academy")
turtle.hideturtle()
turtle.speed(0)
turtle.up()

def permutation(a):
    if len(a) == 1: return [[a[0]]]
    res = permutation(a[1:])
    r = []
    for x in res:
        # need to insert n into x: into all possible position
        for i in range(len(x)+1):
            y = x.copy()
            y.insert(i,a[0])
            if y not in r:
                r.append(y)
    return r

op = ['+', '−', '×', '÷']
def evaluate(a):
    v = []
    for x in a:
        if type(x) is int:
            v.append(x)
        else:
            num2 = v.pop()
            num1 = v.pop()
            if x=='+': v.append(num1+num2)
            elif x=='−': v.append(num1-num2)
            elif x=='×': v.append(num1*num2)
            else:
                if num2 != 0: v.append(num1/num2)
                else: return 0
    return v[0]


class tree_node:
    def __init__(self,value,left,right):
        self.value = value
        self.left = left
        self.right = right

def inorder(root):
    if type(root.value) is int: return str(root.value)
    if type(root.left.value) is not int: left = '('+inorder(root.left)+')'
    else: left = inorder(root.left)
    if type(root.right.value) is not int: right = '('+inorder(root.right)+')'
    else: right = inorder(root.right)    
    return left + root.value + right
    
def convert_to_infix(a):
    # convert to infix
    # convert to tree first
    v = list()
    for x in a:
        if type(x) is int:
            v.append(tree_node(x,None,None))
        else:
            t2 = v.pop()
            t1 = v.pop()
            v.append(tree_node(x,t1,t2))
    return inorder(v[0])
            
def twentyfour(a):
    # postfix
    # try n,n,n,n, p,p,p
    for i in range(4):
        for j in range(4):
            for k in range(4):
                b = a.copy()
                b.append(op[i])
                b.append(op[j])
                b.append(op[k])
                v = evaluate(b)
                if v==24.0:
                    return(convert_to_infix(b))

    # try n,n,n,p,p,n,p
    for i in range(4):
        for j in range(4):
            for k in range(4):
                b = a[:3]
                b.append(op[i])
                b.append(op[j])
                b.append(a[3])
                b.append(op[k])
                v = evaluate(b)
                if v==24.0:
                    return(convert_to_infix(b))

    # try n,n,n,p,n,p,p
    for i in range(4):
        for j in range(4):
            for k in range(4):
                b = a[:3]
                b.append(op[i])
                b.append(a[3])
                b.append(op[j])
                b.append(op[k])
                v = evaluate(b)
                if v==24.0:
                    return(convert_to_infix(b))

    # try n,n,p,n,p,n,p
    for i in range(4):
        for j in range(4):
            for k in range(4):
                b = a[:2]
                b.append(op[i])
                b.append(a[2])
                b.append(op[j])
                b.append(a[3])
                b.append(op[k])
                v = evaluate(b)
                if v==24.0:
                    return(convert_to_infix(b))
    # try n,n,p,n,n,p,p
    for i in range(4):
        for j in range(4):
            for k in range(4):
                b = a[:2]
                b.append(op[i])
                b.append(a[2])
                b.append(a[3])
                b.append(op[j])
                b.append(op[k])
                v = evaluate(b)
                if v==24.0:
                    return(convert_to_infix(b))
    return ''            

while True:
    fournumbers = []
    while len(fournumbers) != 4:
        numbers = screen.textinput("24 Game Solver", "Enter four numbers separated by spaces: ")
        fournumbers = list(map(int,numbers.split()))
    p = permutation(fournumbers)
    foundsolution = False
    turtle.clear()
    for a in p:
        r = twentyfour(a)
        if len(r)>0:
            turtle.goto(0,0)
            turtle.color('royal blue')
            turtle.write(r,font=('Courier', 45, 'bold'), align='center')
            foundsolution = True
            break
    if not foundsolution:
        turtle.color('red')
        turtle.write("No solution",font=('Courier', 45, 'bold'), align='center')

原文地址：https://blog.csdn.net/weixin_41446370/article/details/140385823

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！