18-6. 第1回ビネクラ杯 ―ドラゴンへの道―

ビネクラ杯

2019/09/04

やること
実行環境
用意するもの
考え方
コードを修正する
ルートを可視化する
まとめ

やること

前回は「ルートが見つからなかったら次を調べる」でスコア233が出ました。今回はさらなる工夫を追加して、スコア311以上（ドラゴンレベル）を目指しましょう。

実行環境

WinPython3.6をおすすめしています。

WinPython - Browse /WinPython_3.6/3.6.7.0 at SourceForge.net

Portable Scientific Python 2/3 32/64bit Distribution for Windows

用意するもの

18-4のコードを実装し、18-5の修正を加えておいてください。これをさらに書き換えます。

考え方

発電機と装置には、遠いペアと近いペアがあります。例えば、次のようなシステムはマンハッタン距離が８あるので、これらをつなぐと途中の７点は使えなくなってしまいます。

できるだけたくさんのシステムを繋ぎたいので、７点も死んでしまうのはもったい気がします。一方、次のようなシステムは距離が近いので、つないでもほとんど”死に座標”が生じません。

ですから、マンハッタン距離が短いシステムから順につなぐのが効率的なのです。

遠いシステムはいろいろなつなぎ方ができますから、先に短いケーブルをつないでしまって、長いケーブルにはそれらを避けてもらおうということでもあります。

コードを修正する

前回のコードの「メイン処理」のfor文に入る前に処理を加えます。4000システムのマンハッタン距離を計算して（＝manhattan_dist）、それが短い順のインデックス配列を取得します（＝manhattan_short_index）。

for文ではこのインデックス順に探索を行います。その後は変更ありません。

#============================
# メイン処理（マンハッタン距離が短い順につなぐ、経路が見つからなかったら飛ばして次を探索する）
#============================

#通った場所（Falseで初期化）
barrier = np.zeros((20, 20, 20), dtype=bool)

#記録用の配列
score = 0
routes = []

#4000システム（発電機と装置の）のマンハッタン距離を求める
manhattan_dist = np.sum(np.abs(equipments - generators), axis=1)
print('manhattan_dist:\n{}'.format(manhattan_dist))

#マンハッタン距離の短い順に添え字を取得
manhattan_short_index = manhattan_dist.argsort()
print('manhattan_short_index:\n{}'.format(manhattan_short_index))

#一応、マンハッタン距離順に並び替えて表示してみる
print('manhattan_short:\n{}'.format(manhattan_dist[manhattan_short_index]))

for i in manhattan_short_index:
    print(i)
    
    #これからつなぐスタートやゴールが、すでに障害物となっていたら終わり
    if barrier[generators[i, 0], generators[i, 1], generators[i, 2]] == True:
        continue
    if barrier[equipments[i, 0], equipments[i, 1], equipments[i, 2]] == True:
        continue

    #ルートを見つける
    route = find_route(barrier, generators[i], equipments[i])
    
    #ルートが見つからなかったら終わり
    if route is None:
        continue
    else: #ルートが見つかったら、スコアを記録する
        score += 1
        routes.append(route)

    #通った場所を障害物とする
    for [x, y, z] in route:
        barrier[x, y, z] = True

#
print('score:\n{}'.format(score))
#print('routes:\n{}'.format(routes))

manhattan_dist:
[22  3 12 ... 25 20 15]
manhattan_short_index:
[ 585 1268 2398 ... 2456 2199 3985]
manhattan_short:
[ 1  1  1 ... 46 47 48]
585
1268
2398
（中略）
2456
2199
3985
score:
470

マンハッタン距離は、先頭から順に [22, 3, 12, … , 25, 20, 15] とバラつきがあることがわかりました。これが短い順になるような添字配列は [585, 1268, 2398, … , 2456, 2199, 3985] となりました。一応、添字の順にマンハッタン距離を表示してみると、距離１（発電機と装置が隣り合っている）が数個あり、一方で、距離48のシステムがあることも分かります。

結果、なんとスコア470が出ました。いや、え、いや（動揺）