Zenn
Closed13

【求ム】加算・減算して任意数になるかの判定関数

判定
組み合わせ
問題
nekonikinekoniki

概要

車のナンバーでよくやる遊びですが、与えられた複数の数字を加算・減算して任意の数になるかどうかの判定処理を考えてます。
組み合わせをどう表現するか、という話になるかと思いますが、色々な言語で書いた際にどんな違いがあるかを見てみたいです。

以下ルールです。

  • 言語・バージョンは問わない
  • その言語で使える機能・記法なら何でも使って良い
  • 外部ライブラリはなし(=その言語をセットアップした段階で使える機能のみ使用可能)
  • 扱う数字は自然数の配列で与えられる
  • 簡単のため、判定に使う数字は10とする(=加算・減算で10になるかどうかを判定する)
  • 配列の先頭の数のみ、常に正の値とする(=減算を考慮しない)
  • 10になる場合はTRUEを、ならない場合はFALSEを出力する

上記を踏まえると、テストデータとしては以下でいいかなと思っています。

  • 10になる組み合わせ：[6,7,1,4]
  • 10にならない組み合わせ：[1,2,3,5]
  • 先頭数字のマイナスを考慮した場合のみ10になる組み合わせ：[4,7,6,1]

回答やツッコミ(マサカリ)等々絶賛募集中です。
既に出ている例より短く・効率よく書ける例も募集です。

nekonikinekoniki

例えばJS ならこんな感じ。

// 10になる組み合わせ(6+7+1-4)
const testData = [6,7,1,4];
// 10にならない組み合わせ
const testData2 = [1,2,3,5];
// 先頭をマイナスにすることで10になる組み合わせ
const testData3 = [4,7,6,1];

const checker = (data) => {
    const result = data.reduce((acc, crr) => {
        if (!acc.length) acc.push(crr)
        else {
          acc = acc.reduce((acc1, crr1) => {
            acc1.push(crr1 + crr)
            acc1.push(crr1 - crr)
            return acc1
          }, [])
      }
      return acc
    }, []).includes(10);
    
    console.log(result? 'TRUE' : 'FALSE');
}

// --> TRUE
checker(testData);
// --> FALSE
checker(testData2);
// --> FALSE
checker(testData3);
catnosecatnose

こんな感じで書くこともできそう？（あまり変わっていないですが）

js
const checker = (data) => {
    const [first, ...rest] = data
    const result = rest.reduce(
      (acc, crr) => acc.map(n => [n + crr, n - crr]).flat(), // 現在の累計に足したパターンと引いたパターンを追加
      [first]
    ).includes(10);
    console.log(result ? 'TRUE' : 'FALSE');
}
nekonikinekoniki

回答ありがとうございます！
たしかにflat使った方がスッキリしますね。

リアルにサーモンリアルにサーモン

二分木として、深さ優先探索でやってみました(Scala)

object Solution {
  def checker(data: Array[Int]): Boolean = {
    val SUM = 10
    
    def dfs(acc: Int, d: Array[Int]): Boolean = {
      if (d.isEmpty) return acc == 10
      dfs(acc + d(0), d.drop(1)) || dfs(acc - d(0), d.drop(1))

      // こっちのがscalaっぽい?
      // d.headOption.map(h => dfs(acc + h, d.drop(1)) || dfs(acc - h, d.drop(1))).getOrElse(acc == 10)
    }

    // dfs(0, data) 先頭マイナスを考慮した場合
    dfs(data(0), data.drop(1))
  }
}
nekonikinekoniki

回答ありがとうございます！
おお、Scala初見なのですごく参考になります！

mos1210mos1210

ビット全探索でやってみました。(c++)

#include <bits/stdc++.h>

using namespace std;

const int SUM = 10;

string checker(vector<int> A) {
    for (int tmp = 0; tmp < (1 << A.size()); tmp++) {
        bitset<20> s(tmp); // 最大20個

        int sum = 0;
        for (int i = 0; i < A.size(); ++i) {
            if (i == 0 || s.test(i)) {
                sum += A.at(i);
            } else {
                sum -= A.at(i);
            }
        }
        if (sum == SUM) {
            return "TRUE";
        }
    }
    return "FALSE";
}

int main() {
    cout << checker({6, 7, 1, 4}) << endl;
    cout << checker({1, 2, 3, 5}) << endl;
}
nekonikinekoniki

回答ありがとうございます！
全然思いつきませんでした！
ビット全探索のパターンいいですね！

ほげさんほげさん

演算子の方を回してみた

/tmp/a.hs
f [a, b, c, d]  = elem 10 $ (\op1 op2 op3 -> a `op1` b `op2` c `op3` d ) <$> [(+), (-)] <*> [(+), (-)] <*> [(+), (-)]

main = print $ f [6, 7, 1, 4]    -- True
nekonikinekoniki

回答ありがとうございます！
サラッと書かれてますが、面白い上に短めのコードでまとまっていて個人的には好きです！
Haskell分からないマンですが、これだけの記述でできちゃったりするんですね

KiteKite

面白そうだったのでやってみました。@ulwlu さんの方法がとても効率的なので、そちらを参考に部分和問題の部分を再帰関数で書いてみました (JavaScript) 。今回は真偽を判定するだけなので、解を見つけた時点で再帰処理を終了できます。

少し変更している部分として、先頭の数はそのまま使うルールなので、予めターゲットから引いておき、残りの数についてのみ考える。

また、正グループの総和が 0 のときはすべてが負グループということなので、その時点で真を返します。

const solve = (input, target) => {
  let solved = false;
  const [first, ...rest] = input;
  // 先頭以外の絶対値を求める
  const absRest = rest.map((v) => Math.abs(v));
  // 先頭以外の正グループの総和を計算する
  const targetOfRest = (absRest.reduce((acc, cur) => acc + cur) + target - first) / 2;

  // 正グループの総和が整数じゃない場合は解がないのでこの時点で `false` を返す
  if (!Number.isInteger(targetOfRest)) {
    return false;
  }
  // 正グループの総和が 0 の場合はすべてが負グループということなのでこの時点で `true` を返す
  if (targetOfRest === 0) {
    return true;
  }

  // 部分和を探す再帰関数、解を見つけた時点で再帰処理を終了する
  const find = (index = 0, acc = 0) => {
    for (let i = index; i < absRest.length; i++) {
      if (solved) break;
      const sum = acc + absRest[i];
      if (sum === targetOfRest) {
        solved = true;
        break;
      } else if (sum < targetOfRest) {
        find(i + 1, sum);
      }
    }
  };

  find();

  return solved;
}

console.log(solve([6, 7, 1, 4], 10)); // true
console.log(solve([1, 2, 3, 5], 10)); // false
console.log(solve([4, 7, 6, 1], 10)); // false
console.log(solve([25, -99, 44, -50, 37, -289, 54, 500], 10)); // true
nekonikinekoniki

回答ありがとうございます！
普段JSメインなので、JSに落とし込むとより分かりやすかったです！
最初に自分がサンプルで提示したものより格段に効率がよくなりましたね

nekonikinekoniki

お礼

回答いただいた皆様、ありがとうございました！
様々な回答パターンが見れてとても参考になりました！

※この投稿時点で一旦このスクラップはクローズさせていただきますが、以降も回答いただいても構いません。

このスクラップは2021/03/01にクローズされました