JavaScriptで四則演算を使って目標値を作れるか判定する方法

問題

ちょうど4つの数値からなる配列 arr を第1引数に、目標値 target を第2引数として受け取る JavaScript 関数を書く必要があります。

この関数の役割は、配列内の数値に対して *（掛け算）、/（割り算）、+（足し算）、-（引き算）および括弧 ( ) を自由に組み合わせて、target と等しい値を作り出せるかどうかを判定することです。

たとえば、関数への入力が次の場合を考えてみましょう。

入力

const arr = [5, 3, 2, 1];
const target = 4;

出力

const output = true;

出力の説明

次のように計算すれば 4 を作れるためです −

(5 - 1) * (3 - 2) = 4

解き方のアプローチ

この種の問題は、いわゆる「24ゲーム」のようなパズルと同じ構造を持っており、全数探索（バックトラッキング）が有効です。考え方の流れは以下のとおりです。

• 配列の中から任意の2つの数値を選びます。
• 選んだ2つの数に対して、a+b、a-b、b-a、a*b、a/b、b/a の6通りすべての演算結果を試します。
• 演算結果を新しい要素として配列に戻し、残りの要素数を1つずつ減らしながら再帰的に同じ処理を繰り返します。
• 最終的に配列が1つの値になった時点で、その値が target と一致するかどうかを判定します。

ここで重要なのが浮動小数点の誤差処理です。除算を含む演算では誤差が蓄積するため、x === target のような厳密な比較ではなく、Math.abs(x - target) < 0.0000001 のように十分に小さい許容誤差を使った近似比較を行うのがポイントになります。

例

以下が実際のコードです −

const arr = [5, 3, 2, 1];
const target = 4;
const canOperate = (arr = [], target = 1) => {
   const isValid = x => Math.abs(x - target) < 0.0000001
   const helper = (arr = []) => {
      if (arr.length === 1) {
         return isValid(arr[0])
      }
      let valid = false
      for (let i = 0; i < arr.length; i++) {
         for (let j = i + 1; j < arr.length; j++) {
            const nextArr = arr.filter((x, index) => index !== i && index !== j)
            valid = valid || helper([...nextArr, arr[i] + arr[j]])
            || helper([...nextArr, arr[i] - arr[j]])
            || helper([...nextArr, arr[j] - arr[i]])
            || helper([...nextArr, arr[i] * arr[j]])
            || helper([...nextArr, arr[i] / arr[j]])
            || helper([...nextArr, arr[j] / arr[i]])
         }
      }
      return valid
   }
   return helper(arr)
}
console.log(canOperate(arr, target));

コードの解説

• isValid：誤差を考慮した目標値との一致判定を行うヘルパー関数です。
• helper：再帰的な探索本体です。配列の長さが1になったら一致判定を行い、それ以外は2つずつ組み合わせて全演算パターンを試します。
• filter を使って選んだ2要素を取り除いた新しい配列 nextArr を作り、そこへ演算結果を追加して再帰呼び出しを行います。
• 一度でも true になる経路が見つかれば、valid が true のまま残るため、以降の不要な探索も短絡評価によって効率化されます。

出力

上記のコードを実行すると、コンソールには次の結果が出力されます。

true