Python基礎アルゴリズムケース:24点カードゲームアルゴリズム

作者:長行
時間:2020.05.14
Github原文:Week-03/Example-0303
ターゲット要件
任意に与えられた4枚のトランプについて、24ポイントのゲームを勝ち取る方法があるかどうかを計算する(すなわち、加算、減算、乗算、除算を用いて24にまとめる方法).ある場合は、可能なすべての方法をリストします.
【24時ルール】
大小王以外の52枚のうち、任意に4枚を抽出する.加算、減算、乗算、除四則演算(カッコ可)により、引いた4枚のカードを24とすると勝利となる.各カードは必ず使用しなければならず、一度しか使用できません.
第一の解法
ゲームのルールに基づいて,列挙の方法を用いてすべての計算方法を列挙し,4枚のトランプの数字をすべての計算方法に代入して結果を得,結果が24であれば解を求めるという解決策が考えられる.
これにより,第1の解法を得た.具体的なインプリメンテーションでは、可能なすべての4つの演算の組合せと可能なすべてのカッコの組合せを組み合わせて、可能なすべての演算の組合せを生成します.あるカードグループを計算するときは、まずすべてのカードグループのすべての可能な組合せ方式を計算し、すべての組合せ方式をすべての可能な計算式の組合せ解に持ち込む.

import itertools

class CardGaming:
    def __init__(self):
        self.formula_list = list()  #          
        for marks in itertools.product(["+", "-", "*", "/"], repeat=3):
            for bracket in ["{0}%s{1}%s{2}%s{3}", "({0}%s{1})%s{2}%s{3}", "({0}%s{1}%s{2})%s{3}",
                            "{0}%s({1}%s{2})%s{3}",
                            "{0}%s({1}%s{2}%s{3})", "({0}%s{1})%s({2}%s{3})", "{0}%s{1}%s({2}%s{3})"]:
                self.formula_list.append((bracket % marks))

    def solve(self, card_probability):
        answer = []
        for card_order in set(itertools.permutations(card_probability, 4)):  #              （  24   ）
            for formula in self.formula_list:  #          （448   ）
                final_formula = formula.format(*card_order)
                try:
                    if round(eval(final_formula), 3) == 24:
                        answer.append(final_formula)
                except ZeroDivisionError:
                    continue
        return answer

if __name__ == "__main__":
    print(CardGaming().solve((3, 3, 8, 8)))  #   : 8/(3-8/3)

現在のコードは、各カードグループの答えを計算する際に、4 3を巡回する必要があります.× 7 = 448 4^3\times{7}=448 43×7=448の数式と最大A 4 4=24 A^4_4=24 A 44=24種類のカード順、すなわち処理最大448× 24 = 10752 448\times{24}=10752 448×24=10752の可能性があります.この解法を用いてすべての可能なトランプの組み合わせ(合計1 3 3 4=28561 13^4=28561 134=28561 134=28561の解法)を計算するには1906秒(I 7 7700,8 GB)が必要である.
第2の解法
第1の解法では、各デッキの答えを計算する際に、処理の可能性には、「A+B-C+D」、「D-C+B+A」、「D+A-C+B」など.これは私たちの演算速度を大きく引きずっています.しかし、最初の解法に基づいてこれらの異なる状況を統合するには、記号、括弧、カードの順序を同時に考慮する必要があり、非常に複雑です.
そのため、私たちは別の角度からこの問題を解決することができます.
観察を通じて、どんな計算式でも、本質的には一定の順序で4枚のトランプの数値を3回演算していることが分かった.各演算は,未使用のトランプとそれまでの演算結果から2つを選択して演算する.したがって、すべての式を次のようにまとめることができます.
4枚のカードから任意に2つ抽出して任意演算を行い、抽出されていない2枚のカードと演算結果を3つの数値を含む新しいリストに組み合わせる.新しいリストから任意に2つ抽出して任意の演算を行い、抽出されていない1枚のカードと演算結果を2つの数値を含む新しいリストに構成する.新しいリストの2つの数値を任意に演算して結果を得,結果が24であれば解とする.
これにより,第2のアルゴリズムを得た.具体的な実装では、主に次の点に注意します.

は、数式を列挙しないため、非効率なeval()関数を使用して数式を実行する必要はありません.

演算中に演算式を生成すると演算量が多くなるので,解を求めた後に逆方向に解を生成する演算式のみを求める(それでも演算式を生成するのは難しくなるが,生成する回数は大幅に減少する).

def solve(card_probability):
    card_probability = list(card_probability)  #       
    answer = []
    for combine_1 in set(itertools.combinations(card_probability, 2)):  #       4       2  
        for answer_1 in all_maybe_count_answer(combine_1[0], combine_1[1]):
            card_list_1 = copy.deepcopy(card_probability)
            card_list_1.remove(combine_1[0])  #            1
            card_list_1.remove(combine_1[1])  #            2
            card_list_1.append(answer_1)  #            
            for combine_2 in set(itertools.combinations(card_list_1, 2)):  #       3       2  
                for answer_2 in all_maybe_count_answer(combine_2[0], combine_2[1]):
                    card_list_2 = copy.deepcopy(card_list_1)
                    card_list_2.remove(combine_2[0])  #            1
                    card_list_2.remove(combine_2[1])  #            2
                    card_list_2.append(answer_2)  #            
                    for combine_3 in set(itertools.combinations(card_list_2, 2)):  #          2  
                        for answer_3 in all_maybe_count_answer(combine_3[0], combine_3[1]):
                            if round(answer_3, 3) == 24:
                                answer.append(total_formula(card_probability, combine_1, answer_1, combine_2,
                                                            answer_2, combine_3, answer_3))  #       
    return answer


if __name__ == "__main__":
    start_time = time.time()
    for cards in list(itertools.product([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], repeat=4)):
        solve(cards)
    print("    :", time.time() - start_time)

(all_maybe_count_answer関数は、2つのパラメータを計算して4つの演算を行う可能性のあるすべての結果を計算し、total_formula関数は、中間変数に基づいて完全な計算式を生成する)
実行結果:

    : 136.27595901489258

この接法は1回目の4則演算時にC 4 2=6 C^2_4=6 C 42=6種類の抽出結果があり、6種類の演算結果がある(減算と除算は順序によって2つの結果がある).2回目の四則演算では、C 3 2=3 C^2_3=3 C 32=3種類の抽出結果があり、6種類の演算結果がある.3回目の四則演算では、C 2=1 C^2_2=1 C 22=1種の抽出結果であり,6種の演算結果がある.
したがって,このアルゴリズムは1つのトランプグループの解を求める際に,C 4 2のみを考慮する必要がある.× 6 × C 3 2 × 6 × C 2 2 × 6 = 3888 {C^2_4}\times{6}\times{C^2_3}\times{6}\times{C^2_2}\times{6}=3888 C42​×6×C32​×6×C22​×6=3888の可能性.この解法を用いてすべての可能なトランプの組み合わせ(合計1 3 3 4=28561 13^4=28561 134=28561 134=28561の解法)を計算すると,136秒(I 7 7700,8 GB)かかり,第1の解法より10倍以上速くなった.