LoginSignup
6
6

More than 5 years have passed since last update.

@t-suwa

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

Last updated at Posted at 2016-04-28

はじめに

GW だし、Generator を学ぶために、去年流行ったプログラマ失格問題の 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 を使った最終的なバージョンはこちら。

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 のところで手間取った。左から順にオペレータを挿入しながら再帰するという素朴な実装。

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 時間。はい、失格です。

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 分。内部変数に溜め込むのが嫌な感じ。

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 ポリフィルをベースに reduceGen を書く。+5 分。

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 分。

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 分。

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 ですっきりかけた。ついでに、関数のインタフェースも直した。最初からこう書けないところが、プログラマとして非常に残念な感じ。

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 の先頭と末尾に以下のコードを足してラフに計測してみた。

console.time('total');

// 処理本体

console.timeEnd('total');

結果がこちら。

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$

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

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 に喰わせると、こんなコードを生成した。

'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(''));
});
6
6
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
6