JavaScriptで欠落している演算子を補って方程式を完成させる方法

数値の並びを受け取り、等式が成立するような正しい演算子の組み合わせを返すJavaScript関数を作成することを考えます。使用できる演算子は (+、−、*、/、^、%) の6種類です。

問題の概要

期待される入力と出力の関係は次のとおりです。

入力 : 5 3 8          出力 : 5+3=8
入力 : 9 27 3         出力 : 9=27/3
入力 : 5 2 25 , 1 5 2 出力 : 5^2=25 , 1=5%2

各入力には必ず少なくとも1つの解が存在することが保証されており、そのうち1つの正しい組み合わせを返すことが求められます。

解法のアプローチ

この問題を解くための基本的なアルゴリズムは次の流れになります。

• まず、等号の左右どちらかに置く大きい方の数を選びます。たとえば「1 4 7」であれば 7 を選びます。

• 次に、中央に向かって等号(=)を配置します。「1 4 7」の場合は「1 4=7」となります。

• 最後に、残りの隙間に演算子を当てはめて式を完成させます。

• その組み合わせで等式が成立しない場合は、別の数や演算子のパターンを試します。

本記事では総当たり(ブルートフォース)方式を採用しています。数値の間にあるスペースの位置に対して候補となる文字をランダムに挿入し、eval() で式を評価して等式が成り立つかどうかを判定します。すでに見つけた解答との重複チェックも行っています。

サンプルコード

const arr = ["5 3 8", "9 27 3", "5 2 25", "1 5 2", "3 3 3 30"];
const findCombination = (arr = []) => {
    const answers = [];
    for(let i = 0; i < arr.length; i++){
        const el = arr[i];
        // ブルートフォースで解を探索
        for(let n = 0; n < 1000; n++){
            const s = el.replace(/ /g, () => "+−*/^%="[Math.floor(Math.random() * 7)]);
            if(eval(s.replace(/=/g, "===").replace(/\^/g, "**")) === true
            && answers.indexOf(s) === -1){
                answers.push(s);
            };
        };
    }
    return answers;
};
console.log(findCombination(arr));

コードのポイント:

• スペースの位置に対して「+−*/^%=」の中からランダムに1文字を選んで挿入します。

• 等号は比較として機能させるために「===」へ置換し、べき乗を表す「^」はJavaScriptの累乗演算子「**」に変換してから評価します。

• 同じ解答が重複して配列に追加されないよう、indexOf() でチェックを行っています。

実行結果

コンソールへの出力は次のようになります。乱数を使用しているため、実行ごとに解の順序や見つかる組み合わせが異なる場合があります。

[
    '5+3=8',
    '9=27/3',
    '5^2=25',
    '1=5%2',
    '3=3%3^30',
    '3^3+3=30',
    '3+3^3=30'
]