Pythonで演算子と括弧を挿入して24を作れるかどうかを判定するプログラム

問題の概要

1から9の範囲にある数字が、固定された順序でリストとして与えられます。これらの数字の間に「+」「-」「*」「/」（/は整数除算を表す）の演算子を挿入し、さらに括弧でグループ化することで、計算結果を24にできるかどうかを判定するのがこの問題です。

例えば、入力が nums = [5, 3, 6, 8, 7] の場合、(5 * 3) - 6 + (8 + 7) = 24 となるため、出力は True になります。

解決のアプローチ

この問題は、再帰的な分割統治法を用いて効率的に解くことができます。数列を前半と後半に分割し、それぞれの部分で作り出せるすべての値を列挙して、それらを4種類の演算子で組み合わせます。具体的な手順は以下の通りです。

• 関数 recur() を定義する。引数として配列 arr を受け取る
• answer := 新しいリスト
• i を 0 から arr のサイズ - 2 まで繰り返す
  • pre := recur(arr[先頭から i まで])
  • suf := recur(arr[i + 1 から末尾まで])
  • pre の各要素 k に対して
    • suf の各要素 j に対して
      • answer の末尾に (k + j) を追加
      • answer の末尾に (k - j) を追加
      • answer の末尾に (k * j) を追加
      • j が 0 でない場合
        • answer の末尾に (k / j の商) を追加
• answer のサイズが 0 で、かつ arr のサイズが 1 の場合
  • answer の末尾に arr[0] を追加
• answer を返す
• メイン処理では、24 が recur(nums) の結果に含まれているかを確認し、含まれていれば True、そうでなければ False を返す

この方法では、0による除算を回避するために、割り算の結果は j が 0 でない場合にのみ追加している点に注目してください。また、配列のサイズが1のとき（再帰の終端）には、その要素自体が唯一の候補値となります。

実装例

以下にPythonでの実装を示します。

class Solution:
   def solve(self, nums):
      def recur(arr):
         answer = []
         for i in range(len(arr) - 1):
            pre, suf = recur(arr[: i + 1]), recur(arr[i + 1 :])
            for k in pre:
               for j in suf:
                  answer.append(k + j)
                  answer.append(k - j)
                  answer.append(k * j)
                  if j != 0:
                     answer.append(k // j)
         if len(answer) == 0 and len(arr) == 1:
            answer.append(arr[0])
         return answer
      return 24 in recur(nums)
ob = Solution()
nums = [5, 3, 6, 8, 7]
print(ob.solve(nums))

入力

[5, 3, 6, 8, 7]

出力

True

まとめ

このアルゴリズムは、すべての分割位置と演算子の組み合わせを再帰的に探索することで、24が作れるかどうかを確実に判定できます。計算量は数列の分割数と値の組み合わせ数に依存しますが、要素数が限られている場合は十分に実用的な速度で動作します。