読者です 読者をやめる 読者になる 読者になる

Round 1A

GoogleCodeJam

とりあえずRound 1Bに向けてソワソワしてるので
この間にブログを更新してみます。
Round 1Bに進むということは当然Round 1Aに落ちたわけで、
Aだけ正解して23pt獲得の1340位でした。
問題公開直後に配点の表示がおかしくて
Aから解くのが得策だなんて思ったのは今となっては良い思い出。


問題はこちらです。
A : http://code.google.com/codejam/contest/dashboard?c=544101#s=p0
B : http://code.google.com/codejam/contest/dashboard?c=544101#s=p1
C : http://code.google.com/codejam/contest/dashboard?c=544101#s=p2

まぁ、Aはオセロを実装したことがある人なら
きっとすぐに解けた問題でしょう。
要は

2次元の格子状の盤面に赤と青の駒が無造作に置いてあって、
・それらの駒を重力で隙間なく右方向に詰める
・縦 or 横 or 斜めに指定された数だけ連続して同じ色の駒があるかを判定する

というシンプル極まりない問題です。
こんな問題に80分程度かかってしまったのは、
なんとも恥ずかしいミスをしてしまったからです。

BLANK, R, B = 0, 1, 2
K = 3
brd = [
    [BLANK, R, B],
    [R, B, B],
    [B, R, R],
]

for x in brd:
    print x

N = len(brd)

def find_line(brd):
    found = {
        R:False,
        B:False,
        BLANK:True,
    }
    for y in xrange(N):
        for x in xrange(N):
            target = brd[y][x]
            if found[target]:
                continue
            
            for dx, dy in ((1, 0), (-1, 1), (0, 1), (1, 1)):
                line_found = True
                for i in xrange(1, K):
                    tx = x + dx * i
                    ty = y + dy * i
                    try:
                        if brd[ty][tx] != target:
                            line_found = False
                            break
                    except IndexError:
                        line_found = False
                        break
                if line_found:
                    found[target] = True
                    break
    if found[R]:
        if found[B]:
            return 'Both'
        return 'Red'
    if found[B]:
        return 'Blue'
    return 'Neither'

print find_line(brd)

こんなミスです。
おわかりいただけましたでしょうか?
言い訳をすると、まだC/C++畑で育った癖が抜けてないんですね。
正しくはこうしなければいけません。

def find_line(brd):
    ...(略)
                    if 0 <= tx and tx < N and 0 <= ty and ty < N:
                        if brd[ty][tx] != target:
                            line_found = False
                            break
                    else:
                        line_found = False
                        break
    ...(略)

print find_line(brd)

C++では配列のインデックスに負の値を指定するなどという
傍若無人なことは許されなかったので、
ついこういうコードを書いてしまうんですよね。
いやはや、「なるべく例外を発生させない」という原則は
コードのクオリティが期待されないGoogleCodeJamにおいても
守らなければならないな、と改めて再認識しました。


というわけで、Round 1Bも楽しく挑戦してみたいと思います。
Round 1Bと1Cの解説はまた今度余力があればやります。