Sailing - Rules 日本語訳

Arrow_down  サンプルコードをダウンロードする

「Compressive Sensing」が第2回 MATLAB オンライン・プログラミング・コンテストです。

課題

ヨットでの長い航海の末に、いよいよ帰航する時が来ました。母港への帰路を調べるために慣れ親しんだ海図に手を伸ばします。海図は、以下に図示すように、現在位置 (A点) 、目的地 (B点)、および風の状況を示します。ヨットにはモーターがありますが、多少遠回りになっても、なるべく風を可能な限り利用したいものです。

詳細

この長方形の海域でA点からB点へ航行する必要があります。それには、速度をうまく調整することになります。初期速度はゼロですが、ターンごとに限定的な任意の加速(モーター)を横あるいは縦方向の速度に適用できます。さらに、行列内の個々のマスにもそれぞれ速度に加算される固有の加速(風)があります。移動には摩擦がないものとし、一旦動き始めるたら減速するには逆風を受けるかモーターを使うしかありません。

なるべく全てを単純で行列で処理できるようにするため、全ての計算は行および列を使って表記します。「行速度」-1は、従ってヨットが位置する行を一つ移動します(行のインデックスを1減らします)。ヨットが風の吹いているマスに移動するたびに風の加速値が現在速度に加算されます。この例では行の風(row winds)および列の風(column winds)は以下のように二つの行列で表すことができます。

row winds    = [  .  . -1  .  .  . ]
               [  .  .  .  . -1  . ]
               [  .  .  .  . -1  . ]
               [  .  .  1  . -2  . ]
               [  .  1  .  .  .  . ]
               [  . -1  .  .  .  . ]

column winds = [  .  .  .  .  .  . ]
               [  .  .  .  .  .  . ]
               [  1  2  .  .  .  . ]
               [  .  .  . -2  .  . ]
               [  .  .  .  .  .  . ]
               [  .  .  .  .  .  . ]

コンテストの目的は、A点からB点への航行の際に、以下を最小化することにあります。

  1. B点への最終距離
  2. 最終的な移動速度
  3. モーターの総合使用量
モーターはターンごとに限定的に速度の調整に使用することができます。制限は「最大スロットル」(maxThrottle)として表現されます。最大スロットルが3なら、行あるは列の速度(あるいはその任意の組み合わせ)を合計で3まで変更できます。速度入力は整数単位および上下左右方向にに量子化されます。よってmaxThrottleが3なら以下が有効なモーター入力となります:

 change in row velocity   change in column velocity
          3                         0
          2                        -1
          1                         1
          0                        -3
          0                         0

利用可能なモーター入力以上を要求すると、そのターンではモーターが使用不可能となり、モーター入力がゼロとなります。それでも要求した数値はそのまま得点に加算されますのでご注意ください。

ターンの構成

一回で実行される内訳は以下の通りです:

  1. 速度にヨットの位置するマスの風を加算します。
  2. 速度にモーター入力を加算します。
  3. 速度に基づいて位置を更新します。
実行結果(ステップ3)で海図の外に出てしまうと、その時点でプレイ終了となり最後の有効な海図上の位置および速度を元に得点が計算されます。

構文

このコンテストでは、テストシステムから呼び出す関数solver.mを書いていただきます。この関数は以下のような構文に準拠する必要があります:

[thrustRow, thrustCol] = solver(chart, startIndex, targetIndex, maxThrottle)

二つの引数startIndexおよびtargetIndexはヨットの移動開始点と目標到着点を示すスカラー値です。いずれも行列に対する絶対インデックスです。対応する行および列の値は、以下のようにIND2SUBコマンドで簡単に取得できます。

[targetRow, targetCol] = ind2sub(size(chart(:,:,1)),targetIndex)

海図(chart)変数は三次元行列で、行の風が一ページ目 chart(:,:,1)、列の風が二ページ目 chart(:,:,2)で与えられます。

ターンの回数の絶対的な上限: 100

参考例

上記の海図を元にした詳細な例を見てみましょう。

ここでは、南に下って(行インデックスを上げる)、東に吹く風に乗って右へ航海しよう(列インデックスを上げる)としているものとします。この場合は最初にモーター入力で行速度を1に上げることになります。その後、モーター入力を使って南への移動や東への移動を止める必要があります。この手順を表にすると以下のようになります:

Ri = 初期行、Ci = 初期列、vRi = 初期行速度、vCi = 初期列速度、デルタvWR = 風による行速度の変化、デルタvWC = 風による列速度の変化、デルタ vMR =モーターによる行速度の変化、デルタvMC =モーターによる列速度の変化、vRf = 最終行速度、vCf = 最終列速度、Rf = 最終行、Cf = 最終列。

この図では、三回目終了後のヨットの位置が星印で示されています(行4、列2)。

7回目が終了した時点で、速度はゼロに落とされ、ヨットが指定された目的地に到着します。では、この場合の得点がどうなるかを見てみましょう。

結果

個々の海図(chart)ごとに以下のように得点が計算されます:

(finalRow - targetRow)^2 + (finalCol - targetCol)^2 + ...
  2*abs(vRow) + 2*abs(vCol) + ...
    + sum(abs(thrustRow)) + sum(abs(thrustCol))

この計算式は、ヨットが目的地のマスで正確に停止し(距離あるいは速度にエラーがない)、モーターの使用量が最小の場合に、最小(最良)得点を出力するようになっています。

以下の場合も含み、いかなる場合でもモーター入力が加算されることにご注意ください。:

  1. 海図から外れたためにヨットが途中で止まった場合
  2. 最大スロットル(maxThrottle)で許容された制限以上のモーター入力を要求した場合

