Bats Bunker (O'Reilly) - コウモリ間の伝達

どんな問題？

Bats Bunker
http://www.checkio.org/mission/bats-bunker/

バンカーには、コウモリが多数いる。
入口（座標0,0）から、ボスコウモリまで、警報が伝達する最短時間を求めよ。
コウモリ間は直線でつながっていれば伝達が可能。壁を通り抜けての伝達はできない。
伝達時間は距離に比例し、隣のセルまでの伝達時間は1秒とする。

入口にボスコウモリがいる場合もある。
マップの幅と高さは、3以上7以下
ボスコウモリは1匹だけ

引数は、マップのデータ。Wが壁、Bが斥候コウモリ、Aがボスコウモリとなる。
戻り値は、最小の伝達時間を小数点2桁で返す。

例題：

checkio([
    "B--",
    "---",
    "--A"]) == 2.83
checkio([
    "B-B",
    "BW-",
    "-BA"]) == 4
checkio([
    "BWB--B",
    "-W-WW-",
    "B-BWAB"]) == 12
checkio([
    "B---B-",
    "-WWW-B",
    "-WA--B",
    "-W-B--",
    "-WWW-B",
    "B-BWB-"]) == 9.24

どうやって解く？

重み付きのグラフ探索というやつかな。アルゴリズムの本によると、重みが負でない場合の最短経路探索は「ダイクストラのアルゴリズム（ダイクストラ法）」を使えばいいらしい。

初期設定

引数のマップ情報を、使いやすいよう辞書に変換しておく。

map_data = {(x, y): c for y, line in enumerate(bunker) for x, c in enumerate(line)}

さらに、すべてのコウモリ（斥候とボス）の位置をsetにしておく。

bats = {k for k, v in map_data.items() if v in 'AB'}

コウモリ間の伝達が可能かどうかを判定

コウモリaからコウモリbに伝達可能かどうかを判定する方法だが、線分abが横切るセルをリストアップして、そのセルに壁がなければ、伝達可能と判断することにした。

問題は「線分abが横切るセルをリストアップ」という部分。ab間は、壁でふさがれていなくても、下記のように壁の角が接しているだけでも、伝達はできない。

ａ■
□ｂ

ａ■□
□□ｂ

ａ□□
□■ｂ

あれこれ考えて、線分abを、点aからbに向けて、xを0.5ずつずらしていき、x,yの値によって、どのセルを横切るかを調べていくことにした。
f:id:summer_tree:20140407122317p:plain
例えば、右の図では、a=(0,0)、b=(2,1)なので、線分abの経過点は (0.5, 0.25)、(1, 0.5)、(1.5, 0.75) の3つある。ここから、

(0.5, 0.25) → (0, 0)、(1, 0)にヒット
(1, 0.5) → (1, 0)、(1, 1)にヒット
(1.5、0.75) → (1, 1)、(2, 1)にヒット

と判断する。つまり、値が0.5なら0と1の両方、それ以外なら0.25なら0、0.75なら1のように、丸めればいい。

コードはこちら。0.5刻みで動かすため、先にrange_float()関数を定義している。

def range_float(start, stop, step):
    # range()の浮動小数点版
    while start < stop:
        yield start
        start += step

def get_cells_on_line(a, b):  
    # 線分abが横切るセルの座標をsetで取得
    (x1, y1), (x2, y2) = a, b
    result = set()
    delta = max(abs(x2 - x1), abs(y2 - y1))  # xの差分とyの差分の大きい方
    for i in range_float(0.5, delta, 0.5):   # 0.5刻みで動かす
        x = x1 + (x2 - x1) * i / delta
        y = y1 + (y2 - y1) * i / delta
        xs = [int(x), int(x) + 1] if x % 1.0 == 0.5 else [round(x)]  # 例えば、2.5なら2と3の両方
        ys = [int(y), int(y) + 1] if y % 1.0 == 0.5 else [round(y)]
        result |= set(itertools.product(xs, ys))
    return result - {a, b}  # セルa,bを除外

浮動小数点を == で比較している点が気になるが、、、。

これで、コウモリaからコウモリbに伝達可能かどうかを判定する部分はこうなる。

    def is_connected(a, b):
        return all(map_data[pt] not in 'W' for pt in get_cells_on_line(a, b))

ダイクストラ法(Dijkstra)

アルゴリズムの本によると、ダイクストラ法では、A*と同じようにヒープキュー（優先度付きキュー）を使う。A*ではゴールまでの距離の推定値を使うが、ダイクストラ法ではスタートからの距離を使う、という違いのようだ。

Pythonでヒープキューを使うには、heapqモジュールを使う。
ヒープキューに、(スタートからの距離、現在位置、訪問済みの頂点)を入れる。
heappop()で、スタートからの距離が短い順にキューから取り出す。

    heap = [(0, (0, 0), {(0, 0)})]  # (length, pos, visited)
    while heap:
        length, pos, visited = heapq.heappop(heap)
        if map_data[pos] == 'A':
            # Aに到達したらゴール
            return round(length, 2)
        for bat in bats - visited:
            if is_connected(pos, bat):
                # 未訪問で伝達可能なコウモリがあれば、ヒープキューに追加
                new_length = length + get_length(pos, bat)
                heapq.heappush(heap, (new_length, bat, visited | {bat}))

まとめ

import itertools
import heapq

def range_float(start, stop, step):
    while start < stop:
        yield start
        start += step

def checkio(bunker):
    def get_length(a, b):
        return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5

    def get_cells_on_line(a, b):
        (x1, y1), (x2, y2) = a, b
        result = set()
        delta = max(abs(x2 - x1), abs(y2 - y1))
        for i in range_float(0.5, delta, 0.5):
            x = x1 + (x2 - x1) * i / delta
            y = y1 + (y2 - y1) * i / delta
            xs = [int(x), int(x) + 1] if x % 1.0 == 0.5 else [round(x)]
            ys = [int(y), int(y) + 1] if y % 1.0 == 0.5 else [round(y)]
            result |= set(itertools.product(xs, ys))
        return result - {a, b}

    def is_connected(a, b):
        return all(map_data[pt] not in 'W' for pt in get_cells_on_line(a, b))

    map_data = {(x, y): c for y, line in enumerate(bunker) for x, c in enumerate(line)}
    bats = {k for k, v in map_data.items() if v in 'AB'}

    heap = [(0, (0, 0), {(0, 0)})]  # (length, pos, visited)
    while heap:
        length, pos, visited = heapq.heappop(heap)
        if map_data[pos] == 'A':
            return round(length, 2)
        for bat in bats - visited:
            if is_connected(pos, bat):
                new_length = length + get_length(pos, bat)
                heapq.heappush(heap, (new_length, bat, visited | {bat}))

http://www.checkio.org/mission/bats-bunker/publications/natsuki/python-3/first/

なかなか難しかったが、なんとかクリア。

やっぱり浮動小数点の == が気になる。

x % 1.0 == 0.5

これは、

abs(x % 1.0 - 0.5) < 0.0001

こうしたほうが良かったかな。（しかし、適切な誤差ってどれくらいだろう？）

（追記）
get_length()のところは、math.hypotを使えばよかった・・・。

summer_tree_home

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