ともぐい、ともぐいをする。 (つまり、からあげのつまみ方とは。)

どうも、通りすがりのからあげです。

関数型プログラミングはまず考え方から理解しよう
唐揚げつまんでみた

を見て、いや、関数型という点に注目するんだったらこーかな、とゆーのを思ってしまったので、さくっと書いてみました。
みんなJavaScriptで書いてるみたいだから、私もJavaScriptで。

前提

課題：
唐揚げ弁当がいくつかあるとします。それぞれ唐揚げが複数入っています。
この中からｘ個の唐揚げをつまみ食いするプログラムを作りましょう。
つまみ食いはバレないようにするために、
その時点で最も唐揚げ数が多いお弁当から取るという仕様にします。

• データは数値配列で定義されているとする。
  • 一つの数値が弁当箱一つである。
  • 数値の大きさはその弁当箱に入っているからあげの個数である。

ざっくりとしたポイント

• しっかり抽象化をしましょう
  • (日本語の)動詞に囚われない。
    • 「選ぶ」は、それで終わりな時にしか使えない。
  • 弁当箱、別にそれぞれ区別しなくてもいいよね! ← これ一番重要
• トップダウンに、かつ 結果から 先に考える
  • n 個つまみたい。1個つまんだらどうなる。
    • ここで「つまむ」事は考えない。 つまんだら どうなる。これが先。
  • なお、ゼロは自然数です。
    • つまむ時だけ考えるからうまく抽象化できない。つままなくてもいい。

とはいえ、実際書く時は上と下を行ったり来たりしながら書くことになるので、こればっかりでは無いんですが、心構えとして。

コード

本体

karaage.js

//とりあえず名前空間ぐらいつける
var karaage = karaage || {};

// 弁当箱を、からあげが少ない順に並び替える
karaage.sortBox = arr => arr.concat().sort( (a,b) => (a<b)?-1:1 );

// boxx から、からあげを num 個つまむ。
// num=0 だったら、そのまま boxx を返却する。
// num が 1 以上だったら、1個つまんで、 さらに num-1 個つまもうとする。
karaage.pick = boxx => num =>
  num===0 ? boxx
          : karaage.pick( karaage.pickOne( boxx ) )( num-1 );

karaage.pickOne = boxx => {
  console.log(boxx + 'からいっこつまむよ'); // デバグコード

  var sortedBox = karaage.sortBox(boxx); // boxx を大きい順にソート

  // 最大の物は配列の一番最後にいるので、
  // その箱とそれ以外のものに分ける
  // 破壊操作してるけどちかたない
  var maxBox = sortedBox.pop();
  var otherBoxx = sortedBox;

  // 最大のものを一つ引いたものを、残りの箱と一緒に返す。破壊操作以下略。
  // 本当は return otherBoxx.push(maxBox-1); とか書きたいんだけど
  // こいつ配列の方返してくれないのよね。
  otherBoxx.push(maxBox-1);
  console.log('=>' + otherBoxx); // デバグコード
  return otherBoxx;
}

テストコード

tset.js

// なんとなく sinon 使ってるけど、あんまり意味が無い。
var sinonTestCase = sinon.testCase({

  /**
   * 事前処理
   */
  setUp: function () {
    jstestdriver.console.log('setUp');
    // なにもしない
  },

  /**
   * 事後処理
   */
  tearDown: function () {
    jstestdriver.console.log('tearDown');
    // なにもしない
  },

  /**
   * 以下テストケース
   */

  /**
   * ソートをしてくれるかどうか
   */
  'test sort': function () {
    jstestdriver.console.log('test sort');
    var actual = karaage.sortBox([4,2,3]);
    var expected = [2,3,4];
    assertEquals(expected, actual);
  },

  /**
   * 1個だけちゃんとつまめるかどうか
   */
  'test picOne': function () {
    jstestdriver.console.log('test pickOne');
    var actual = karaage.pickOne([4,2,3]);
    var expected = [2,3,3];
    assertEquals(expected, actual);
  },

  /**
   * 元の配列は破壊されていないかどうか。
   */
  'test immutable': function () {
    jstestdriver.console.log('test immutable');
    var boxx = [4,2,3];
    var pickedboxx = karaage.pickOne(boxx);
    // JSって変数使われないと評価されないとかあったっけ。
    jstestdriver.console.log(pickedboxx);
    var expected = [4,2,3];
    assertEquals(expected, boxx);
  },

  /**
   * 0個つまむ時は何もしないかどうか
   */
  'test picZero': function () {
    jstestdriver.console.log('test pickOne');
    var actual = karaage.pick([4,2,3])(0);
    var expected = [4,2,3];
    assertEquals(expected, actual);
  },

  /**
   * 5個ぐらいつまんでみる
   */
  'test picAny': function () {
    jstestdriver.console.log('test pickOne');
    var actual = karaage.pick([10,8,9,10,9])(5);
    var expected = [8,8,8,9,8];
    assertEquals(expected, actual);
  },

});

