CodeIQ Blog

自分の実力を知りたいITエンジニア向けの、実務スキル評価サービス「CodeIQ(コードアイキュー)」の公式ブログです。

「マラソンマッチ:効率的に敵を撃滅せよ」第3回戦2013年7月30日0時30分時点暫定ランキング発表 #javascript #MarathonMatch

CodeIQ中の人、millionsmileです。

第3回戦「マラソンマッチ:効率的に敵を撃滅せよ」の暫定ランキングです。2013年7月30日0時30分時点となります。

真夏のマラソンマッチの順位はどうなったでしょうか。1位が入れ替わりましたよ。

出題者の柳井さんの解説付きで暫定ランキングの発表です。
===================================================

● 順位

 2013年7月30日、0時30分時点の順位は、以下の通りになりました。

 1位(↑前 2位/ -位)(2247点)simbelmyn 様
 2位(↓前 1位/ 1位)(2242点)sapics 様
 3位(←前 3位/ 7位)(2187点)hm001 様
 4位(↑前 8位/ 2位)(2164点)hellowd 様
 5位(↓前 4位/ -位)(2141点)simanman 様
 6位(↑前 -位/ 4位)(2083点)mad_p 様
 -位(…初 -位/ -位)(2080点)promwing 様(時間Over)
 7位(↓前 6位/ 8位)(2063点)とさ 様
 8位(↓前 5位/ 5位)(1937点)takryo 様
 9位(↓前 7位/ 3位)(1866点)ayuzak 様
10位(…初 -位/ -位)(1845点)alluser 様
10位(↓前 9位/ -位)(1845点)Azicore 様
11位(↓前10位/ 6位)(1789点)ciel 様

 前回1位だった sapics 様が今回は2位になりました。逆に、前回2位だったsimbelmyn 様が、今回は僅差で1位でした。

 トップ逆転です。sapics 様の牙城が崩されました。おめでとうございます、simbelmyn 様!

 惜しかったのは、promwing 様で、時間をオーバーしてしまいました。

 今回、期間中に、私のパソコンが壊れてしまい、修理に送られることになりました。去年の12月に買って、今回2度目。合計2か月間の修理入り。買った意味がない……。

 というわけで、少し貧弱なノートパソコンでの確認になりました。実測したところ、計算時間が1.2倍掛かっていたので、「40秒以内で終わること」という条件を1.2倍して「48秒以内」ということで判定させてもらいました。

 もしかしたら、特定の計算方法でCPUの処理時間の違いとかあるかもしれませんので、時間をオーバーしたpromwing 様(55.3秒だった)も、順位をブランクにした状態ですが、順位表に掲載いたしました。


● アルゴリズムとコード コスト

 前回は、アルゴリズムの時間コストについて触れました。今回はアルゴリズムとコード コストについて書きたいと思います。

 プログラマーの間では「簡潔なコード」は、多くの場合、推奨されます。

 同じ処理をするのに、ロジックが整理されていて、短い手順で行っていれば、それだけアルゴリズムがよいと推測できるからだと思います。

 ではそういった「簡潔なコード」を、定量的に計る方法はあるのでしょうか? 今回はそういった話をしたいと思います。

 ソースコードには、多くの場合、タブやスペースが挿入されて、読みやすく加工してあります。そして、他人や自分がコードを把握しやすいように、コメントが差し挟まれています。

 そのため、ソースコードの文字数を見ても、そのコードが「簡潔なコード」であるかどうかは判断できません。

 そこで役立つのが、JavaScriptの場合は「minify」ツール(コード圧縮ツール)と呼ばれるものです。JavaScriptのコードから、無駄な部分を省いて、コードゴルフ的に、コードを短く書き替えてくれるツールです。

 こういった「minify」ツールを使い、各人のコードを短縮すれば、ほぼ同じ条件でコードの文字数を比較可能になります。

 ただし、「for」「while」「function」など、予約語の長さがそれぞれ違うという難点はあります。

 しかし、変数などは可能な限り短い文字数に書き換えられますし、「if (~) {~}」というコードは「~&&~;」のように書き換えられますので、ほぼロジック部分の長さと考えて差支えないと思います。

 というわけで、今回は「minify」ツールとして、Googleの「Closure Compiler」を使い、各参加者のコードを短縮化して比較してみました。


 今回送られてきた各参加者の、コード コストと、その効率を計算してみました。

 まず最初に、前回と同じ「ランダムマン」という、猿のように適当に砲弾を撃つアルゴリズムを用意します。

 そのままでは「Closure Compiler」では通らないので、関数の形にします(各人のコードも同じように関数の状態にして短縮化を掛けています)。

