Xs and Os Referee (Check iO > Home)

Xs and Os Referee
http://www.checkio.org/mission/x-o-referee/

問題の前に…

いまさらだが、Check　iO なのか CheckiO なのかどっちなんだ？サイトのロゴ画像では「Check」と「iO」の間にスペースが入ってるように見えるけど、サイトの文章ではCheckiOで統一されているみたいだ。

どんな問題？

いわゆる、○×ゲーム（三目並べ）の譜面を見て、どっちが勝ちかを判断する。英語では Tic-Tac-Toe とか Xs and Os と言うらしい。ルールはみんなが知っている通り、縦・横・斜めで3つ揃った方が勝ちというものだ。

譜面は、["XOX", "XX.", "O.X"] という形式で渡される。「.」は空きマスを意味する。戻り値は、Xが勝ちなら"X"、Oが勝ちなら"O"、引き分けなら"D"を返す。

例はこちら

checkio([
    "X.O",
    "XX.",
    "XOO"]) == "X", "Xs wins"
checkio([
    "OO.",
    "XOX",
    "XOX"]) == "O"
checkio([
    "OOX",
    "XXO",
    "OXX"]) == "D"

どうやって解く？

縦横斜めを順番に調べても、3+3+2で8回チェックすればいいんだから、そんな手間ではない。

def checkio(game_result):
    def get(x, y):
        return game_result[y][x]

    def check_line(p1, p2, p3):
        return get(*p1) == get(*p2) == get(*p3) != '.'

    # 横
    for yy in range(3):
        if check_line((0, yy), (1, yy), (2, yy)):
            return get(0, yy)
    # 縦
    for xx in range(3):
        if check_line((xx, 0), (xx, 1), (xx, 2)):
            return get(xx, 0)
    # 斜め
    if check_line((0, 0), (1, 1), (2, 2)):
        return get(0, 0)
    if check_line((2, 0), (1, 1), (0, 2)):
        return get(2, 0)

    return 'D'

引数(game_result)は、list of string なので、簡単に x,yの座標でアクセスできるように関数get()を定義しておいた。

クリアはしたものの、全体的にちょっと冗長な感じがする。
そして、気になるのが、引数が ['XXX','OOO','XOX'] のようなケース。OとXの両方が揃っている場合はどうすればいいんだろう？
上のコードでは、yy=0から順にチェックするため、Xが勝者となってしまう。

もちろん、実際の○×ゲームで ['XXX','OOO','XOX'] という結果はありえない。ただし、そういうありえない譜面が渡されたときに、Xが勝者です、としてしまっていいんだろうか？

ゲームなんだから、与えられた条件だけ考えればいいんだとも思うけれど、あえて ['XXX','OOO','XOX'] にも配慮したコードを書いてみることにした。Oが勝ち、Xが勝ち、引き分け、判断不可 の4パターンを区別できるようにしたい。そのためには、縦横斜め、すべてを調べてから結果を判断する。書いてみたコードはこちら。

def checkio(game_result):
    def get(p):
        return game_result[p % 3][p // 3]

    def get_line_winner(p1, p2, p3):
        if get(p1) == get(p2) == get(p3) != '.':
            return get(p1)  # 'X' or 'O'
        else:
            return None

    lines = [(0, 1, 2), (3, 4, 5), (6, 7, 8),  # 横の線
             (0, 3, 6), (1, 4, 7), (2, 5, 8),  # 縦の線
             (0, 4, 8), (2, 4, 6)]  # 斜めの線

    winners = {p for p in [get_line_winner(*l) for l in lines] if p is not None}

    if len(winners) == 1:
        return list(winners)[0]
    elif len(winners) == 2:
        return 'D'
    else:
        return 'D'

まず、get(x,y) は座標指定が面倒なので、get(p) という形にしておいた。
3x3のマスを左上から順に0～8で指定する。[[0,1,2],[3,4,5],[6,7,8]]

次に、縦・横・斜めのラインを8本定義する。各ラインごとに勝者を調べてリストを作成、Noneを除いて、set化して重複を削除する。

winnersが {} なら、引き分け。
{'X'} または {'O'} のように要素が1つであれば、それが勝者。
そして、{'X', 'O'} のように複数の勝者があれば、 ['XXX','OOO','XOX'] のような判断不可タイプということだ。とりあえず 'D' を返しているが、例外発生させてもいい。

見直してみると、なんだかやっぱり冗長だ。
Noneを除去するためだけに内包表記を2重にしているのも無駄だし、setから1要素を取り出すところの list(winners)[0] も美しくない。

setについて調べてみると、要素を削除するには、.discard() を使うらしい。set同士の引き算 {a,b,c} - {a} という書き方もできるようだ。
setから1要素を取り出すときは、.pop() を使う。

最終的にこうなった。

def checkio(game_result):
    def get(p):
        """
        p is position
        0 1 2
        3 4 5
        6 7 8
        """
        return game_result[p % 3][p // 3]

    def get_line_winner(p1, p2, p3):
        if get(p1) == get(p2) == get(p3) != '.':
            return get(p1)  # 'X' or 'O'
        else:
            return None

    lines = [
        # horizontal
        (0, 1, 2), (3, 4, 5), (6, 7, 8),
        # vertical
        (0, 3, 6), (1, 4, 7), (2, 5, 8),
        # diagonal
        (0, 4, 8), (2, 4, 6)]

    winners = {get_line_winner(*l) for l in lines} - {None}

    if len(winners) == 1:  # {'X'} or {'O'}
        return winners.pop()
    elif len(winners) == 2:  # {'X', 'O'}
        # such as ['XXX','OOO','XOX']
        return 'D'  # or raise exception
    else:
        return 'D'

公開用に、なんちゃって英語でコメントも付けてみた。
あいまいな問題への皮肉を込めて、「or raise exception」って書いておいた。

linesの定義部分はもうちょっとスマートにできそうだが、まあいいか。これで公開しておく。

修正

公開後にミスに気づいた！

    def get():
        return game_result[p % 3][p // 3]

ここ間違えてる。正しくは↓

    def get():
        return game_result[p // 3][p % 3]

他の人の答え

今日は疲れたので、他の人の解答を見るのは、また後日。