あいつの日誌β

人生はお酒があれば何とかなります。 drunkard.tokyo

Youtube で MIT OpenCourseWare でやっている Programming for the Puzzled が面白い

あらすじ

そろそろ英語の勉強しないといけないのでとりあえず Youtube で英語に慣れよう、エンジニアだしMITの動画でも見てみようかな。と思って見たらえらい面白かったので講義の内容をなんとなくブログにします。

www.youtube.com

問題: coin row game

コインを集めるゲームが題材です。例えば以下のようにコインが並んでいるとすると全部集めるといくらになるでしょうか?

[14, 3, 27, 4, 5, 15, 1]

答えは以下の通りです。

const _ = require('lodash');
const result = _.sum([14, 3, 27, 4, 5, 15, 1]);
console.log(result); // 69

はえいこれではゲームにならないので制約を加えます。拾ったコインのすぐ次のコインは拾えない です。この制約下においてもっとも大きな値となるようにコインを集める関数を考える、というゲームです。

coins([14, 3, 27, 4, 5, 15, 1]) // 14 + 27 + 15 = 56
coins([14, 3, 27, 4, 5, 15, 11]) // 14 + 27 + 5 + 11 = 57

動画では考え方と解法が解説されています。言語は Python ですが私は Node.js で書いています。

サブセットを用意する

サブセットという概念を説明します。たとえば [1, 2] からは 2の2乗のサブセットが作成できます。

[1, 2] => {}, {1}, {2}, {1, 2}

[1, 2, 3] からだと2の3乗のサブセットができます。コードで説明したほうが分かりやすいので以下をご覧ください。

function getSubsets(items) {
  var subset = [];
  helper(items, subset, 0);
}

function helper(items, subset, i) {
  // n 番目の階層に到着したら標準出力
  if (items.length === i) {
    console.log(subset);
  }
  // 分岐が 
  else {
    // empty の場合
    subset[i] = null;
    helper(items, subset, i + 1);

    // 数値を代入する場合
    subset[i] = items[i];
    helper(items, subset, i + 1);
  }
}

getSubsets([1, 2, 3])

上記を実行すると以下のようになります。これを見ればコインを拾ったか、スキップしたかがわかると思います。

[ null, null, null ]
[ null, null, 3 ]
[ null, 2, null ]
[ null, 2, 3 ]
[ 1, null, null ]
[ 1, null, 3 ]
[ 1, 2, null ]
[ 1, 2, 3 ]

Pick or Skip

この coin row game で実行できる事は基本的に Pick するか、 Skip するかの2つしかありません。これを 0 と 1 で表現します。

Skip: 0
Pick: 1

Pick or Skip を2進数で表現すると以下のようにすることができます。

0000
0001
0101
1111

さて、先頭の数字から順番に処理する際に、基本的に以下の選択肢があります。

  • 直前のコインを Pick している場合 => Skip only
  • 直前のコインを Pick していない場合 => Pick or Skip

上記の条件を考えると先ほど2進数で表現した Pick or Skip では制約に違反しているものがあります。一番下の 1111 です。

という事で並んだコインを Pick or Skip したサブセットを全て取得して、制約に違反していないサブセットから拾ったコインの合計値を求めると問題を解決できそうです。 このロジックでも問題は解決できますが、コインの数が増えれば増えるほど分岐する tree が深くなっていきます。ネズミ算式に増えるイメージです。

もしコインが 50 個並んでいたらサブセットの数は以下の通りです。

> 2 ** 50
1125899906842624

必要なサブセットだけを取得する

今回のゲームは コインを Pick した後は必ずスキップ する必要がありますので取得しなくても良いサブセットが存在します。

ということでこれを踏まえてサブセットを取得する方法を考えます。

完成

いわゆる再帰呼び出しを使って以下のように書けます。

function coins(row, table) {

  // no coins
  if (row.length == 0) {
    table[0] = 0;
    return {result: 0, table}
  // one coin
  } else if (row.length == 1) {
    table[1] = row[0];
    return {result: row[0], table};
  }

  // pick the coin, and skip next coin -> slice(2)
  const pick = row[0] + coins(row.slice(2), table).result

  // skip the coin -> slice(1)
  const skip = coins(row.slice(1), table).result;

  const result = _.max([pick, skip]);
  table[row.length] = result;

  return { result, table };
}

const coinRow = [14, 3, 27, 4, 5, 15, 1];
const {result, table} = coins(coinRow, {});

console.log({result, table});

結果は以下の通り。result が求めている答えです。

{ 
  result: 56,
  table: { '0': 0,
     '1': 1,
     '2': 15,
     '3': 15,
     '4': 19,
     '5': 42,
     '6': 42,
     '7': 56 
  } 
}

動画では traceback する関数を用意して table を解析しています。興味がある方は動画をご覧ください。

まとめ

MIT の動画はとても面白いのでおすすめです。