python - 优化蛮力数字求解器python的建议

Question

我知道其他一些类似的线程，但我不确定如何将它们应用到我的示例中。

我正在尝试通过蛮力算法攻击倒计时数字游戏。这是我第一次尝试这样的事情，有什么关于如何加快这个过程的提示吗？

我正在针对给定初始数字无法解决答案的情况进行测试。这最终将与完整游戏的 tkinter 界面配对。

结构应该是这样的，我们尝试 abcdef 的每个顺序和 op1-5 的每个操作组合

from datetime import datetime
import itertools
import math

starttime = datetime.now()
def permutationG(input, s):
    if len(s) == len(input): yield s
    for i in input:
        if i in s: continue
        s=s+i
        for x in permutationG(input, s): yield x
        s=s[:-1]
def op(operator, number1,number2):
    string=str(number1)+str(operator)+str(number2)
    return eval(string)

a=11
b=10
c=9
d=8
e=7
f=6

targetnumber = 101234
    
listofnumbers = ['a','b','c','d','e','f']
listprep = ['+','-','*','/']
stringofnumbers = ''.join(str(e) for e in listofnumbers)


numberlocations =[]

for item in permutationG(listofnumbers,''):
    numberlocations.append(item)
numberlocations = set(numberlocations)

myarray = itertools.combinations_with_replacement(listprep, 5)
operatorlist = []
for item in myarray:
    #for all different numbers find the different permutations
    temp = list(itertools.permutations(item))
    operatorlist.extend(temp)
#remove duplicates
finaloplist = list(set(operatorlist))

dist=[math.inf]
currentclosestnumber = 0
count=0
looptime=datetime.now()
print('Starting Loop')

for item in numberlocations:
    for ops in finaloplist:
        initial_value = op(ops[0],item[0],item[1])
        for i in range(2,len(item)):
            intcheck2 = int(initial_value) - initial_value
            if initial_value != targetnumber and initial_value >= 0 and intcheck2 == 0:
                newvalue = op(ops[i-1], initial_value, item[i])
            else:
                break
            initial_value = newvalue
        attempt = initial_value
        intcheck = int(attempt) - attempt
        distance = targetnumber - initial_value
        if abs(distance) < abs(dist[0]) and intcheck == 0:
            currentclosestnumber = attempt
            dist[0]=distance
            print(attempt)
        if targetnumber == attempt:
            break
    if targetnumber == attempt:
        break

endtime = datetime.now()
stringtime= endtime-starttime
#print('Loops:    ', count)

if targetnumber == attempt:
    print('FOUNDIT!! Target Number = %s     Closest Number = %s        Time Elapsed = %s' %(targetnumber, currentclosestnumber, stringtime))
elif targetnumber!=attempt:
    print('Heres how close: Target Number = %s     Closest Number = %s        Time Elapsed = %s' %(targetnumber, currentclosestnumber, stringtime))

这会输出大约一分半钟的时间。

另一个问题是因为我使用的方法(使用 eval 字符串操作)我不知道在打印时显示括号在最终公式中的位置，或者如何在末尾将 eval 放入 zip 中显示数字而不是字母。

非常感谢任何指导。

---

注意:我已经使用最新版本的代码编辑了帖子。这将计算时间从 1:30 减少到 0:45。主要的变化是我为每个顺序操作创建了一个 for 循环，而不是一长串的计算，并使用 if 语句来确保当前值是负数或小数时它会中断。

这大大减少了所需的计算量。

Answer 1

这是一个较慢的版本，但没有错误。

我没有时间尝试优化，但我的想法是大部分问题在于在拆分子集时创建/销毁垃圾。

如果我真的希望它很快，我认为您可以使用动态编程方法。

def subset_splits (a_list):
    if 0 == len(a_list):
        yield ([], [])
    else:
        for sublist1, sublist2 in subset_splits(a_list[1:]):
            yield ([a_list[0]] + sublist1, sublist2)
            yield ([a_list[0]] + sublist2, sublist1)

def reachable (numbers):
    if 1 == len(numbers):
        yield (numbers[0], numbers[0])
    else:
        for list1, list2 in subset_splits(numbers):
            if 0 == len(list2):
                continue
            for x1, expr1 in reachable(list1):
                for x2, expr2 in reachable(list2):
                    yield x1+x2, (expr1, '+', expr2)
                    yield x1*x2, (expr1, '*', expr2)
                    yield x1-x2, (expr1, '-', expr2)
                    yield x2-x1, (expr2, '-', expr1)
                    if 0 != x2:
                        yield x1/x2, (expr1, '/', expr2)
                    if 0 != x1:
                        yield x2/x1, (expr2, '/', expr1)

numbers = [1, 2, 3, 4, 5, 6]
target = 10000

best = numbers[0]
if best == target:
    print(("Answer: ", numbers[0], numbers[0]))
else:
    print(("Best: ", numbers[0], numbers[0]))
    done = False;
    for s, t in subset_splits(numbers):
        if done:
            break

        for x, expr in reachable(s):
            if x == target:
                print(("Answer: ", x, expr))
                done = True
                break
            elif abs(target-x) < abs(target-best):
                print(("Best: ", x, expr))
                best = x

        if done:
            break


        for x, expr in reachable(t):
            if x == target:
                print(("Answer: ", x, expr))
                done = True
                break
            elif abs(target-x) < abs(best-x):
                print(("Best: ", x, expr))
                best = x