kahoの日記： Google Code Jam 2009敗戦記

/.Jで紹介されていたGoogle Code Jamに参加してみたが，システムがよく分かっていなかったのでlarge問題の入力ファイルをダウンロードして放っておいた所，時間切れになっていて投稿できなくなっていた．２４時間でやればいいと悠長に構えていた頭の悪さで敗退．
とりあえず自分がやった結果をメモとして記す．あまり長くならないように切り詰めたので読みにくいコードだが，その際にエンバグしていなければ少なくともsmall問題は通過するはず．

A.エイリアンの言語
与えられた辞書に適合する単語の数を数えるもの．（）を［］に置換して正規表現にするだけという書くまでもないプログラムなので省略．

B.水系の区画
土地の高さデータから水の流れる方向を決め，それぞれの区画を出発点とした水流がどこに流れるかを決めるもの．
それほど大きなデータサイズではないので力技でできる．それだけにあまり工夫せず冗長なスクリプトで対処．
N x Mのデータに対して計算量はO(N x M)．

#-*-coding:utf-8-*-
def propagate(lat, sinks, H, W, i, j, sink_num): # あるセルがどのsinkにつながるか調べる
    points = []
    while sinks[i][j] is None:
        points.append((i,j))
        l = lat[i][j]
        north = lat[max(0, i - 1)][j]
        west = lat[i][max( 0, j - 1)]
        east = lat[i][min(W - 1, j + 1)]
        south = lat[min(H - 1, i + 1)][j]
        if north < l and north <= west and north <= east and north <= south:
            i -= 1
        elif west < l and west <= east and west <= south:
            j -= 1
        elif east < l and east <= south:
            j += 1
        elif south < l:
            i += 1
        else: # 新しいsinkに到着
            sinks[i][j] = sink_num
            sink_num += 1
            break
    for r,c in points: sinks[r][c] = sinks[i][j] #経路を全て塗りつぶす
    return sink_num
 
def determine_flow(H, W, latitudes):
    lat = [map(int, line.split(' ')) for line in latitudes]
    sink_num = 97 # chr(97) = 'a'
    sinks = [[None] * W for i in range(H)]
    pattern = ''
    for i, j in [(h,w) for h in range(H) for w in range(W)]: #流れる先を決定
        sink_num = propagate(lat, sinks, H, W, i, j, sink_num)
        pattern += chr(sinks[i][j]) + '¥n '[j < W - 1]
    return pattern
 
if __name__ == '__main__':
    print(determine_flow(4, 5, ('7 1 8 6 7',
                                '8 0 6 5 2',
                                '3 2 3 4 1',
                                '7 5 9 2 3')))

C.特定の文字パターンの組み合わせ数
任意のスキップを入れつつ，あるテキストと同一のパターンをとる経路の数を数える問題．
シークエンスのアライメントを意識しつつ行が目的の配列で列が入力配列のマトリクスを作成し，集計した．
目的配列の長さがN，入力配列の長さがMのとき，計算量はO(N x M^2)

#-*-coding:utf-8-*-
def count_variants(text, correct):
    rows, columns = len(correct), len(text)
    matrix = []
    matrix.append([text[col] == correct[-1] for col in range(columns)]) #最初の行の初期化．末端と適合していれば1
    for row in range(1,rows):
        matrix.append([0 if text[col] != correct[-1 - row] else sum(matrix[row - 1][col + 1:]) % 10000 for col in range(columns)])
        pass
    return sum(matrix[rows-1]) % 10000
 
if __name__ == '__main__':
    print(count_variants('wwwelllcome tto code jjjjjamm', 'welcome to code jam'))

追記：特定の入力ファイルがないと何をしているか意味が分からなかったので修正．