【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

【CSS】display属性について

display属性の継承について

仕事で詰まったので調査をします。

displayプロパティ(しらぎくさいと)を見ると、display属性は下位の要素には継承されないらしい
以下、引用。

displayプロパティは、上位要素から継承されません。

ここで疑問。

1. 最初にページが描画されたときは継承しないのか
2. JavaScriptで動的にdisplay属性を操作したとき、その子要素はどうなるのか

この辺りを調査します。

長文なので結論から書きます

結論。

1. 最初にページが描画されたときは継承しない
2. JavaScriptで動的にdisplay属性を操作したとき、その子要素のdisplay属性には影響はない

サンプルコードはこんな感じのを使用します

HTML(サンプル1とする)

<a href="#" id="a">
 <img id="img" src="http://example.com/example.jpg"/>
</a>

aタグ、imgタグのdisplayをちょこちょこ修正して調査していきます。

描画時点のaタグ、imgタグのdisplay属性の値は、以下のようなJavaScriptで調べます。

alert("aタグのdisplay属性の値:" + $("a").style.display);
alert("imgタグのdisplay属性の値:" + $("img").style.display);

function $(id){
 return document.getElementById(id);
}

最初にページが描画されたときは継承しないのか

【まずはサンプル1で検証】
予想。

• aタグはインライン要素なので、描画された時点では display:inline; となっているハズ
• imgタグもインライン要素なので、描画された時点では display:inline; となっているハズ

結果。

	aタグのdisplay属性の値	imgタグのdisplay属性の値
IE7	値なし	値なし
Firefox 3.6.8	値なし	値なし
Google Chrome 8.0	値なし	値なし
Opera 11.00	値なし	値なし

予想外。
display属性の値は明示的にセットしないと、JavaSriptでは何も取得できないようです。

【aタグをdisplay:block;とするとどうなるのか】
HTML(サンプル2とする)

<a href="#" id="a" style="display:block;">
 <img id="img" src="http://example.com/example.jpg"/>
</a>

予想。

• aタグは、描画された時点では display:block; となっているハズ
• imgタグは、描画された時点では display:値なし となっているハズ

結果。
予想通り。

aタグをdisplay:none;としても、上記と同様の結果になりました。

JavaScriptでdisplay属性を操作したとき、その子要素はどうなるのか

aタグのdisplay属性をJavaScriptで操作したあと、imgタグのdisplay属性を確認します。

【HTMLサンプル1で検証】
以下のJavaScriptを使用します。

//aタグのdisplay属性をblockにしてからimgタグのdisplay属性を確認
$("a").style.display = "block";  

alert("imgタグのdisplay属性の値:" + $("img").style.display);

function $(id){
 return document.getElementById(id);
}

予想。

• 上位のdisplay属性は継承されないので、imgタグのdisplay属性は 値なし となる

結果。
予想通り。

aタグのdisplay属性をnoneに変更しても、結果は同じでした。

結論

1. 最初にページが描画されたときは継承しない
2. JavaScriptで動的にdisplay属性を操作したとき、その子要素のdisplay属性には影響はない

ただここでもう一つ疑問が。
HTMLサンプル3

<a href="#" id="a" style="display:none;">  <!-- display:none; -->
 <img id="img" style="display:block;" src="http://example.com/example.jpg"/>  <!-- display:block なのでこれは表示されて欲しい -->
</a>

としたときに、imgタグの画像が表示されて欲しいのに、表示されない。

またもっと見て行きます。

HTML5で作られた画像編集サービス

ざっと検索したら出てきました。

1. Aviary (Tech Crunchの紹介文)
2. Cloud Canvas (Tech Crunchの紹介文)
3. Dark Room

Flashもびっくりのリッチなインターフェースみたい。
FlexとかSilverlightはどうなるのかなあ。
JavaScript使ったサービスが多くなってゆるやかに衰退していくのかな。

【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週間くらいはかけてもいいかもしれません。

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

コーディングの練習のために その1

書籍を読んでいたら、役に立ちそうなサイトが書いてありました

情熱プログラマー-ソフトウェア開発者の幸せな生き方という本を読んでいたら、役に立ちそうなサイトが書いてありました。

1. TopCoder
2. Code Kata

以下、ほぼ書籍の丸写しですが、概要です。

TopCoder

プログラミングコンテストのサイトで、参加者登録をするとプログラミングコンテストに参加できる。
また、多数の練習問題も用意されている。

Code Kata

Kata…武道の「型」。
プログラミングの具体的なプロセスや思考プロセスについての、21通りのKataが用意されている。