Crossword - Rules 日本語訳

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

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

課題

あなたは大手数学ソフトウェア新聞「The New York Multiply ("All the News That's Bits and Ints")」の新任クロスワードパズル担当研修生です。上司の編集者から今週のパズルで使う単語のリストを渡されました。リストにある言葉を全て使い切ることはできないのは了解済みですが、単語ごとに重みをつけ、「ベストを尽くしてがんばってみて」と言い残していきました。上司が同じ課題を他の研修生にも与えたことをたまたま知ってしまったので、地位を維持するにはいい結果を出さないといけません。なにかいいソフトウェアが役に立つかもしれません...

詳細

ルール上では説明のために単語を使って解説しますが、実際には「単語」は整数ベクトルであることにご注意ください。

言い換えると、課題は以下のようになります: 与えられた有効な単語のリスト(「辞書」)とグリッドの大きさに対し、高価値の単語を最大限に使いつつ無効な単語(辞書に含まれない単語)を最小限に抑えるようなグリッドを返してください。

採点ソフトウェアは返されたグリッドを、行は左から右に、列は上から下に走査し、そこに含まれる全ての単語のリストを作成します。パズルグリッドから取り出された単語はそれぞれ(有効な単語の場合は)辞書から削除されるか、(無効な場合は)無効な単語のリストに追加されます。このため、辞書に一回しか現れない単語の場合、グリッドに一回目以降現れるとそれは無効な単語として扱われます。

例えば、辞書にHELP、SINE、MAP、MATHおよび PLOTが含まれており、その重みは左に示すとおりだとします。そして右にあるようなグリッドを作成したとします。

採点アルゴリズムは行を走査してMAP、HELP、MATHの三つの単語を読み出します。縦に走査すると有効な単語PLOTだけでなく二つの無効な単語MHとAEも読み出されます。有効な単語SINEはボード上に組み込まれませんでした。

辞書に残った未使用の単語の重みは全て得点に加算されますので、得点は低いほどよいことになります。単語が使われると、有効な単語のリストから削除されます。SINEは使われず、重みは5なので、それが得点になります。それだけではありません。無効な単語についても全てペナルティを支払わなければなりません。無効な単語に対する重みは個々のパズルによって異なります。この場合ではペナルティが3だとします。このペナルティを考慮に入れると、辞書の合計5に無効な単語の合計2*3=6を加え、総合計は11となります。

これを見ると単語MAPを最初の行に加えたのがよくなかったのが容易に分かります。その価値(辞書の重み5)に対しそのコスト(ペナルティ6)が見合いません。ただし、ペナルティが単語あたり3ではなく2であれば、MAPを使ったのは賢い手であったことになります。さらによいのは、総合得点が4となる次のグリッドです。辞書に残される単語はMATHおよびPLOTの二件だけとなり、無効な単語は発生しません。

他の注意事項

  1. 空欄はゼロで示してください。
  2. 有効な単語の長さは最短で2です。つまり、辞書には一文字だけの単語は含まれません。
  3. 辞書に含まれる個々の単語は辞書に出現する回数以上に使用することはできません。例えば、辞書で一回だけしか出現しない単語はグリッド上では一回しか有効に試用できません。それ以降は、出現するたびに無効として扱われます。
  4. 単語は一続きの連続したグループである必要はありません(Scrabbleのような連続性は要求されません)。
  5. 一文字が単独で出現する場合、それは上下左右で二回無効な単語としてペナルティが発生します。
  6. ここではASCII文字と英単語を説明のために使いましたが、実際のテストシステムでは正の整数からなるベクトルが使用されます。これらのベクトルはASII文字および英語のいずれの制約も受けません。

数字による例

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

>> words
    [1x4 double]    [1x4 double]    [1x3 double]    [1x4 double]    [1x4 double]

>> words{1}
    72    69    76    80
>> words{2}
    83    73    78    69
>> words{3}
    77    65    80
>> words{4}
    77    65    84    72
>> words{5}
    80    76    79    84

>> penalty
     3

>> weights
    10     5     4     2     2
そして、返されるグリッドは以下のようになります。
    77    65    80     0
    72    69    76    80
     0     0    79     0
    77    65    84    72

構文

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

board = solver(words, weights, n, penalty)

  • words は有効な単語のセル配列です。実際にはこれらは数字です。
  • weightsはwordsと同じサイズのベクトルです。
  • nは出力されるグリッドの大きさです。
  • penaltyはグリッドに含まれる個々の無効な単語に対して加算される点数です。
  • boardは、数字からなるn-by-n行列です。使用しないマス目はゼロに設定します。

結果

個々のパズルごとに以下のように得点が計算されます:

result = sum(未使用単語得点) + penalty * (無効な単語の数)

採点

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

  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は木曜日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 - いずれのエントリーの得点もコードも閲覧できません。