Buildings visibility (Mine) - 建物の投影図

どんな問題？

Buildings visibility
http://www.checkio.org/mission/buildings-visibility/

建物の配置データから、南側から見える建物の数を調べよ。

引数は、建物の配置データで、建物ごとに、座標(x1,y1,x2,y2)と高さがリスト形式で指定される。座標はintだが、高さはfloatなので注意。
戻り値は、南側から見える建物の数を返す。

建物は軸に平行に建っており、視野角などは考えない。（平行投影で正面図を表示させたイメージ）

例題：

checkio([
    [1, 1, 4, 5, 3.5],
    [2, 6, 4, 8, 5],
    [5, 1, 9, 3, 6],
    [5, 5, 6, 6, 8],
    [7, 4, 10, 6, 4],
    [5, 7, 10, 8, 3]
]) == 5 #"First"
checkio([
    [1, 1, 11, 2, 2],
    [2, 3, 10, 4, 1],
    [3, 5, 9, 6, 3],
    [4, 7, 8, 8, 2]
]) == 2 #"Second"
assert checkio([
    [1, 1, 3, 3, 6],
    [5, 1, 7, 3, 6],
    [9, 1, 11, 3, 6],
    [1, 4, 3, 6, 6],
    [5, 4, 7, 6, 6],
    [9, 4, 11, 6, 6],
    [1, 7, 11, 8, 3.25]
]) == 4 #"Third"

どうやって解く？

建物の座標は整数値なので、X=1のときに見える建物、X=2のときに見える建物、というようにX軸にそって調べていけばよさそうだ。

この例で言えば、

まず、X=nに存在する建物を調べる。例えば、

• X=1のときは、高さ3.5の建物
• X=2のときは、高さ3.5と5の建物
• X=5のときは、高さ6、8、3の建物

となる。

次に、南側から見える建物を数える。手前（南側）から順に建物の高さを調べて、手前より高い建物だけをカウントする。X=5のときは3つの建物があるが、南側から見えるのは、高さ6と8の建物の2つ。

まとめ

from collections import namedtuple

Building = namedtuple('Building', 'x1 y1 x2 y2 height')

def checkio(buildings):
    # 引数をBuildingのリストに変換
    bs = [Building(*b) for b in buildings]

    result = set()
    for x in range(min(b.x1 for b in bs), max(b.x2 for b in bs)):
        height = 0
        # 手前（南側）から順に高さをチェック
        for b in sorted([b for b in bs if b.x1 <= x < b.x2], key=lambda b: b.y1):
            # 前の建物より高ければ resultに追加
            if b.height > height:
                result.add(b)
                height = b.height
    return len(result)

http://www.checkio.org/mission/buildings-visibility/publications/natsuki/python-3/first/

他の人の答え

def checkio(b):
    def v(d,r=False,z={}):
        for x in range(d[0],d[2]):
            if d[4]>z.get(x,0): r,z[x]=True,d[4]
        return r
    return sum(map(v,sorted(b,key=lambda d: d[1])))

http://www.checkio.org/mission/buildings-visibility/publications/veky/python-3/closure/

最初、なんでこれで動くのかがよくわからなかったが、ポイントは引数の z={} だった。

Pythonのデフォルト引数は、最初に一度だけ初期化される仕様になっている。だから、デフォルト引数にmutableな値を指定しないのがお約束なんだが、この仕様を逆手にとってデフォルト引数をグローバル変数のように利用することもできる。

zは、最初に{}に初期化されて、あとは使い回されるので、これでうまく動くのだ。なるほどなぁ。