プログラムは突然に。任意の数列から合計がXXXになる組み合わせを求めよ。

３連休の中日。

最近ハマってる料理のチキンのトマト煮カレーを食べていたら大学時代の先輩からLINEが。

「暇してたら昼飯食べん？」と。

本来なら、黒部漁港で取れた新鮮なお魚たちで、一人お魚パーティをする予定であったが、北陸地方大雪につき、魚の発送が、連休最終日の月曜日と連絡があり、どう考えても暇だったので、

即座に

「ひまなので、行きます」と返事を送った。

東京都のとある駅のドトールで待ち合わせをして、グラッチェに直行して、サラダと山盛りポテトだけ食べて、まだ暇ということで、二人で再度ドトールへ。

とある駅のドトールの３階は、喫煙席だったはずだが、時代の波か、単純に私がボケているのか、禁煙席になっていた。

先輩の課題

先輩は、決算書を作らないといけないということで、エクセルをぽちぽちしていたのだが、突然、

「この数字分からん・・」

と、

先輩のパソコンの画面には1円から75万円ほどの、22個の値が並んでいた。

すでに、その数字がなんだったか、私は覚えていない。

なのでその数字の詳細はさておき、

「その22個の数字を組み合わせて100万円になる組み合わせが知りたいとのこと」

AtCoderで無色コーダーの最低ランクの称号を持つ私は、当然目を輝かせて、

「その一覧ください」とお願いした。

武器はスマホのみ。

昼飯ということで、手ぶらで来ていたため、私の武器はスマホのみ。

この装備で闘えるのか？と頭をよぎったが、とりあえずAppStoreで「JavaScript run」で検索。

すると、こんなアプリを見つけた。

JS Code Run: JavaScript Editor

なんだか、イケそう。

ということで、なんとなく頭の中で設計して、実装

const data = [1,2,3]

let array = []

const f = (numbers, current = 0, index = 0) => {
  if (numbers.length === 0) return array.push(current)
  const end = numbers.pop()
  f(numbers, current + end)
  f(numbers, current)
}

f(data)
console.log(array)

// => [ 6, 5, 3, 0 ]

なんでやねん。と、

おそらく、根本的にJavaScriptを良く理解していないが原因な気がする。

多分、先にreturnしちゃうんだよなと、なんとなく分かるが、修正方法はわからない。

第二回戦

「先輩から、とりあえず汚くても良いから、まずは回答がでるコードを作ってみたら？」
とのアドバイスをもらい、背に腹は変えれないということで、とりあえず実装してみた。

そして、スマホが辛すぎたので、先輩のMacbookを借りて、適当にvimでjsファイルを作る。

const data = [1,2,3]

let array = []

for (let i = 0; i < 2; i++) {
    for (let j = 0; j < 2; j++) {
        for (let k = 0; k < 2; k++) {
            array.push(data[0]*i + data[1]*j + data[2]*k)
        }
    }
}

console.log(array.sort((a, b) => a - b))
// => [0, 1, 2, 3, 3, 4, 5, 6]

このforループを22個作れば、とりあえず先輩の課題は解決できる。

がしかし、無色コーダーといえど、そんな無様なことはできない。

第三回戦

先輩は夕食の時間が来てしまい、無念にもタイムアップ。

しかし、私は諦めたくない。

ということで、家に着いて、また朝食べたカレーを食べて、再挑戦。

再度考える。

問題はどう考えても非常にシンプル。

0or1の全ての組み合わせが網羅できれば、そこで勝ち確定。
というのも、数値を使う or 使わないの全網羅ができれば良いからだ。
例えば、数値が2つであれば、使わない,使わない 使わない,使う 使う,使わない 使う,使う の４パターンである

あ、bit演算。ということで私は閃いてしまった。

0or1の組み合わせを生成する関数を作ってしまえば、いいじゃないかと。

const generateBitList = (n) => {
    let array = []
    for (let i = 0; i < 1 << n; i++) {
        let bit = i.toString(2)
        while (bit.length < n) {
            bit = '0' + bit
        }
        array.push(bit)
    }
    return array
}

console.log(generateBitList(3))
// => [  '000', '001',  '010', '011',  '100', '101',  '110', '111']

完璧である。

あとは、実際に値を入れて、ループを回すだけ。

const data = [6_580, 1_598, 2_861, 52_536, 46_600, 110_075, 51_860, 600, 4_950, 150_000, 5_258, 5_588, 16_522, 2_100, 4_950, 1, 8_580, 4_598, 4_950, 1_430, 1_430, 1_430, 785_184]
const generateBitList = (n) => {
    let array = []
    for (let i = 0; i < 1 << n; i++) {
        let bit = i.toString(2)
        while (bit.length < n) {
            bit = '0' + bit
        }
        array.push(bit)
    }
    return array
}

const result = generateBitList(data.length).filter((bit) => {
    if (bit.split('').reduce((prev, cur, index) => prev + data[index] * cur, 0) === 1_000_000) {
        return bit
    }
})

console.log(result)
// => ['01100000111111111110111',  '01100000111111111111011',  '01100000111111111111101']

ということで、100万円の組み合わせになるのは、↑の3パターン

先輩に、

「できました〜〜〜〜〜〜」

と、送り、ミッション完了。

先輩の役に立てて、嬉しい1日であった。