Google Code Jam Japan 2011 明日開催

ご無沙汰してます。Over80です。
最後にこのブログにエントリを書いたのは3月頭ですから、半年ぶりの更新になります。
その間の事に関しては、書くと愚痴が多くなってしまうのでやめておきますが、震災の影響はいろいろと大きかったことと、私は直接被災はしておらず無事であること、あと、震災に遭われた方々へお見舞い申しあげます、とだけは言っておきます。

さて、今日の本題は、明日に開催をひかえた Google Code Jam Japan 2011 と、それに向けた Python の自作テンプレートの紹介です。

Google Code Jam Japan 2011 とは?

簡単に言うと、競技プログラミングコンテストで、明日午後1時にWebで公開される問題(複数)に対して、それを解くプログラムを作成して提出すればポイントゲット。沢山、早く解いた人が勝ち。みたいなコンテストです。
問題は比較的典型的なアルゴリズム問題(たとえば「迷路の最短経路を答える」のような)で、Webから問題データ(たとえば「迷路を表現したテキストデータ」)をダウンロードでき、それを作ったプログラムで解いて、答えのデータをアップロードすることで回答になります。

類似のコンテストと比べると以下のような個性的な特徴があります。

• 予選から決勝までオンラインで開催される。自分の慣れたPCで集中して解けば良い。
• プログラミング言語や実行環境に(事実上)制限が無い。事務局や他の参加者が確認できるよう、フリーで実行環境が入手可能なもの、という制限があるだけで、VisualStudio も Express があるので OK となっている。あまつさえ、表計算ソフトのような物で解くことも認められている。("プログラム"の代わりに、そのソフトをどう使ったかを説明するテキストの提出が求められますが。)
• 今回の Japan 2011 は、日本語で開催される。大抵の大会(通常の google code jamも含む)は英語で開催され、問題文も英語なので、読むのに時間がかかる所が最初からハンデだったりする。

詳しくは Google Code Jam Japan 2011 のサイト を参照してください。(私の説明には誤謬があるかもしれません。)

上位入賞者には賞金や景品がありますので、気楽に参加してみてはいかがでしょうか？

日本語の例題は既に Code Jam Japan のサイトに上がっていますし、英語で良ければ過去問はこちらにあります。試しに解いてみるだけでも勉強になるかもしれません。

Python のテンプレート

さて、私もこれに参加してみようかと思い、過去の Google Code Jam の問題を幾つか解いてみたのですが、これ、問題の入力や出力がある程度定型フォーマット化していますので、予め parsing するコードなどは作成しておく事をおすすめします。

とりあえず私はこんな感じのコードを書いてみました。
これは Code Jam 2009, Qualification Round の Alien Language という問題 に対する回答です。

#!/usr/bin/env python2.6

import getopt
from itertools import *
import multiprocessing
import os.path
from random import *
import sys

# utils
def read_numbers():
    return map(int, infile.readline().split())
def read_string():
    return infile.readline().rstrip('\r\n')
def list2str(*array):
    return ' '.join(map(str,array))

############################################################

# random testcase
def rand_testcase():
    chars = [chr(x) for x in range(ord('a'), ord('z')+1)] + [' ']
    Ls = [choice(chars) for x in range(1000)]
    del chars, x
    return locals() 

# pre-condition parser
def read_precond():
    (L,D,N,) = read_numbers()
    Ds = set()
    for d in range(D):
        Ds.add(read_string())
    
    return (N, dict(Ds=Ds))

# testcase parser
def read_testcase():
    s = read_string()
    pat = []
    cs = None
    for c in s:
        if c == '(':
            cs = []
        elif c == ')':
            pat.append(cs)
            cs = None
        else:
            if cs != None:
                cs.append(c)
            else:
                pat.append([c])
    print pat
    return dict(pat=pat)

# solver
def solve(Ds, pat):
    i = 0
    for p in pat:
        Ds = filter(lambda a: a[i] in p, Ds) 
        i += 1
    return len(Ds)


############################################################

opt_single = True
opt_random = 0

try:
    opts, args = getopt.gnu_getopt(sys.argv[1:], "mr:")
    for o, a in opts:
        if o == '-m':
            opt_single = False
        elif o == '-r':
            opt_random = int(a)
        else:
            raise Exception("unknown option(%s)" % (o,))
    if opt_random:
        outfile = (sys.stdout,)
    else:
        infilename = args[0]
        outfilename = os.path.splitext(infilename)[0] + ".out"
        infile = open(infilename, 'r')
        outfile = (sys.stdout, open(outfilename, 'w'))
except Exception, e:
    print >>sys.stderr, e
    print >>sys.stderr, 'Usage: %s [-m] <inputfile>' % (sys.argv[0])
    print >>sys.stderr, '       %s -r num' % (sys.argv[0])
    exit(1);

if opt_random:
    num_tests = opt_random
    get_testcase = rand_testcase
else:
    (num_tests, precond) = read_precond()
    get_testcase = read_testcase

# prepare testcase iterator
def read_testcases(num_tests):
    for i in range(num_tests):
        yield get_testcase()
testcases = read_testcases(num_tests)

# prepare solve iterator
def call_solve(q):
    d = dict(precond)
    d.update(q)
    return solve(**d)
if opt_single:
    res = imap(call_solve, testcases)
else:
    p = multiprocessing.Pool()
    res = p.imap(call_solve, testcases)

# solve & print
for (i, r) in enumerate(res, start=1):
    for f in outfile:
        print >>f, "Case #%d: %s" % (i, str(r))

ちょっと長いですが、本番で問題を解く場合には上記のコードのうち中程にある、 read_precond (入力データの先頭にあるヘッダの読み込み) と read_testcase (個々のテストケースの読み込み) と solve (与えられたテストケースを解く) の 3 つの関数の中身を埋めるだけで良いようになっています。上記の例では高々30行です。

パースや整形出力は極力楽に出来るようデザインしています。この問題の場合、テストケースのフォーマットが特殊なので解析のコードが若干長くなっていますが、入力データが数字だけの場合は、

def read_testcase():
   Ds = read_numbers()
   return locals()

のように簡潔な記述ができますし、問題を解く solve も、引数で与えられたテストケースを解き、答えを return するだけで良く、問題に集中できるようにしてあります。

プログラムには引数として入力ファイルを与えて実行します。結果は入力ファイルの拡張子を .out に変更したファイルに、自動的に定型フォーマットに整形した形で出力されますので、そのまま提出できます。デバッグ情報を print しても、出力ファイルが汚される事はありません。

また、"-m"オプションを付けて実行するだけで、自動でマルチプロセスによる並列計算を行いますので、マルチコアCPUでもプロセッサを無駄にしません。さらに、問題に応じて rand_testcase 関数としてランダム問題ジェネレータを自分で実装すれば、入力ファイル無しで実行テストが出来ますので、Large のデータで回答するまえにパフォーマンスが十分かどうかの確認に使えます。

itertools をフルでインポートしてたりする辺りも密かにポイントです。このてのアルゴリズム問題を解くのに便利なツールが大量に詰まっているモジュールです。

とまぁ、いろいろ無駄に詰め込んだスケルトンコードなのですが、実はコレを作成したのは半年前、まさに震災の頃で、その時にこれを作って以降、練習はおろか、python すら触っていないので、明日の朝にかるくリハビリしてから予選に望もうかと思います。

(2011/10/08 追記: テンプレートを拡張しました → Google Code Jam 向け python template - 玉虫色に染まれ！)