4/14(日) 足・靴・木型研究会「第2回研究集会」を開催します☆彡

18-5. 第1回ビネクラ杯 ―総書記への道―

やること

8月を通して開催された「第1回ビネクラ杯」が終わりました。16名の方が解答を提出してくださり、約半数の方々が最上位レベルに到達されているので驚きました。今回はスコア151以上(総書記レベル)のコードを書いてみましょう。

総書記とは?な方は問題編の「達成目標」をご参照ください。

実行環境

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-4の記事では、システム(発電機と装置)をNo.1から順番につないで、これ以上つなげなくなったところでfor文を中断(break)しました。その結果、18番目のシステムをつなぐ際にbreakが発生し、それまでにつなげた17システムがスコアとなりました。繰り返しがbreakしてしまう条件は2つあります。

  1. これからつなごうとする発電機または装置の座標にすでにケーブルが通っていた(barrier[x, y, z] == True になっていた)
  2. 発電機と装置をつなごうとしたが、ルートが見つからなかった(find_route() から None が返ってきた)

スコア17を可視化したグラフを見ると、

フィールドはスカスカですので、条件2で終了したとは考えにくいです。なぜなら、遠回りすればいくらでもルートが見つかりそうですから。よってこれくらいのスコア帯では、条件1で終了することが多いと考えられます。

一方で、よりたくさんのケーブルが詰め込まれてギチギチになると、条件2に引っかかるケースもあるかもしれません。

そこで今回は、終了条件に引っかかってもbreakせず、「そのシステムは飛ばして次のシステムを調べる」を実装します。

コードを修正する

前回のコードの「メイン処理」の部分を書き換えます。といっても、実は3箇所あるbreakcontinueに書き換えるだけで済みます。breakは「for文を中断する」コマンドでしたが、continueは「このループを中断し次のループを開始する」コマンドです。ですから、i=17でcontinueに引っかかったらそれ以降の処理をすっ飛ばしてi=18のループが始まります。

#============================
# メイン処理(経路が見つからなかったら飛ばして次を探索する)
#============================
    
#通った場所(Falseで初期化)
barrier = np.zeros((20, 20, 20), dtype=bool)

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

#find_route中の最大探索ステップ数を99に減らておきます

for i in range(4000):
    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))
0
1
2
(中略)
3997
3998
3999
score:
233

「これがダメなら次のシステムを…」ということで4000システムすべてが調べられ、なんと、スコア233が出てきました。いや、本当でしょうか。(routesはあまりにも多いので非表示にしておきました)

ルートを可視化する

前回のshow_routes関数を用いて可視化します。

show_routes(routes)

キタ━━━(゚∀゚)━━━!!

まとめ

わずか3箇所を書き換えるだけでスコアが17→233にまで向上しました。これぞプログラミングの醍醐味だと思いました。これで皆さん「総書記」レベルです!

余談ですが、なぜ「総書記」が偉いのかと知人に尋ねたところ、「書記は議事録を好き勝手に書き換えられるから」とのことでした。嘘か真か…

タイトルとURLをコピーしました