採点

あなたのエントリーの総合得点は複数の要因の組み合わせです。最初の二点が最も重要です。残りの二点は副次的な影響があります。

  1. 全ての課題を通しての結果の平均値
  2. コードの実行速度
  3. コードの循環的複雑度 (詳しくは下記を参照してください)
  4. コードのノード数 (詳しくは下記を参照してください)
いずれの要因も最小化するのが目的ですので、コンテスト終了時の最低得点が優勝となります。

循環的複雑度

循環的複雑度は、McCabe複雑度ともいい、プログラムのソースコード内の独立パス数の尺度です。通常、この数値が大きいほど、プログラムの内容の理解が困難になります。またテスト、修正、リファクタリングも難しくなります。

ファイル内には、複数の関数が含まれる可能性がありますので、あるファイルの複雑度は、そこに含まれる関数のいずれかの最大複雑度により定義されます。標準的な指標は、個々の関数の複雑度を10以下に抑えることですので、このコンテストでは、10を超過した複雑度に応じて得点が上がります。つまり、全ての関数の複雑度が10以下のエントリーには、複雑度のペナルティーは課されません。

MATLABでは、mlintで「cyc」オプションを指定することにより、どの関数でもその循環的(またはMcCabe)複雑度を計測できます。例えば、この例を試してください:

>> mlint -cyc magic.m

エントリーの複雑度をより簡単に判定できるように、コンテスト用の配布ファイルにgetComplexity.m関数を含めました。

ノード数

これは、コードの長さの大まかな尺度ですが、コメントや変数名の長さではペナルティーは課されません。

t = mtree('your code');
length(t.nodesize)

実行時間とサイズの上限

実行に180秒(3分)以上かかるエントリーはタイムアウトし、失格となります。

コードのサイズは、データベースの構造により制限されます。Mコードを格納するコンテスト用MySQLデータベースのコラムはText型で、最長65,535バイトに制限されています。この上限を超過するエントリーはエラーとなります。

エントリーの作成

コンテストにエントリーするのに必要なファイルは、MATLAB Central File ExchangeにあるZIPファイルに含まれています。このZIPファイルをダウンロードして解凍すると、以下に解説するファイルを入手できます。

構文

メインのルーチンはsolver.mです。その構文は上出の通りです。変数名は重要ではありません。この関数をZIPファイルに含まれるテスト環境でテストするには、runcontest.mを実行します。

 >> runcontest

コンテストについて

コンテストは、三つの期間に分割されています。一週間の期間のほどんどは、コードを自由に交換できる通常モードとなりますが、最初の二日間は、個々のエントリーについての情報の一部が隠蔽されます。

  • Darkness (水曜日12 PM~木曜日12 PM) コンテスト一日日は、どのエントリーもコードや得点が見られません。
  • Twilight (木曜日12 PM~金曜日12 PM) コンテスト二日目は、得点は見られますが、コードは見られません。
  • Daylight (金曜日12 PM~水曜日12 PM) コンテスト残存期間は、 (Late-Stage Twilight期間を除き)、全てのエントリーの得点とコードが見られます。
全ての時間は米国東部標準時間です。日本時間では、Darknessは木曜日2 AM~金曜日2 AMとなります。

他者との協力と既存エントリーの編集

一旦エントリーが提出されると、変更できません。しかし、どのエントリーも閲覧、編集、新規エントリーとしての再提出が可能です。提出されたエントリーはどれでも閲覧やコピーが自由です。既存のエントリーへの改変が得点を改善できれば、このコンテストの優勝者を決定する上では、改変者がそのコードの「著者」になります。既存のエントリーを研究して最適化することは奨励しています。

また、解決策や戦略などを他者と話し合うことも奨励しています。このために用意したスレッドへMATLAB CentralのNewsreaderから投稿してください。

細則

利用が許可されている関数は、$MATLAB/toolbox/matlabにある基本MATLABパッケージ内で提供されているものとし、$MATLABはMATLABルートディレクトリを指すものとします。他のツールボックスの関数は利用できません。エントリーは、最新版のMATLAB上でテストされます。 以下の利用は禁止されています:

  • MEXファイル
  • Javaコマンドやオブジェクトの作成
  • eval, feval, inline, function handlesなど
  • !, dos, unixなどのシェル エスケープ
  • Handle Graphicsコマンド
  • ActiveXコマンド
  • File I/Oコマンド
  • Debuggingコマンド
  • Printingコマンド
  • Simulinkコマンド
  • tic, toc, flops, clock, pauseなどのベンチマーク用コマンド
  • error, clear, persistent

ハッキング

コンテストのシステムを侵害するエントリーは許されていません。コンテストの参加者全員に対する配慮として、システムの不正利用をしないようにお願いします。

採点、実行、あるいはエラー条件を操作してテスト環境内のパズルを抽出することも禁じます。限定的な範囲で、これは過去のコンテストの要素の一つでしたが、Blockbuster Contestでは、Alan Chalker氏が科学の領域まで高めてしまいました。Tweak bombingその他の手法によりコンテストのテスト環境にエントリーをチューニングすることは許可されていますが、システムの処理能力を圧倒しないようお願いします。

FAQ

コンテストについてよくある質問への回答は、FAQで確認してください。

指定された情報の隠蔽期間について

コンテストは、ユーサーに対して一部あるいは全ての得点やコードが隠蔽される期間に分割されています。このコンテストの期間は以下のとおりです:

  • Daylight - 全てのエントリーの得点およびコードを閲覧できます。
  • Twilight - 得点は閲覧できますが、コードは見られません。
  • Darkness - いずれのエントリーの得点もコードも閲覧できません。