Google Codejam 2014 Qualificationラウンドの三問目

今日はGoogle CodejamのQualificationラウンドでしたね。

張り切って参加したもののMinesweeper Masterが、解けそうで解けなかったので書いときます。マインスイーパが1クリックで解ける条件として、空のセルは1つの領域に固まってる必要があって、それをボードのサイズで細かく場合分けして行く感じでした。

僕は「ボードの小さい方の辺が2以上の場合に、空のセルが5もしくは7の時は解けない」という条件が思いつけず、あえなく時間切れになってしまいました。サンプルを処理するまでは、結構簡単に出来たのですけど、
そのダラダラデバッグしてたら解ききれなくて悲しいです。タイムアップ後少し修正したコードを貼っておきます。

# -*- coding: utf-8 -*-

import sys


def judge(R, C, M):
    E = R * C - M # empty
    W, last_row, need_adjust = (0, 0, False)
    if E == 0:
        pass
    elif E == 1 or M == 0:
        W = C
    elif C == 1:
        if E > 0:
            W = 1
    elif C == 2:
        last_row = int(E / 2) + 1   # 1 base
        if E % 2 == 0 and E >= 4:
            W = 2            
    elif E == 5 or E == 7:
        pass
    elif C >= 3:
        for w in range(2, C+1):

            last_row = int(E / w) + 1   # 1 base
            last_row_num = E % w

            if E < = w: continue
            if last_row > R: continue
            
            if last_row == 2:
                if last_row_num == 0:
                    W = w
                    break
            elif last_row >= 3:
                if last_row_num >= 2 or last_row_num == 0:
                    W = w
                    break
                elif w >= 3 and last_row_num == 1 and R >= 3:
                    W = w
                    need_adjust = True
                    break
    return W, last_row, need_adjust



for T in range(1, int(sys.stdin.readline())+1):
    (R, C, M) = map(int, sys.stdin.readline().split(' '))
    transpose = False
    if C > R:
        (R, C) = (C, R)
        transpose = True

    E = R * C - M # empty
    W, last_row, need_adjust = judge(R, C, M)
    if W == 0:
        ans = 'Impossible'
        print 'Case #%(T)s:\n%(ans)s' % locals()
        continue

    # make board
    board = [['*'] * C for i in range(R)]
    for i in range(E):
        c = i % W
        r = i / W
        board[r][c] = '.'
    if need_adjust:
        board[last_row-1][1], board[last_row-2][W-1] = board[last_row-2][W-1], board[last_row-1][1]
    if transpose:
        board = map(list, zip(*board))
        R, C = (C, R)
    board[0][0] = 'c'

    # show answer
    print 'Case #%(T)s:' % locals()
    def show_board(board):
        for row in board:
            print ''.join(row)
    show_board(board)

今年はTシャツ欲しいです。

Google Glass買った

Google Glassはまだ一般には販売されてなくて、あらかじめExplorer Programに申し込んでおいて、枠が空いたらメンバーに招待される感じになっています。しかもアメリカに住所がないと買えません。僕は1年くらい前に申し込んで、ようやくInvitationが送られてきました。まぁ1500ドルとか笑えない金額なんですけど、せっかくアメリカに住んでるし、ウェアラブルコンピュータが次のトレンドっぽいし、Androidも覚えたいし、ボーナスも貰ったし、まぁいいかというので買いました。

続きを読む

Xcodeプロジェクト内の使われてないリソースを探す

iOS7以降、主なアプリはほぼフラットなスタイルに移行していますね。iHeartRadioでもフラット+iOS7対応は一旦完了しているものの、まだ試行錯誤の途中でバージョンアップ毎に結構デザインを変更しています。

そこで問題になるのがリソースの管理です。プロジェクトの体制にもよると思いますが、一般に新しいファイルの追加は簡単でも、古いファイルを削除するのは本当に使われてないか確認するコストが高くて面倒です。そうして気がついたらプロジェクトの中が古い画像ファイルだらけになっていて、これは良くないなというので使われてない(かもしれない)画像ファイルを列挙するスクリプトを書きました。

続きを読む

Xcodeプロジェクト中のコード行数を取得するGemを書いた

RubyはiHeartRadioだとプロダクションコードではあまり使われてないんですが、開発補助系のタスクでは徐々に存在感を増してる感じです。自分で最初から何か書く時はPythonで良いのですけど、他の人が書いたツールを弄ったりするのに必要なのでRubyでコード書き始める事にしました。それでいきなり仕事のコード書くのはアレなので、練習がてらGemを作ってみました。

続きを読む

2013年の振返りと2014年の目標

年末年始は久々に日本で過ごしていたのですけど、元旦から奥さんの膝が外れて救急病院に行ったり、NY行きのフライトが悪天候でキャンセルになって、サンフランシスコで16時間くらい待たされた挙げ句、バゲッジロストしたりと幸先悪い感じですが何とか生きてます。

続きを読む