python - 为 "Four fours"谜题制作解谜器

Question

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 不同，因为阶乘不能在 -

Answer 1

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

• (4)-阶乘((4)+阶乘((4)/(.4)))
• = 4 - 阶乘( 4+阶乘( 10 ) )
• = 4 - 阶乘(3628804)

如果它成功通过了那一步，那之后还有更难的事情要做。它不会在你的一生中完成。

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