Google Code Jam 2019のインタラクティブ問題を解くときのメモ

google code jam

このエントリーをはてなブックマークに追加

Google Code Jam でインタラクティブ問題が初登場したのはリニューアル後の2018年。2019年にも引き続きインタラクティブ問題が出題されたのだけれど、ローカルでのデバッグ用にGoogleが提供するデバッグツールの使い方が2018年から変わっていたので、その使い方を忘れないようにメモしておきます。

準備

まず、手元にPython環境を用意します。手元で動かす限りPython 2でもPython 3でもどちらでもよいようですが、今ならPython 3の一択でしょう。

次に、interactive_runner.pyとtesting_tool.py、2種類のデバッグツールを、問題文に付記されたリンクからダウンロードします。このうち、interactive_runner.py はインタラクティブ問題に共通するスクリプトで、testing_tool.pyはその問題に特有のスクリプトです。

注：Google Code Jam 2020では testing_tool.py から local_testing_tool.py という名前に変わりました。名前以外は今も変わっていないと思います。

実装

次に、問題を解くスクリプトを実装します。例えば、Google Code Jam 2019 Round 1Aで出題された Golf Gophers のSmallを解くC++のコードを gist に示します。

実装には以下のことに気をつける必要があります。

  • 標準出力したあとは必ずflushする。
    • これをしないとツールが待ち状態になってTLEしてしまいます。
    • C++でのflushは、標準出力のあとに毎回必ず cout << flush; とすればよいです。
    • Python 3でのflushは、print('answer', flush=True) などとflush=Trueをprintに加えればよいです。もしくは、以下のようなprint2関数を定義しておき、print2('answer')などとprintの代わりにprint2を使うようにする手もあります。
def print2(*args, **kwargs):
    print(*args, **kwargs)
    sys.stdout.flush()
  • デバッグプリントは標準エラー出力で行う。
  • 問題文の指示に従った入出力を行う。
    • 例えば、 Golf Gophers の場合、解答を出力したあとにその結果が正しいか否かをverdictで受け取り、これが-1だったらすみやかにプログラムを終了させねばなりません。そうしないとデバッグツールがずっと待ち状態になってしまいます。

C++のようなコンパイルを要する言語で実装した場合は実行ファイルを生成しておきます。ここでは実行ファイルをa.outとします。

ツールの実行

C/C++にて実行ファイルa.outを生成した場合、以下のようにツールを実行します。

$ python interactive_runner.py python testing_tool.py 0 -- ./a.out

Pythonにてsolve.pyという名前のスクリプトファイルを作成した場合、以下のようにツールを実行します。

$ python interactive_runner.py python testing_tool.py 0 -- python solve.py

(solve.pyに実行権限をつけている場合)
$ python interactive_runner.py python testing_tool.py 0 -- ./solve.py

ここで、第3引数にある'0'はSmall用のテストケースを、'1'はLarge用のテストケースを使うことを意味します。テストケースはtesting_tool.pyに埋め込まれているので自由に改変可能ですが、問題により埋め込み方は異なるので読み解きが必要です。たとえば

Google Code Jam 2019 Round 1Aの Golf Gophers であれば以下の部分を修正する必要がありました。

CASES = ([1, 2, 3],
         [1, 2, 3]) # fill in your own cases
QS = (365, 7)

Google Code Jam 2019 Qual DのDat Baeであれば以下の部分を修正する必要がありました。

def getTestCases(test_number):
  F = (10, 5)[test_number]
  # You can edit or add your own test cases here.
  cases = [Case([1, 2, 3], 4, F), Case([2, 3, 5], 6, F), Case([1000], 1024, F)]
  return cases

ツールの実行結果の見方

無事正答を出すプログラムで上記ツールを実行すると以下のように表示されるはずです。

Judge return code: 0
Judge standard error:
Solution return code: 0
Solution standard error:
(標準エラー出力の結果がここにまとめて表示される)

エラーがある場合は以下のようにどのテストケースで落ちたかが表示されます。

Judge return code: 1
Judge standard error: Case #1 (1) failed: Wrong guess: 3. Expected: 1.

Solution return code: 0
Solution standard error:
(標準エラー出力の結果がここにまとめて表示される)

参考URL