【超訳】CodeKata2：Karate Chop（ソースコード付）

photo by sean dreilinger

「TypeScript実践プログラミング」を読んで、Code Kata（http://codekata.com/）という存在を知り、早速試してみた。

ちなみにCode KataのKataは、空手や柔道の「形（Kata）」からきている。
決められた形を何度も練習することで、プログラミングの基本を覚える。そして、実践で使えるようにするのがCode Kataの目的。



見ての通り、すべて英語。しかも日本語訳サイトが少ない。

ということで、CodeKataの練習がてら翻訳した内容をまとめていく。
※ 英語は苦手なので、最低限意味が分かる程度に超訳した。


今回は、Kata02の「Karate Chop（空手チョップ）」について書いていく。

Kata02: Katate Chop

バイナリチョップ（二分探索法）は、ソートされた配列の中から目的の値の場所を見つける。

とにかく、どんな言語でも良いので二分探索ルーチンを実装してみよう。
ただし、後述する仕様に則うこと。

実装できたら、今度はまったく違うテクニックで5種類の二分探索ルーチンを実装してみよう。（例えば、良くあるループ処理や、再帰呼び出しとかいろいろ）

ゴール（目的）

このカタは、3つのゴールに分けられる。

1. いろんなアルゴリズムでコーディングすることで、ミスしたことをノートに記録しておく。二分探索法は、境界条件や植木算エラーに適している。日が経つにつれミスが減ってくる。
   
2. 自分で選んだテクニックの相対的な評価を理解してますか？プロダクションコードに適しているのはどれでしょうか？コーディングしてて楽しかったコードは？一番苦労したものは？自分で考えてみてください。
   
3. 5種類の二分探索法を考えるのは大変だったでしょう。4つ目と5つ目はどうやって思いつきましたか？

 

仕様

二分探索メソッドを実装するには、「目的の値」と「ソートされた配列」が必要。
目的の値が配列のどこにあるかを返す。見つからない場合は"-1"を返す。

chop(int, array_of_int) -> int

配列の要素数は100,000未満でOK。 性能やメモリのパフォーマンスは考えなくて良い。

テストデータ

筆者が使ったテストデータ。自由に使ってください。 ちなみに配列の添字は、ゼロ始まり。

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

実践

バイナリサーチ（二分探索法）の処理を、5通り書けというもの。
実際のソースコードは、GitHubにアップロードした。（ブログ執筆時点では2通り）

リポジトリの「commits」を見ると、私がどのようにしてバイナリサーチを実装していったかがわかると思う。

関連記事

今回は、JasmineというJavaScriptのテストフレームワークを使った。
簡単な使い方は、以下の記事にまとめてあるので参照ください。


以上

written by @bc_rikko