読者です 読者をやめる 読者になる 読者になる

CodeIQ Blog

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

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

CodeIQ中の人、millionsmileです。

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

みなさん、ぐんぐんスコアを伸ばしていますね。第1回戦では1000点台でしたが、今回はついに3000点台を叩きだしたソルジャーがいらっしゃいます。

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

● 順位

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

 1位(3047点)sapics 様
 2位(2996点)simbelmyn 様
 3位(2808点)hm001 様
 4位(2750点)simanman 様
 5位(2676点)takryo 様
 6位(2672点)とさ 様
 7位(2447点)ayuzak 様
 8位(2383点)hellowd 様
 9位(2324点)Azicore 様
10位(2287点)ciel 様
11位(------)mad_p 様(特定シードで無限ループ)

 前回1位だった sapics 様が、今回もダントツで1番でした。おめでとうございます。

 惜しかったのは、mad_p 様で、特定のシードの場合に無限ループになるバグがありました。mad_p 様は、whileでループを回しており、ある条件の場合に、そのループ処理が終わらなくなっていました。

 最初、実行途中でブラウザが止まっていたので、何が起きているのだろうと思いデバッグしたら、特定の場所で無限ループになっていることが判明しました。

 私がゲームを作る際は、想定外の数値が入る可能性のある処理では、極力whileを使わないようにして、可能な限りforを使うようにしています。そして、一定回数試行したら、処理の成否に関わらずに打ち切るようにしています。ゲームは「止まったら負け」なので、そういう風にすることが多いです。


● アルゴリズムと時間コスト

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

 今回送られてきた各プログラムの、時間コストと、その効率を計算してみました。

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

// 引数を展開
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;

 ランダムマンの成績は「1160」点で、処理時間は「6.8」秒でした。この値が、「アルゴリズムがまったくない」場合での、基準の点数と時間になります。

 次に、各プログラムの点数と処理時間を表にします。mad_p 様については、無限ループになるシードを含まない場合での成績を掲載します。

名前 点数 時間
sapics 様 3047 15.4
simbelmyn 様 2996 13.1
hm001 様 2808 12.3
mad_p 様 2763 11.4
simanman 様 2750 26.4
takryo 様 2676 9.1
とさ 様 2672 27.4
ayuzak 様 2447 8.2
hellowd 様 2383 17.3
Azicore 様 2324 8.3
ciel 様 2287 10.7

 この点数と時間から、ランダムマンの点数と時間を引き、1秒当たりの点数を計算します。

名前 増加点数 増加時間 point/sec
sapics 様 1887 8.6 219.4
simbelmyn 様 1836 6.3 291.4
hm001 様 1648 5.5 299.6
mad_p 様 1603 4.6 348.5
simanman 様 1590 19.6 81.1
takryo 様 1516 2.3 659.1
とさ 様 1512 20.6 73.4
ayuzak 様 1287 1.4 919.3
hellowd 様 1223 10.5 116.5
Azicore 様 1164 1.5 776.0
ciel 様 1127 3.9 289.0

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

 この数値が意味を持つのは、ほぼ同じ順位で、「point/sec」の値に大きな差が開いている場合です。ほぼ同じ点数なのに、一方の人は1秒当たり、多くの点数を稼いでいるのに、もう一方の人は、少ししか点数を稼げていない場合は、計算量の割に、思ったような成果を挙げられていないことが推測できます。

 そういった場合は、計算方法に何らかの問題があるか、そもそものアプローチが間違っている可能性があります。少なくとも、短い処理で実現できるのと同じことを、遠回りな方法で実装してしまっている可能性があります。

 自分のプログラムが、近い順位の人に比べて極端に非効率な場合は、何らかの発想の転換をした方がよいかもしれません。また、こういった数値を自分の書いたプログラムの各バージョンで計算してみることで、アプローチの方法が正しそうか、間違っていそうかを、推測できるかもしれません。


● 第3戦について

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

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

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

 さて、第3戦は、敵の移動の仕方がこれまでとは違います。

 X方向には、1度の移動で最大40ドット移動しますが、Y方向には8ドットしか移動しません。その結果、敵の分布は横に広くなっています。

 そういった条件を踏まえて、他人よりも効率よく敵を倒せるプログラムを投稿してください。


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

さて、第3回戦スタートです。マラソンマッチやって暑い夏を乗り切りましょう。

過去の暫定ランキング
第1回戦「マラソンマッチ:効率的に敵を撃滅せよ」2013年7月15日24時時点暫定ランキング発表
http://codeiq.hatenablog.com/entry/2013/07/17/165252

https://codeiq.jp/ace/yanai_masakazu/q378
f:id:codeiq:20130724152328j:plain

CodeIQ中の人の一言:富士五湖すべて巡って来ました。

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