Calculate Islands (Scientific Expedition) - 島のサイズを調べよ

どんな問題？

Calculate Islands
http://www.checkio.org/mission/calculate-islands/

海に複数の島が浮かんでいる。
マップデータから、それぞれの島のサイズを調べよ。

引数のマップデータは、海が0、陸が1の list of list で渡される。
戻り値は、島のサイズを昇順で並べてリストとして返す。

陸地は縦横斜めに連結して島となる。
マップは、辺の長さが10未満の長方形。マップの外は、すべて海とみなす。
マップには少なくとも1つの島が含まれている。

例題：

checkio([
    [0, 0, 0, 0, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0]]) == [1, 3]
checkio([
    [0, 0, 0, 0, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 0, 0]]) == [5]
checkio([
    [0, 0, 0, 0, 0, 0],
    [1, 0, 0, 1, 1, 1],
    [1, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0]]) == [2, 3, 3, 4]

問題文の最後に、素集合データ構造(disjoint-set data structure)がなんたらかんたら、と書いてある。知らない専門用語が気になるが、まずは気にせずに解いてみる。

どうやって解く？

なんか、前にもよく似た問題があったような・・・。そうだ、Radiation searchと似てる。同じ考え方でやってみよう。

まず、マスごとに、探索済みかどうかのフラグを作る。あらかじめ、海は探索済みにしておく。
あとは、すべてのマスについて、

探索済みなら次へ
陸なら縦横斜めに探索を進め、陸続きの場所を探す。
探索が済んだら、マスの数を返す。

という流れになるかな。

ところで、CheckiOでは、自分の周辺8マスのデータを必要とする状況が多いのだが、なかなかベストな書き方が見つからない。今回は、こういうコードにしてみた。

import itertools
ADJACENT = {p for p in itertools.product([-1, 0, 1], repeat=2)} - {0, 0}

こうしておいて、

pts = [(x + p[0], y + p[1]) for p in ADJACENT]

とすれば、(x,y)の周辺8マスの座標が得られる。

Radiation searchでは、他の人の答えで、再帰呼び出しを使ってスマートに解いている人がいたので、今回、私も再帰を使って書いてみることにした。search()内からsearch()を呼び出している。

まとめ（再帰）

import itertools

ADJACENT = {p for p in itertools.product([-1, 0, 1], repeat=2)} - {0, 0}

def checkio(data):
    def search(x, y):
        if 0 <= x < w and 0 <= y < h and unchecked[y][x]:
            unchecked[y][x] = False
            return 1 + sum(search(x + p[0], y + p[1]) for p in ADJACENT)
        else:
            return 0

    h, w = len(data), len(data[0])
    unchecked = [[data[y][x] == 1 for x in range(w)] for y in range(h)]
    results = [search(x, y) for y in range(h) for x in range(w)]
    return sorted(r for r in results if r > 0)

http://www.checkio.org/mission/calculate-islands/publications/natsuki/python-3/first/

再帰って普段使わないから、なんか違和感がある。再帰を使わずにスタックを使ったコードがこちら。

まとめ（スタック）

import itertools

ADJACENT = {p for p in itertools.product([-1, 0, 1], repeat=2)} - {0, 0}

def checkio(data):
    def get_island_size(start):
        size = 0
        stack = [start]
        while stack:
            x, y = stack.pop()
            if 0 <= x < w and 0 <= y < h and unchecked[y][x]:
                unchecked[y][x] = False
                size += 1
                stack += [(x + p[0], y + p[1]) for p in ADJACENT]
        return size

    h, w = len(data), len(data[0])
    unchecked = [[data[y][x] == 1 for x in range(w)] for y in range(h)]
    pts = [(x, y) for y in range(h) for x in range(w)]
    result = [get_island_size(pt) for pt in pts]
    return sorted(r for r in result if r > 0)

http://www.checkio.org/mission/calculate-islands/publications/natsuki/python-3/second/

他の人の答え

さて、問題文にさらりと書いてあった「素集合データ構造」だが、少し調べてみた。
参考リンク

それを使っている解答がこちら。（コードが長いので引用はしない。）
http://www.checkio.org/mission/calculate-islands/publications/PositronicLlama/python-3/disjoint-set/
理解するには時間がかかりそうなので、詳しく見るのは、また後日にしておこう。

summer_tree_home

Check iOでPython3をマスターするぜっ