function yourCode(arg) {
// 引数を展開
var w = arg.w;
var h = arg.h;
var rngIn = arg.rngIn;		// 爆弾降下で敵を倒せる範囲

// 砲撃位置
arg.x = rngIn + Math.floor(Math.random() * (w - rngIn * 2));
arg.y = rngIn + Math.floor(Math.random() * (h - rngIn * 2));

// 結果の配列を戻して終了
return arg;
}

 ランダムマンの成績は「862」点で、短縮した後の文字数は「137」文字でした。この値が、「アルゴリズムがまったくない」場合での、基準の点数とコード長になります。

 次に、各プログラムの点数とコード長を表にします。

名前 点数 コード長
simbelmyn 様 2247 1791
sapics 様 2242 4651
hm001 様 2187 1183
hellowd 様 2164 1350
simanman 様 2141 1401
mad_p 様 2083 7995
promwing 様 2080 2733
とさ 様 2063 1148
takryo 様 1937 2550
ayuzak 様 1866 799
alluser 様 1845 1693
Azicore 様 1845 752
ciel 様 1789 1147

 この点数とコード長から、ランダムマンの点数とコード長を引き、1文字当たりの点数を計算します。

名前 増加点数 増加文字数 point/len
simbelmyn 様 1385 1654 0.84
sapics 様 1380 4514 0.31
hm001 様 1325 1046 1.27
hellowd 様 1302 1213 1.07
simanman 様 1279 1264 1.01
mad_p 様 1221 7858 0.16
promwing 様 1218 2596 0.47
とさ 様 1201 1011 1.19
takryo 様 1075 2413 0.45
ayuzak 様 1004 662 1.52
alluser 様 983 1556 0.63
Azicore 様 983 615 1.60
ciel 様 927 1010 0.92

 この「point/len」の数値は、前回の「point/sec」と同様に、単純に大きければよいというわけではありません。なぜならば、最初は少しの改良で点数が高くなり、より高得点になれば、点数の取りこぼしがないように手数を掛けて計算を行わなければならないからです。

 この数値が意味を持つのは、ほぼ同じ順位で、「point/len」の値に大きな差が開いている場合です。ほぼ同じ点数なのに、一方の人は1文字当たり、多くの点数を稼いでいるのに、もう一方の人は、少ししか点数を稼げていない場合は、アルゴリズムの発想に違いがあることが推測できます。

 そういった場合は、アプローチを変えることで、点数を上げられる可能性があります。少なくとも、短いコードで実現できることを、遠回りな方法で実装してしまっている可能性があります。

 前回の「point/sec」や、今回の「point/len」といった値を比較することで、他人との違いが見えてくるかもしれません。また、自分のコードのログで確かめてみることで、コードの改良の軌跡が見えてくるかもしれません。


● 第4戦について

 問題は、パラメータを変えて、第4戦に突入します。

 新しいコードを送っていただいた場合は、最新のコードで順位用の判定を行います。また、そのままの場合は、以前のコードを使って、順位の判定を行います。

 というわけで、同じアルゴリズムでも、問題の環境が変わったために、順位が変動する可能性があります。

 さて、第4戦は、新しいパラメータが増えます。敵の移動の仕方に制約が加わります。そのため、これまでと敵の見た目が大きく変わっていると思います。

f:id:codeiq:20130730173152p:plain

 パラメータがどう変わっているかは、問題を見て確かめてください。

 どこが変わっているか、それがアルゴリズムにどう影響するか。そういったことを踏まえて、他人よりも効率よく敵を倒せるプログラムを投稿してください。

===================================================

いかがでしたか?
アルゴリズムとコード コストの話は面白いですね。「minify」なんぞいうツールも使ってみたいです。

まだまだマラソンは続きますよ―。マラソンといえばLSD(Long Slow Distance)。ゆっくりペースで長く走る。みなさんもやりすぎないように適度な時間でマラソンやってくださいね。
https://codeiq.jp/ace/yanai_masakazu/q378
f:id:codeiq:20130730173421j:plain

CodeIQ中の人の一言:Rubyやるとモテるとかいうのって迷信だと思わないかい?

エンジニアのための新しい転職活動!CodeIQのウチに来ない?の特集ページを見る