TestCase('karaage Test', sinonTestCase);

テスト実行結果

(前略)

Total 4 tests (Passed: 4; Fails: 0; Errors: 0) (8.00 ms)
  Chrome 50.0.2661.102 Windows: Run 4 tests (Passed: 4; Fails: 0; Errors 0) (8.00 ms)
    karaage Test.test sort passed (4.00 ms)
      [LOG] setUp
[LOG] test sort
[LOG] tearDown
    karaage Test.test picOne passed (2.00 ms)
      [LOG] setUp
[LOG] test pickOne
[LOG] 4,2,3からいっこつまむよ
[LOG] =>2,3,3
[LOG] tearDown
    karaage Test.test picZero passed (1.00 ms)
      [LOG] setUp
[LOG] test pickOne
[LOG] tearDown
    karaage Test.test picAny passed (1.00 ms)
      [LOG] setUp
[LOG] test pick5
[LOG] 10,8,9,10,9からいっこつまむよ
[LOG] =>8,9,9,10,9
[LOG] 8,9,9,10,9からいっこつまむよ
[LOG] =>8,9,9,9,9
[LOG] 8,9,9,9,9からいっこつまむよ
[LOG] =>8,9,9,9,8
[LOG] 8,9,9,9,8からいっこつまむよ
[LOG] =>8,8,9,9,8
[LOG] 8,8,9,9,8からいっこつまむよ
[LOG] =>8,8,8,9,8
[LOG] tearDown

解説

問題の分解と抽象化

「からあげをn個つまむ」 → 1個だけ? からあげのほうが少なかったら? 2個めからはどこからつまむ?
と、このままだと考えるケースがちょっと多くなってしまうのでこのように分解します。
自然数は「n」「1」「0」に置き換えしましょう。 ポイントになる考え方です。

• あなたはからあげが ｎ個ほしい
• からあげが ほしかったら 1個つまむ
• からあげが (もう)ほしくなかったら もうつままない

これで注目すべきケースは「からあげがほしいとき」と「ほしくないとき」の2つに減りました。

せっかくなので上から考えましょうか。次は からあげをつまんだらどうなるか を考えます。
ついでに思考の流れにそってインデントをととのえます。

• あなたはからあげが ｎ個ほしい
  • からあげが ほしかったら
    • 1個つまむ
    • あなたはからあげが n-1個ほしい
  • からあげが (もう)ほしくなかったら
    • もうつままない

これで再帰部分はできあがりました。入力がたりないですね。与えますか。

• お弁当箱に唐揚げが入ってる
• あなたはからあげが ｎ個ほしい
  • からあげが ほしかったら
    • 1個つまむ
    • あなたはからあげが n-1個ほしい
  • からあげが (もう)ほしくなかったら
    • もうつままない

では具体的に中の処理を考えます。「つまむ」ってなんですかね。一番多くからあげが入っているものを選ぶそうです。

• お弁当箱に唐揚げが入ってる
• あなたはからあげが ｎ個ほしい
  • からあげが ほしかったら
    • 1個つまむ
      • 一番多くからあげが入っている箱を探す
      • からあげを取る
    • あなたはからあげが n-1個ほしい
  • からあげが (もう)ほしくなかったら
    • つままない

からあげが多く入っている箱は、別にどうサーチしてもいいんですが、いちいち覚える事増やすのも面倒なのでもう並べ替えてしまいましょう。

• お弁当箱に唐揚げが入ってる
• あなたはからあげが ｎ個ほしい
  • からあげが ほしかったら
    • 1個つまむ
      • からあげが入っている箱を降順にならべる
      • 先頭の箱にからあげが沢山入ってる!ラッキー!!
      • からあげを取る
    • あなたはからあげが n-1個ほしい
  • からあげが (もう)ほしくなかったら
    • つままない

あとはこれをコードに落とすだけです。ね?簡単でしょ?