The square chest (Scientific Expedition) - 正方形の数を数えよ

どんな問題？

The square chest
http://www.checkio.org/mission/the-square-chest/

No.1～16までの点があり、隣り合う点と点のいくつかは線で結ばれている。
これらの線で構成された正方形の数を数えよ。

文章で説明するより、説明文の図を見た方がわかりやすいだろう。

引数は、点と点を結ぶ線のリストで、[1,2]なら、点1と点2を結ぶ線となる。
戻り値は、線のリストから作られる正方形の数を返す。

例題：

checkio([[1, 2], [3, 4], [1, 5], [2, 6], [4, 8], [5, 6], [6, 7],
     [7, 8], [6, 10], [7, 11], [8, 12], [10, 11],
     [10, 14], [12, 16], [14, 15], [15, 16]]) == 3
checkio([[1, 2], [2, 3], [3, 4], [1, 5], [4, 8],
     [6, 7], [5, 9], [6, 10], [7, 11], [8, 12],
     [9, 13], [10, 11], [12, 16], [13, 14], [14, 15], [15, 16]]) == 2

どうやって解く？

全体のサイズは固定のようなので、作成できる正方形の数は限られていそうだ。
1x1の正方形が9個、2x2の正方形が4個、3x3の正方形が1個で、合計14個しかない。
だったら、正方形14個すべてをチェックするのが手っ取りばやいかな。

あらかじめ14個の正方形について、含まれる線分を定義しておいて、引数にその線分が含まれていれば、正方形が成立することになる。

例えば、点1,2,5,6から成る正方形なら

[[1,2],[1,5],[2,6],[5,6]]

が、線分リストとなる。
サイズが1x1の正方形は簡単だが、2x2になると線は8本になるので、少しやっかいだ。

正方形の左上の座標(x,y)と辺の長さ(length)から、線分リストを作成する関数を作った。

    def get_no(x, y):
        return y * 4 + x + 1

    def get_square_lines(x, y, length):
        for i in range(length):
            yield get_no(x, y + i), get_no(x, y + i + 1)  # left lines
            yield get_no(x + length, y + i), get_no(x + length, y + i + 1)  # right lines
            yield get_no(x + i, y), get_no(x + i + 1, y)  # top lines
            yield get_no(x + i, y + length), get_no(x + i + 1, y + length)  # bottom lines

1x1、2x2、3x3の正方形（合計14個）の線分リストを作成する。

    squares = [set(get_square_lines(x, y, 1)) for y in range(3) for x in range(3)]  # 1x1 squares
    squares += [set(get_square_lines(x, y, 2)) for y in range(2) for x in range(2)]  # 2x2 squares
    squares += [set(get_square_lines(0, 0, 3))]  # 3x3 square

あとから、引数のリストと比較することを考えて、listではなくsetにしておいた。

まとめたのがこちら

def get_all_squares():
    def get_no(x, y):
        return y * 4 + x + 1

    def get_square_lines(x, y, length):
        for i in range(length):
            yield get_no(x, y + i), get_no(x, y + i + 1)  # left lines
            yield get_no(x + length, y + i), get_no(x + length, y + i + 1)  # right lines
            yield get_no(x + i, y), get_no(x + i + 1, y)  # top lines
            yield get_no(x + i, y + length), get_no(x + i + 1, y + length)  # bottom lines

    squares = [set(get_square_lines(x, y, 1)) for y in range(3) for x in range(3)]  # 1x1 squares
    squares += [set(get_square_lines(x, y, 2)) for y in range(2) for x in range(2)]  # 2x2 squares
    squares += [set(get_square_lines(0, 0, 3))]  # 3x3 square
    return squares

SQUARES = get_all_squares()

def checkio(lines_list):
    lines_set = set(tuple(line) for line in lines_list)  # 比較用に、引数をset of tupleに変換
    return len([sq for sq in SQUARES if sq <= lines_set])  # 引数に含まれる正方形を数える

あらかじめSQUARESという定数を作っておく。
メイン部分(checkio)では、引数に含まれている正方形の数を数えているだけだ。

sq <= lines_set

は

sq.issubet(lines_set)

と同じで、部分集合かどうかを判定できる。（これを使うためにsetに変換したのだ。）

さくっと実行～

FAIL
Your answer: 0
Right answer: 3
checkio([[16,15],[16,12],[15,11],[11,12],[11,10],[10,14],[9,10],[14,13],[13,9],[15,14]])

えっ、なんで？
引数をよく見たら、

[16,15]
[14,13]

のように、順番が逆になっているものが含まれるじゃないか。想定してなかった。

なら、引数をset of tupleに変換するときに、sorted()しておこう。
（または、tupleじゃなくfrozensetを使ってもいいかも。）

def checkio(lines_list):
    lines_set = set(tuple(sorted(line)) for line in lines_list)
    return len([sq for sq in SQUARES if sq <= lines_set])

これで無事にクリア＆公開
http://www.checkio.org/mission/the-square-chest/publications/natsuki/python-3/first/