24小时游戏的Python实现

Question

以下是我尝试在 Python 2 中实现 24 游戏，我尝试遵循 leetcode 中指定的要求:https://leetcode.com/problems/24-game/description/

我的方法基本上是检查 4 个提供的数字的所有排列与 4 个操作中的 3 个操作(加、减、乘和除)的所有排列。

我使用 iteratools.product() 来获取操作的排列，因为可能会有重复的操作。

我有两个问题:

1. 我不确定内部 for 循环中的 3 个代码块是否涵盖了所有情况，如果涵盖了，我该如何证明？例如，我不确定是否应该检查 ((W op (X op Y) op Z))。
2. 我认为在最坏的情况下会有 24 * 64 * 9 = 13824 次计算。可以减少计算次数吗？

---

import itertools
class Solution(object):
    def judgePoint24(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        Ops = list(itertools.product([add,sub,mul,div], repeat=3))
        for ns in set(itertools.permutations(nums)):
            for ops in Ops:
                # W = ns[0], X = ns[1], Y = ns[2], Z = ns[3]

                # (((W op X) op Y) op Z)
                result = ops[0](ns[0], ns[1])
                result = ops[1](result, ns[2])
                result = ops[2](result, ns[3])
                if 23.99 < result < 24.01:
                    return True

                # (Z op (Y op (W op X)))
                result = ops[0](ns[0], ns[1])
                result = ops[1](ns[2], result)
                result = ops[2](ns[3], result)
                if 23.99 < result < 24.01:
                    return True

                # ((W op X) op (Y op Z))
                result1 = ops[0](ns[0], ns[1])
                result2 = ops[1](ns[2], ns[3])
                result = ops[2](result1, result2)
                if 23.99 < result < 24.01:
                    return True
        return False

def add (a, b):
    return a+b
def sub (a, b):
    return a-b
def mul (a, b):
    return a*b
def div (a, b):
    if b == 0:
        return 0
    return a/float(b)

Answer 1

这里有一些通用的提示。

1. 你可以cache一些计算的结果。这在您的情况下可能不是必需的，但您应该知道如何权衡内存与时间。
2. 您可以避免重复计算(表达式 ops[0](ns[0], ns[1]) 在每次迭代中计算三次)。一次获取结果并将其插入到更多表达式中。
3. 最后一点引出了一个更一般的考虑:每个表达式都可以表示为 tree .现在你正在以(几乎)随机的顺序暴力破解所有可能的树。有没有办法以“更智能”的顺序进行？当然!如果前两个数字是 9 和 9，而你在 9*9+(x op y)，那么它不会无论您选择哪种操作以及剩余的两个数字是多少 - 您都无法减少到 24。当您不需要继续评估时，请尝试考虑更多“停止条件”。