python - 为 "Four fours"拼图制作拼图解算器

import itertools
import math
import time
from time import time
from math import factorial
from math import sqrt


def pretty(string):
    string=string.replace("(4)","4")
    string=string.replace("factorial4","factorial(4)")
    string=string.replace("sqrt4","sqrt(4)")
    return string


def test(n):
    start=time()
    fails=0
    for i in range(0,n+1):
        if(fours(i))!=None:
            print(fours(i))
        else:
            print("Failed: "+str(i))
            fails+=1
    return("\nFailed "+str(fails)+" out of "+str(n)+"\n\nTotal time: "+str(time()-start)       [:4]+"\nAverage time: "+str((time()-start)/n)[:4])

def fours(goal):
    operators = ['-', '/', '+', '*', '-sqrt', '-^', '-factorial', '-.', '/sqrt', '/^',   '/factorial',  '/.', '+sqrt', '+^', '+factorial', '+.', '*sqrt', '*^', '*factorial', '*.']
    brackets = ["{0}{1}{0}{2}{0}{3}{0}",
                "({0}{1}{0}){2}{0}{3}{0}",
                "({0}{1}{0}{2}{0}){3}{0}",
                "({0}{1}({0}{2}{0})){3}{0}",
                "(({0}{1}{0}){2}{0}){3}{0}",
                "{0}{1}({0}{2}({0}{3}{0}))",
                "{0}{1}(({0}{2}{0}){3}{0})",
                "({0}{1}{0}){2}({0}{3}{0})"]
    for combination in itertools.product(operators, repeat=3):
        for bracket in brackets:
            try:
                formula = bracket.format("(4)", *combination).replace(".(4","(.4")
            except ValueError:
                pass
            try:
                if eval(formula)==goal:
                    return(pretty((formula + " = " + str(int(eval(formula))))))
            except:
                pass

print(test(20))

这是“四个四”难题的求解器代码。 http://en.wikipedia.org/wiki/Four_fours 。

它大部分都有效，但随着输入量的增加，它会变慢。

我想做的是制作一个较小的运算符列表，就像这样。

['-','/','+','*','sqrt','^','factorial',"."]

但是要做到这一点，我需要这样做，以便程序可以将两个运算符放在一行中
这样它就可以得出这样的结果。

4/4+factorial(4)/sqrt(4) = 13

请注意，它们的阶乘紧跟在 + 号之后。

我之前问过如何做到这一点，有人建议我制作互斥列表，以便不在同一列表中的运算符可以一个接一个放置。

问题是，如果不彻底重写我的代码，我似乎无法找到一种有效的方法来做到这一点。

如果有人有这样做的好方法(或完成同一件事的更好方法)，请告诉我。

此外，我希望程序能够将两个四边形并排放置以生成类似 44 的数字，但是这样做给我带来了同样的问题。

例子:当我做 0 到 20 时，我得到

(4-(4-4))-4 = 0
(4-(4-4))/4 = 1
(4-(4-4))-sqrt(4) = 2
4-((4-sqrt(4))/sqrt(4)) = 3
4-((4-4)/4) = 4
4-((4/4)-sqrt(4)) = 5
4-((4-4)-sqrt(4)) = 6
4-((4/4)-4) = 7
4-((4-4)-4) = 8
4-((4-factorial(4))/4) = 9
(4-(4-4))/(.4) = 10

但是当我用我想用的系统做这件事时，我得到

(4-(4-4))-4 = 0
(4-(4-4))/4 = 1
4-((4+4)/4) = 2
(4+4+4)/4 = 3
4-((4-4)/4) = 4
(4+4*4)/4 = 5
(4+4)/4+4 = 6
4-((4/4)-4) = 7
4-((4-4)-4) = 8
4/4+4+4 = 9
Failed: 10

数字 10 失败，因为它不能在除法符号后放小数，而数字 9 不同，因为阶乘不能在后面 -

最佳答案

对于更大的目标，您的程序花费的时间太长，因为它会尝试取 3628804 的阶乘。Python 会在很长一段时间内解决这个问题。评估期间会发生这种情况:

(4)-factorial((4)+factorial((4)/(.4)))

= 4 - factorial( 4+factorial( 10 ) )

= 4 - 阶乘(3628804)

如果它成功了，那之后就更难做了。它不会在你有生之年结束。

您需要找到一种方法来避免此类计算。避免函数的组合(如 factorial(factorial(x)) 可能就足够了。避免这些问题的一个简单方法是编写一个中间函数，比如“lfact”，以限制计算阶乘的大小。lfact 将测试参数, 如果太大则引发异常或返回 None, 否则调用 math.factorial. 你会在你的 eval'd 公式中调用你的替代 lfact 函数。

关于python - 为 "Four fours"拼图制作拼图解算器，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21396155/