!!! サイト改修中のため表示が乱れる場合があります(1月末頃まで) !!!
未分類

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にまで向上しました。これぞプログラミングの醍醐味だと思いました。これで皆さん「総書記」レベルです!

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

リアクションのお願い

「参考になった!」「刺激された!」と思ったらぜひリアクションをしましょう。エンジニアの世界はGive and Takeによって成り立っています。これからも無料で良質な情報にアクセスできるよう、Giveする人への感謝をリアクションで示しましょう!

この記事をシェアする

自身のブログ等で使用する場合は引用を忘れずに!

また、寄付も受け付けています。コーヒー1杯でとても喜びます(*˘︶˘*)

 Amazonでギフト券(アマギフ)を贈る

こちらのリンク から金額を指定してお贈りください。(デフォルトで10000円になっているのでご変更ください)

配送:Eメール
受取人:staffあっとvigne-cla.com
贈り主:あなたのお名前やニックネーム
メッセージ:◯◯の記事が参考になりました。など

のようにご入力ください。見返りはありませんのでご了承ください。

 Amazonで食事券(すかいらーく優待券)を贈る

500円 1000円 2000円 5000円 からお贈りください。

配送:Eメール
受取人:staffあっとvigne-cla.com
贈り主:あなたのお名前やニックネーム
メッセージ:◯◯の記事が参考になりました。など

のようにご入力ください。見返りはありませんのでご了承ください。

 その他、ギフト券やクーポン券をメールで贈る

デジタルのギフト券/クーポン券はメールアドレス(staffあっとvigne-cla.com)までお送りください。受領の返信をいたします。
紙のギフト券/クーポン券は 「郵便物はこちらへ」の住所 まで送付してください。名刺やメールアドレスを同封していただければ受領の連絡をいたします。
余った株主優待券等の処理におすすめです。
いずれも見返りはありませんのでご了承ください。

不明点はSNSでお気軽にご連絡ください

ビネクラのTwitter・Youtubeでコメントをください!


Slack・Discordの場合はこちらの公開グループに参加してShoya YasudaまでDMをください!


※当ブログに関することは何でもご相談・ご依頼可能です。

この記事を書いた人
Yasuda

博士(理学)。専門は免疫細胞、数理モデル、シミュレーション。米国、中国で研究に携わった。遺伝的アルゴリズム信者。物価上昇のため半額弁当とともに絶滅寸前。

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