Python-Implementierung des 24 Spiels

Question

unter meinem Versuch, das 24-Spiel in Python 2 zu implementieren, habe ich versucht, die Anforderungen von leetcode angegeben folgen: https://leetcode.com/problems/24-game/description/

Mein Ansatz ist im Grunde alle überprüfen die Permutationen der 4 Nummern versehen gegen alle Permutationen von 3 Operationen von 4 (addieren, subtrahieren, multiplizieren und dividieren).

Ich verwendete iteratools.product(), um die Permutationen der Operationen zu erhalten, da es wiederholte Operationen geben konnte.

Ich habe zwei Fragen:

1. Ich bin nicht sicher, ob alle Fälle, wenn die drei Codeblöcke in meinem inneren for-Schleife abzudecken, wenn ja, wie kann ich das beweisen kann? Zum Beispiel bin ich nicht sicher, ob ich ((W op (X op Y) op Z)) überprüfen sollte oder nicht.
2. Ich denke im schlimmsten Fall wäre 24 * 64 * 9 = 13824 Berechnungen. Kann die Anzahl der Berechnungen reduziert werden?

---

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

Hier sind einige allgemeine Hinweise.

1. Sie können das Ergebnis einiger Berechnungen cache. Dies ist in Ihrem Fall wahrscheinlich nicht erforderlich, aber Sie sollten wissen, wie Sie Speicher gegen Zeit austauschen können.
2. Sie können wiederholte Berechnungen vermeiden (der Ausdruck ops[0](ns[0], ns[1]) wird in jeder Iteration dreimal ausgewertet). Holen Sie das Ergebnis einmal und fügen Sie es in weitere Ausdrücke ein. Der letzte Punkt führt zu einer allgemeineren Überlegung: Jeder Ausdruck kann als tree dargestellt werden. Im Moment bist du brutal - erzwingt alle möglichen Bäume in einer (fast) zufälligen Reihenfolge. Gibt es eine Möglichkeit, es in einer "schlaueren" Reihenfolge zu tun? Sicher! Wenn die ersten beiden Zahlen 9 und 9 sind, und Sie sind bei 9*9+(x op y), dann ist es egal, welche Operation Sie auswählen und was die verbleibenden zwei Zahlen sind - Sie werden nicht in der Lage sein, auf 24 zu gehen. Versuchen Sie, an mehr zu denken "Stopp-Bedingungen", wenn Sie nicht weiter bewerten müssen.