【Code Kata 翻訳 その2】空手チョップ！

原文はCode Kata Two - Karate Chopです。

Code Kata Two - 空手チョップ！

バイナリチョップ(要するに、二分探索法)では、順番に並んだ値の配列の中での、目的の値の位置が分かります。
値を調べる度に考慮する値の件数を半分にしていくので効率的です。
最初のステップで、目的の値は、配列の前半にあるのか後半にあたるのかが決まります。次のステップでは、先ほどの前半or後半の中の半分についてだけ考えればよく、更に前半と後半に分かれます。目的の値が見つかるか、木を全て探索し終われば手順は完了です。二分探索法はCSの中で一番好きな講義です。

このカタは明解です。あなたの好きなプログラム言語とテクニックを使って、二分探索法ルーチンを実装して下さい。ただし、後述の仕様に則って下さい。
実装できた次の日には、全く違うテクニックを使ってもう一度実装してみてください。次の日も、次の日も。。まるで異なる二分探索法の実装が5つできるまで続けて下さい。(例えば、古典的な繰り返しアプローチや、再帰処理や、配列の中を回す関数、などが考えられます)

目的
このカタは3つのゴールに分けられます。

1. それぞれのアルゴリズムをコーディングすることによって、出会った失敗の種類を記録しておくことができます。二分探索法は境界条件や植木算エラーを鍛えるのに適した問題です。日が経つにつれ、これらの失敗を起こす頻度が少なくなっていくと思います。(そしてそれは、一つのテクニックから学んだのでしょうか、それとも複数の異なるテクニックでコーディングしたからでしょうか？)


2. あなたが選択したテクニックの優劣について分かっていますか？本番用のコーディングに最も適しているのはどれでしょうか？書いていて一番面白かったコードはどれでしょうか？プログラムを動かすのに一番苦労したのは？そして、これらの問いについて、「なぜそうなのか」を考えて見てください。


3. 5つもの二分探索法のアプローチを考えるのはかなりきつかったでしょう。4つ目と5つ目のアプローチはどのようにして考え付きましたか？突飛なニューロン脳細胞を発火させるために、どんなテクニックを使いましたか？

二分探索法の仕様
二分探索法のメソッドを記述するのには「目的の値」と「ソート済みの整数の配列」の2つが必要です。このメソッドは目的の値が配列の何番目に位置するかの整数(ゼロベース)を返します。が、目的の値が配列の中になかった場合には「-1」を返却します。論理的にこんな感じで記述できるでしょう。

chop(int, array_of_int) -> int

配列の要素数は100,000未満でよいコトとします。このカタでは、処理速度やメモリのパフォーマンスについては考慮しません。十分なRAMで十分な速度でアルゴリズムが動いているというコトにしておいてください。

コードカタの筆者が実装するときに使用したテストコードです。自由にケースを追加してくれていいです。このテストでは、配列の添え字が0から始まることを担保しています。このテストケースをあなたの選択した言語に合う形にするには、グローバル検索とグローバル置換が何回か必要になると思います(たまたまRubyを選択していたら、その限りではないですが)

def test_chop
assert_equal(-1, chop(3, []))
assert_equal(-1, chop(3, [1]))
assert_equal(0,  chop(1, [1]))
#
assert_equal(0,  chop(1, [1, 3, 5]))
assert_equal(1,  chop(3, [1, 3, 5]))
assert_equal(2,  chop(5, [1, 3, 5]))
assert_equal(-1, chop(0, [1, 3, 5]))
assert_equal(-1, chop(2, [1, 3, 5]))
assert_equal(-1, chop(4, [1, 3, 5]))
assert_equal(-1, chop(6, [1, 3, 5]))
#
assert_equal(0,  chop(1, [1, 3, 5, 7]))
assert_equal(1,  chop(3, [1, 3, 5, 7]))
assert_equal(2,  chop(5, [1, 3, 5, 7]))
assert_equal(3,  chop(7, [1, 3, 5, 7]))
assert_equal(-1, chop(0, [1, 3, 5, 7]))
assert_equal(-1, chop(2, [1, 3, 5, 7]))
assert_equal(-1, chop(4, [1, 3, 5, 7]))
assert_equal(-1, chop(6, [1, 3, 5, 7]))
assert_equal(-1, chop(8, [1, 3, 5, 7]))
end

【Code Kata 翻訳 その1】スーパーマーケットの価格設定

Code Kataの翻訳をして行こうと思います

前の記事で紹介したCode Kataですが、(勿論)英語で書かれています。やってみようにも問題が分からずやる気を削がれるので、まずは翻訳してみようと思い立ちました。
1つの記事で、1つのKataを翻訳していきます。

間違いがあったらご指摘ください

久しぶりの翻訳なので、認識違いがあるかもしれません。
ご指摘よろしくお願いいたします。

それでは、「壱の型」を翻訳します。

Code Kata One - スーパーマーケットの価格設定

原文はCode Kata One - Supermarket Pricingです。

この型はDFW Practioners(注 これかな?)のミーティングでの ある議論の中で出てきました。スーパーマーケットの商品に価格を設定すること…一見単純そうに見える問題です。
スーパーマーケットにあるいくつかの商品は単純な価格設定がされています。例えば豆なら0.65ドル、などです。しかし、複雑な価格設定の商品もあります。例えば…

• 3つで1ドル。(では、4つや5つ買った場合はどうなる？)
• 1ポンドで1.99ドル。(では、4オンス分(= 1/4ポンド分)買ったらどうなる？)
• 2つ買うと1つはタダになる(では、3つ買ったらどうなる？)

この型ではコーディングは必要ありません。この練習問題の目的は、お金と価格を表す様々なモデルについて試行することです。このモデルはこれらの(そして他の)価格体系を扱うのに十分柔軟な形です。また同時に、一般的によく使われています(精算時、在庫管理時、受注時、などなど)

以下の事柄について考えてみてください。

• 端数のお金は存在するのか？
• (やるとするならば)いつ価格の丸め込みをするのか？
• どのようにすれば価格決定の監査証跡を保持できるのか？(そもそも保持する必要があるのか？)
• コストと価格は同じものか？
• ある棚に100個の缶詰があり、それらが「2つ買えば1つタダ」という価格設定ならば、どのようにして在庫を評価するのか？

この型は小さい型ですが、注意が必要です。いくつかの問題は思ったよりも複雑です。主な選択肢を検討するのに2,3週間くらいはかけてもいいかもしれません。

目的
この型の目的は、モデル化の試行をゆるい形で練習することにあります。価格設定のパターンをできるだけたくさん探してください。そして、それぞれの長所と短所について考えてみてください。また、これらのモデルを検討するのに最良のテクニックはなんでしょうか？それらのモデルを記録・保持するのに最良のテクニックは？どうすればそのモデルが合理的であることを確認できますか？