The Vines - Rules 日本語訳

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

課題

このコンテストはお馴染みの15パズルからヒントを得ています。

通常の15パズルは、4×4のボード上に、1から15までの番号を振られた移動可能なコマがあります。16番目のコマに相当するマス目は空いています。この空いたマス目を利用して目的の形になるまでコマを動かします。

コンテストで使用するゲームでは、ボードはより大きく、目的はより抽象的です。

詳細

与えられた数値が並ぶボードを使って、数値を最大化するような順番にコマを並べるものとし、これを「ツル (vine)」と呼びます。ツルは単調増加する(同じ数字の連続も許容する)4つの連続したコマです。言い換えると、一回ごとに一マス上下左右への移動により作成される自己交差しない経路のことです。ツルの値は個々のコマの値の合計です。 例を使って説明します。4x4のボードがあります。すぐに15パズルとの二つの違いがお分かりかとおもいます: 数字は1から15に制限されていないこと(ただし整数ではあります)、空いたマスがないことです。

ツルの数字は単調増加する必要があることにご注意ください。このボードで可能なツルの一例は [5 8 14 15 20 50] で、その合計値 112です。もうひとつの可能性は [5 8 9 15 20 50]ですが、合計値は107にしかなりません。

ツルの長さ

ツルは、任意に好きなだけ長くできますが、得点はツルの値(コマの値の合計)であって、ツルの長さではないことにご注意ください。

ツルを指定するには、コマの線形インデックスを順番に並べます。この場合、ツルの最初のコマは [1,1]で、その線形インデックスは1です。添え字を [行,列] 表記から線形表記に変換するには、MATLABの sub2ind 関数を以下のように使います。

        ind = ind2sub(size(board),row,col)
        
図示したツルの線形インデックス表記は [1 2 3 7 11 12] となります。board(ind) はツルを構成する値のベクトルを戻します。

コマの移動

15パズルと同様に、コマを移動させることができます。このコンテストでは、移動するマス目が空いているかどうかは気にする必要はありません。既存のコマの上に別のコマを移動すると、既存のコマは取り除かれます。

コマ20と44を移動して[5 8 14 20 44 50]というツルを作る場合は以下のようになります。下図のステップ1でコマ20をコマ15があるマス目に移動します。コマ15はこれでボードから完全に取り除かれます。これで新たに出来た空いたマス目はステップ2でコマ44で埋めます。

これにより、以下のようなボードとなりますので、[5 8 14 20 44 50] というツルを作成できるようになります。

移動上限

このツルを作成するのに二回移動しました。明らかに他のコマの移動でもなんらかのメリットがあったでしょう。たとえば、9を8の上に移動すると、[5 9 14 20 44 50] というさらに少し得点の高いツルになります。しかし、移動回数には上限があり、それは2回です。

他の注意事項

  1.   空いたマス目の値はゼロであるとみなします。
  2.   ツルの構成要素の値は単調増加するものとしますが、連続した同数値も許容されます。例えば、[1 3 4 4 7] は有効なツルです。また [4 4 4 4] も同様です。
  3.   コマの移動は必須ではありません。

実例

明確性を期すため、実際には上述の課題は以下のようになります。

        >> board
        
             5     6    18     6
             8     9    44    12
            14    15    20    16
             7    11    50     3
        
        >> limit
        
            2
        
        >> [moves, vine] = solver(board, limit)
        
        moves =
        
            11     7
            10    11
        
        vine = 
        
             1     2     3     7    11    12
        
        >> modified_board 
        
             5     6    18     6
             8     9     0     1
            14    15    44    16
             7    11    50     3
        
        >> modified_board(vine)
        
             5     8    14    15    44    50
        
        >> sum(board(:))
        
           244
        
        >> sum(modified_board(vine))
        
           136
        
        >> result = sum(board(:)) - sum(modified_board(vine))
        
           108
        

構文

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

[moves, vine] = solver(board, limit)

  • board は正の整数からなる n x m 配列です。
  • limit は許容される総移動回数の上限です。
  • moves は、移動の順番を示す n-by-2 配列です。個々の行は移動の順番を示します。最初の列は移動するコマの線形インデックスです。二番目の列は移動先のインデックスです。
  • コマを移動したくない場合は、空の配列 [] を moves として戻してください。
  • 無効な移動は無視されます。
  • vine は番号の並び順を指定する特定のボードに対する線形インデックスのベクトルです。

結果

個々のパズルごとに以下のように得点が計算されます。移動によりボードは変わるため、元のボードと移動後のボードの両方を比較することが出来ることにご注意ください。

        result = sum(board(:)) - sum(modified_board(vine))
        

result は最小化する必要があります。また、以下の制約も違反しないようにしてください:

size(moves,1) <= limit

採点

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

  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、夏時間の場合は木曜日1 AM~金曜日1 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 - いずれのエントリーの得点もコードも閲覧できません。