Entry

プログラミングメモ - プログラミング基礎体力テスト

2008年08月26日

ちょっと前に周りの人にやってもらった実装関連の基礎体力テストをご紹介します。

基礎体力というのは,定番アルゴリズムや実装テクニックをすぐに引き出しから取り出して,不具合なく一発で実装できる能力です。特異な処理を実行するプログラムでも,特異なアルゴリズムそのものが使われる場所ってのは,プログラム全体の中でもかなり少なかったりします(全部特殊な処理をしているプログラムももちろんあるけれど)。大抵のプログラムでは,よくあるアルゴリズムやテクニックが大半を占めていたりする。

で,おそらく,実装の効率ってのは,そういった軽い処理をどれだけ卒なくこなせるか,にかかってると思うんですね。そういう処理を,ウンウンうなってやっとこさ作る,とか,コンパイルエラーを出しまくって作ってるようじゃ,結果は同じでも困りもんです。肝心な「特異な処理」に割くべきリソース(時間とか考える労力とか)を,つまらない処理に回してしまうことになるからです。

ということで,軽めの処理をどこまで一発(コンパイルエラーなし,バグなし)で実装できるか,試してもらったというわけです。

言語はC言語を想定しています。他の言語にも対応しようと思ったんですけど,難易度が均一にならなかったので(簡単になりすぎたり難しくなりすぎたりする),今回はC言語だけ。

ルールは次の通り。

  1. レベルは0から8まであります。
  2. 30分以内で実装してください。30分を過ぎたら終了です。
  3. 問題文の意味に疑問を持たないでください。言っていることが分からない場合は終了です。
  4. コンパイルは一発で通してください。コンパイルが通らなかったら終了です。コンパイルする前に見直しを忘れずにしましょう。
  5. 使っていいライブラリは ANSI C の標準ライブラリだけです。
  6. level 0 を除き,任意のレベルの問題に着手するには,それより下のレベルの問題を全てクリアしている必要があります。level 0 の問題には誰でも着手できます。
  7. 問題文所定の動作が実行されなければ終了です。

ただし,以下のことに配慮する必要はありません。

  1. 30分以内で実装できればいいので,30分以内であれば,どれも同じくらいに「できる」と思っていただいて結構です。むやみに速さを競う必要はありません。
  2. コードの長さもむやみに短く(あるいは長く)する必要はありません。長くても100ステップ程度で作れるお題を出しているつもりです。
  3. 特異な実装テクニックを競うわけではないので,普通の処理を普通に書いてください。できれば他の人が読んでも分かりやすいように(これが難しいんだけど)。

ではお題です。

level 0:

文字列"Hello, world"を標準出力に出力させてください。

level 1:

1から1000000までの和を計算し、その答えを標準出力に出力させてください(※「計算」すること)。

level 2:

文字列"You Are My Sunshine"の小文字と大文字を入れ替えた文字列を作り、標準出力に出力させてください。結果の文字列は一旦メモリ上に置いてください(読みながら表示してはいけないということ)。元の文字列を壊してもかまいません。

level 3:

標準入力から文字列を読み取り,先頭に行番号をつけて標準出力に出力させてください。行末は'\n'またはEOF。入力される文字は ASCII 文字のみとします。行番号のフォーマットは"00001: "(0詰め5桁の後にコロンとスペース)とします。

level 4:

strlcpy(3) を実装してください。strlcpy(3) の仕様については man 等を参照してもかまいません。仕様調査の時間は実装時間(30分以内)に含めません。BSD 系の Unix を使ってる方は strlcpy(3) を使わないこと!

level 5:

任意の Windows BMP ファイルのヘッダ情報(BITMAPINFOHEADER)から、画像の幅(biWidth)と高さ(biHeight)を取得する関数を実装してください。ビットマップファイルの仕様については適宜調査してもかまいません。仕様調査の時間は実装時間(30分以内)に含めません。

level 6:

適当な片方向線形リストの要素を定義して、5個の要素を追加した後、全ての要素を削除してください。

level 7:

大きさ10のint型配列があり,各要素に任意の値が設定されています。これを昇順にソートしてください。なお,アルゴリズムは任意ですが,ここでは qsort(3) を使用しないでください(意味がなくなるから)。その他の標準ライブラリは使用してかまいません。

level 8:

改行とカンマを含まない ASCII 文字のみの文字列を,空白(スペース)で分割し,CSV 形式の文字列を返す関数を実装してください。連続する空白は1つの空白と同じように扱います。また,文字列末尾の空白は無視します(空フィールドが最後にできるわけではない)。1フィールドの最大長も入力文字列全体の長さも無制限とします。

level 1 や level 2 あたりは,プログラム中でそのまま使うようなことはないんだと思います。いわゆる教室問題ですね。けど,添字を使った処理とか,文字列を1文字ずつ処理することを問題のテーマにすると,こんな感じになるんだと思います。その他は,どれも,じっくり考える時間があればできるのに……ってなもんだと思います。

あたしの周りでは,level 7 が最高点でした。level 8 は時間切れで終了……。その後20分くらいかけて level 8 をクリアしていた人はいました。バリバリ実装できる人も,意外とつまらないところでコンパイルエラーを食らっちゃったりして,ゲームオーバーになってる人もいました(これがいちばんつらい)。

レベルの高い問題でも得意な分野ではちゃっちゃか実装しちゃう人もいたので(ソートとか),分野によって,割と得意不得意が出るみたいですね。

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN