今更：1 時間以内に解けなければプログラマ失格問題 5 を Generator を使って解いてみた

# はじめに

GW だし、Generator を学ぶために、[去年流行ったプログラマ失格問題](https://www.shiftedup.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour)の 5 をやってみた。

> Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

再帰とか高階関数と Generator の相性ってどうなんだろうね、という素朴な疑問が出発点。

結果、完全にプログラマ失格です :scream: 

# UPDATE@2016-05-07: 末尾再帰バージョン

計算部分を末尾再帰にできないかといじっていたら、盛大なバグを発見 :scream:
ひとまず、Generator を使った最終的なバージョンはこちら。

```js
const calc = (exp) => {
  const calcInner = (exp, tmp, sum = 0) => {
    if (exp.length === 0) return sum + tmp;

    const op = exp[0];
    const val = exp[1];
    const rest = exp.slice(2);

    if (op === '+') return calcInner(rest, +val, sum + tmp);
    if (op === '-') return calcInner(rest, -val, sum + tmp);

    const sign = (tmp > 0) ? 1 : -1;

    return calcInner(rest, tmp * 10 + sign * val, sum);
  };

  return calcInner(exp.slice(1), exp[0]);
};

const gen = function* (src, acc = []) {
  if (src.length === 1) {
    yield acc.concat(src);
    return;
  }

  for (let op of ['+', '-', '']) {
    yield* gen(src.slice(1), acc.concat(src[0], op));
  }
};

const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9];

console.time('total');

[...gen(numbers)]
  .filter(exp => calc(exp) === 100)
  .forEach(exp => console.log(exp.join('')));

console.timeEnd('total');
```

というわけで、**以降の内容は全てバグありバージョン**となっています。コードを修正してしまうと記録の意味がなくなってしまうので、恥を忍んでオリジナルのまま残しておきます。コードを追ってバグを探してみるのも一興かもしれません :sob: 

# 最初のバージョン

まずは簡単なやり方で、`eval` と `console.log` を使って 40 分くらい。`reduce` のところで手間取った。左から順にオペレータを挿入しながら再帰するという素朴な実装。

```js:v1.js
const solve = (acc, src) => {
  if (src.length === 1) {
    const exp = acc.concat(src).join('');
    if (eval(exp) === 100) {
      console.log(exp);
    }
    return;
  }

  for (let op of ['+', '-', '']) {
    src.reduce((prev, curr, index) => {
      solve(acc.concat(prev, op), src.slice(index));
      return [].concat(prev, op, curr);
    });
  }
};

const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9];

solve([], numbers);
```

# `eval` 使わないバージョン

`eval` はさすがに安直すぎるかなと思い、自前計算してみた。最初はウンウン唸って大変だったけど、再帰で道が開けた。+20 分くらい。しかしこの時点で早くも 1 時間。はい、失格です。

```js:v2.js
const calc = (sum, exp) => {
  if (exp.length === 0) return sum;

  const op = exp.shift();
  const val = exp.shift();

  if (op === '+') return sum + calc(val, exp);
  if (op === '-') return sum - calc(val, exp);

  return calc(sum * 10 + val, exp);
};

const solve = (acc, src) => {
  if (src.length === 1) {
    const exp = acc.concat(src);
    if (calc(exp[0], exp.slice(1)) === 100) {
      console.log(exp.join(''));
    }
    return;
  }

  for (let op of ['+', '-', '']) {
    src.reduce((prev, curr, index) => {
      solve(acc.concat(prev, op), src.slice(index));
      return [].concat(prev, op, curr);
    });
  }
};

const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9];

solve([], numbers);
```

# `console.log` 使わないバージョン

`console.log` の代わりにきちんと値を返す。+5 分。内部変数に溜め込むのが嫌な感じ。

```js:v3.js
const calc = (sum, exp) => {
  if (exp.length === 0) return sum;

  const op = exp.shift();
  const val = exp.shift();

  if (op === '+') return sum + calc(val, exp);
  if (op === '-') return sum - calc(val, exp);

  return calc(sum * 10 + val, exp);
};

const solve = (acc, src) => {
  let result = [];

  if (src.length === 1) {
    const exp = acc.concat(src);
    if (calc(exp[0], exp.slice(1)) === 100) {
      result.push(exp.join(''));
    }
  } else {
    for (let op of ['+', '-', '']) {
      src.reduce((prev, curr, index) => {
        const tmp = solve(acc.concat(prev, op), src.slice(index));
        result = result.concat(tmp);
        return [].concat(prev, op, curr);
      });
    }
  }

  return result;
};

const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9];

for (let exp of solve([], numbers)) {
  console.log(exp);
}
```

# 内部変数をなくすべく、Generator を使ってみる

標準の高階関数は Generator をサポートしていないので、まずは対応版を用意する。[MDN の `reduce` ポリフィル](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce#Compatibility)をベースに `reduceGen` を書く。+5 分。

```js:reduceGen.js
Object.defineProperty(Array.prototype, 'reduceGen', {
  value: function* (callback) {
    if (this === null || this === undefined) throw new TypeError("Object is null or undefined");

    let i = 0;
    let l = this.length >> 0;
    let curr;

    if (typeof callback !== "function") throw new TypeError("First argument is not callable");

    if (arguments.length < 2) {
      if (l === 0) throw new TypeError("Array length is 0 and no second argument");
      curr = this[0];
      i = 1; // start accumulating at the second element
    }
    else
      curr = arguments[1];

    while (i < l) {
      if (i in this) curr = yield* callback(curr, this[i], i, this);
      ++i;
    }

    return curr;
  }
});
```

これを使って、全体を書き直してみる。+10 分。

```js:v4.js
import {} from './reduceGen';

const calc = (sum, exp) => {
  if (exp.length === 0) return sum;

  const op = exp.shift();
  const val = exp.shift();

  if (op === '+') return sum + calc(val, exp);
  if (op === '-') return sum - calc(val, exp);

  return calc(sum * 10 + val, exp);
};

const solve = function* (acc, src) {
  if (src.length === 1) {
    const exp = acc.concat(src);
    if (calc(exp[0], exp.slice(1)) === 100) {
      yield exp;
    }
    return;
  }

  for (let op of ['+', '-', '']) {
    yield* src.reduceGen(function* (prev, curr, index) {
      yield* solve(acc.concat(prev, op), src.slice(index));
      return [].concat(prev, op, curr);
    });
  }
};

const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9];

for (let exp of solve([], numbers)) {
  console.log(exp.join(''));
}
```

おお、なんとか完成した。しかし、あまり Generator っぽい感じが出ていない。なぜだ。。。

# UPDATE: 責務を分離してすっきりさせる

昼飯を食べた後にふと、「計算可能な配列」だけをひたすら返してくれる Generator があれば直感的になるのではないかと思い直し、やってみた。+5 分。

```js:v5.js
import {} from './reduceGen';

const calc = (sum, exp) => {
  if (exp.length === 0) return sum;

  const op = exp.shift();
  const val = exp.shift();

  if (op === '+') return sum + calc(val, exp);
  if (op === '-') return sum - calc(val, exp);

  return calc(sum * 10 + val, exp);
};

const gen = function* (acc, src) {
  if (src.length === 1) {
    yield acc.concat(src);
    return;
  }

  for (let op of ['+', '-', '']) {
    yield* src.reduceGen(function* (prev, curr, index) {
      yield* gen(acc.concat(prev, op), src.slice(index));
      return [].concat(prev, op, curr);
    });
  }
};

const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9];

[...gen([], numbers)]
  .filter(exp => calc(exp[0], exp.slice(1)) === 100)
  .forEach(exp => console.log(exp.join('')));
```

なるほど。こう書けると見通しが良いし、再利用性も高まり、結果としてテストもしやすくなる。これはこれでありな気がしてきた。遅いけど。

# UPDATE@2016-05-01: 高階関数使わないバージョン

一晩寝て起きて、計算可能な配列がダブってるのはそもそもおかしいと思い、点検したら高階関数が不要だった。そのおかげで、Generator ですっきりかけた。ついでに、関数のインタフェースも直した。最初からこう書けないところが、プログラマとして非常に残念な感じ。

```js:v6.js
const calc = (exp) => {
  const calcInner = (sum, exp) => {
    if (exp.length === 0) return sum;

    const op = exp[0];
    const val = exp[1];
    const rest = exp.slice(2);

    if (op === '+') return sum + calcInner(val, rest);
    if (op === '-') return sum - calcInner(val, rest);

    return calcInner(sum * 10 + val, rest);
  };

  return calcInner(exp[0], exp.slice(1));
};

const gen = function* (src, acc = []) {
  if (src.length === 1) {
    yield acc.concat(src);
    return;
  }

  for (let op of ['+', '-', '']) {
    yield* gen(src.slice(1), acc.concat(src[0], op));
  }
};

const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9];

[...gen(numbers)]
  .filter(exp => calc(exp) === 100)
  .forEach(exp => console.log(exp.join('')));
```

# パフォーマンス測定

v6.js の先頭と末尾に以下のコードを足してラフに計測してみた。

```js
console.time('total');

// 処理本体

console.timeEnd('total');
```

結果がこちら。

```sh
orange:es6 t.suwa$ node -v
v6.0.0
orange:es6 t.suwa$ node v6.js
1+2+3-4-5+6+78+9
1+2+34-5-67-8-9
1+23-4-5+6+78-9
1+23-4-56+7+8+9
12+3+4+5-6+7-89
12+3-4-5+67+8+9
12-3+4-5-6-7+89
123+4-5-67-89
123+45-67-8-9
123-4+5+6+7-8-9
123-45+67-89
total: 92.935ms
orange:es6 t.suwa$ for a in {1..10}; do node v6.js; done|awk '/total/ { print }'
total: 97.466ms
total: 92.567ms
total: 97.987ms
total: 91.589ms
total: 93.228ms
total: 93.102ms
total: 93.283ms
total: 97.761ms
total: 98.860ms
total: 96.923ms
orange:es6 t.suwa$ for a in {1..10}; do node v6.js; done|awk '/total/ { sum += $2; count += 1 } END { print sum / count }'
97.1889
orange:es6 t.suwa$ 
```

ロジックはそのままで、内部変数を使ったバージョンはこちら。

```sh
orange:es6 t.suwa$ for a in {1..10}; do node v6-buffer.js; done|awk '/total/ { print }'
total: 57.161ms
total: 56.873ms
total: 58.543ms
total: 57.483ms
total: 57.599ms
total: 57.794ms
total: 57.284ms
total: 56.833ms
total: 58.584ms
total: 57.959ms
orange:es6 t.suwa$ for a in {1..10}; do node v6-buffer.js; done|awk '/total/ { sum += $2; count += 1 } END { print sum / count }'
58.7878
orange:es6 t.suwa$ 
```

今回のケースでは、Generator を使うとざっくり 1.6 倍くらい遅くなる。これだと、現時点では使う場面が限られてくると思う。

# 感想

~~Generator を使うとすっきり書けるかなと思ったが、案外そうでもなかった。とにもかくにも、高階関数が軒並み使えないため、いちいち Generator 対応版を用意しなければならないのが痛い。また、そうまでして書いたコードを眺めて見ても、心地良さを感じることはない。無駄に難しい感じになってしまっている。~~

Generator をうまく使うと、関数の再利用性を高めることができる。ただし、そのためにはお膳立てとして追加のコーディングを強いられることがあるので、その辺りのコストの見極めは慎重にしたい。また、書きっぷりの便利さに惑わされず、他の手段で実装できる場合には、性能比較をした上で使うかどうかを決めるようにすべきかなと。当たり前ですけど。

ちなみに、v6.js を Babel に喰わせると、こんなコードを生成した。

```js
'use strict';

function _toConsumableArray(arr) { if (Array.isArray(arr)) { for (var i = 0, arr2 = Array(arr.length); i < arr.length; i++) { arr2[i] = arr[i]; } return arr2; } else { return Array.from(arr); } }

var calc = function calc(exp) {
  var calcInner = function calcInner(sum, exp) {
    if (exp.length === 0) return sum;

    var op = exp[0];
    var val = exp[1];

    if (op === '+') return sum + calcInner(val, exp.slice(2));
    if (op === '-') return sum - calcInner(val, exp.slice(2));

    return calcInner(sum * 10 + val, exp.slice(2));
  };

  return calcInner(exp[0], exp.slice(1));
};

var gen = regeneratorRuntime.mark(function gen(src) {
  var acc = arguments.length <= 1 || arguments[1] === undefined ? [] : arguments[1];

  var _arr, _i, op;

  return regeneratorRuntime.wrap(function gen$(_context) {
    while (1) {
      switch (_context.prev = _context.next) {
        case 0:
          if (!(src.length === 1)) {
            _context.next = 4;
            break;
          }

          _context.next = 3;
          return acc.concat(src);

        case 3:
          return _context.abrupt('return');

        case 4:
          _arr = ['+', '-', ''];
          _i = 0;

        case 6:
          if (!(_i < _arr.length)) {
            _context.next = 12;
            break;
          }

          op = _arr[_i];
          return _context.delegateYield(gen(src.slice(1), acc.concat(src[0], op)), 't0', 9);

        case 9:
          _i++;
          _context.next = 6;
          break;

        case 12:
        case 'end':
          return _context.stop();
      }
    }
  }, gen, this);
});

var numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9];

[].concat(_toConsumableArray(gen(numbers))).filter(function (exp) {
  return calc(exp) === 100;
}).forEach(function (exp) {
  return console.log(exp.join(''));
});
```