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

18-7. 第1回ビネクラ杯 ―ホルスへの道―

やること

皆さんは「(ホルス)」読めましたでしょうか。エジプト神話でもっとも偉い人です(人?)。「遊戯王をやっていれば読める」というコメントをいただきましたが、そういうアニメではなかったと思います…。ちなみに遊戯王の話ですが、三幻神を束ねた姿として、ホルスの一形態であるホルアクティが降臨し、「ジェセル。。(もぅマヂ無理。。)」と唱えると地平線の彼方まで尊い光が放たれ、大邪神ゾークが蒸発します。

さて、前回は驚きのスコア470に到達しました。しかし、天空と太陽の神に肩を並べるには、スコア485以上が必要です。今回はがんばって485を目指します

実行環境

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-6の発展型となります。

考え方

次の3つのシステムをつなぎたいとき、AとBを次のようにつないでしまうと、Cをつなげることができなくなります。

しかし、AとBを次のようにつなぐとどうでしょうか。Cのルートが確保されます。

これまでのfind_route関数には乱数の要素がありませんでしたので、何度実行しても上の図の状態になったかもしれません。しかし、新たに乱数の要素を追加すれば、この例では1/4の確率ではありますが、下の図の状態が出現する可能性がでてきます

神頼みは立派な戦略

サイコロを振りまくって、たまたま高いスコアが出たときの解答を採用すればよい。なんともパワープレイな発想です。そう、千手観音ならサイコロを1000個同時に振れる!

現在はCPUのマルチコア化が進んでおり、一般消費者向けにもかかわらず12コア/24スレッドのCPUも発売されています。(あまり語ると趣味がバレそうなので自粛)

AMD Ryzen 9 3900X BOX スペック・仕様
■最安価格(税込):価格情報の登録がありません ■価格.com売れ筋ランキング:-位 ■満足度レビュー:4.91(147人) ■クチコミ:1484件 (※3月17日時点)

だから、乱数シードを変えながら24スレッドでガンガン探索すれば、今は470だけどたまたま485以上のスコアが出るかもしれない。これも立派な戦略なのです。

乱数要素を加える修正

乱数を用いるため、importに次を追加します。

import numpy.random as nr

次に、find_route関数の後半の部分(ゴールから逆順にたどって経路をあぶり出す部分)に乱数を導入します。来た可能性がある方向をすべてチェックし、previous = [‘x-‘, ‘y+’, ‘y-‘] のようにメモしておきます。そしてサイコロを振り、どの方向を採用するかを決めます。

#============================
# ひとつのルートを見つける関数
#============================
def find_route(barrier, start, goal):
    #########################
    # 前処理
    #########################
    (中略)
    
    #########################
    # 幅優先探索
    #########################
    (中略)
    
    #++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    # 【追加】 ここで一旦終了判定、ゴールのコストが999であれば、ルートが見つかっていないので強制終了
    #++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    (中略)
    
    #########################
    # ゴールから逆順でルート計算
    #########################
    point_now = goal
    cost_now = cost[goal[0], goal[1], goal[2]]
    route = [goal]
    #print('route\n{}'.format(route))
    while cost_now > 0:
        #来た可能性がある方向をすべてチェックする
        previous = []
        
        #x-から来た?
        try:
            if cost[point_now[0] - 1, point_now[1], point_now[2]] == cost_now - 1 and point_now[0] != 0:
                previous.append('x-')
        except: pass
        #x+から来た?
        try:
            if cost[point_now[0] + 1, point_now[1], point_now[2]] == cost_now - 1:
                previous.append('x+')
        except: pass
        #y-から来た?
        try:
            if cost[point_now[0], point_now[1] - 1, point_now[2]] == cost_now - 1 and point_now[1] != 0:
                previous.append('y-')
        except: pass
        #y+から来た?
        try:
            if cost[point_now[0], point_now[1] + 1, point_now[2]] == cost_now - 1:
                previous.append('y+')
        except: pass
        #z-から来た?
        try:
            if cost[point_now[0], point_now[1], point_now[2] - 1] == cost_now - 1 and point_now[2] != 0:
                previous.append('z-')
        except: pass
        #z+から来た?
        try:
            if cost[point_now[0], point_now[1], point_now[2] + 1] == cost_now - 1:
                previous.append('z+')
        except: pass
        
        #サイコロを振る
        dice = nr.randint(len(previous))
        #サイコロで出た方向を採用する
        direction = previous[dice]
        
        #その方向にトレースバック
        if direction == 'x-':
            #更新
            point_now = (point_now[0] - 1, point_now[1], point_now[2])
            cost_now = cost_now - 1
            #記録
            route.append(point_now)
            continue
        if direction == 'x+':
            point_now = (point_now[0] + 1, point_now[1], point_now[2])
            cost_now = cost_now - 1
            route.append(point_now)
            continue
        if direction == 'y-':
            point_now = (point_now[0], point_now[1] - 1, point_now[2])
            cost_now = cost_now - 1
            route.append(point_now)
            continue
        if direction == 'y+':
            point_now = (point_now[0], point_now[1] + 1, point_now[2])
            cost_now = cost_now - 1
            route.append(point_now)
            continue
        if direction == 'z-':
            point_now = (point_now[0], point_now[1], point_now[2] - 1)
            cost_now = cost_now - 1
            route.append(point_now)
            continue
        if direction == 'z+':
            point_now = (point_now[0], point_now[1], point_now[2] + 1)
            cost_now = cost_now - 1
            route.append(point_now)
            continue
    
    #ルートを逆順にする
    route = route[::-1]
    #print('route\n{}'.format(route))
    
    return route

メイン処理の修正

「メイン処理」の冒頭で乱数シードを指定するだけです。

#============================
# メイン処理(乱数シードを固定して、マンハッタン距離が短い順につなぐ、経路が見つからなかったら飛ばして次を探索する)
#============================

#乱数の固定
seed = 0
nr.seed(seed)

#通った場所(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:
475

とりあえず乱数シード0で実行してみたところ、スコア475が出ました。前回の470をあっさりと更新してしまったのです。

サイコロを振りまくる

乱数シードを0~99まで試してみました。(もちろんRyzen 9 でやったわけではないです…)

seed:0 score:475
seed:1 score:473
seed:2 score:469
seed:3 score:483
seed:4 score:471
seed:5 score:478
seed:6 score:473
seed:7 score:470
seed:8 score:478
seed:9 score:473
seed:10 score:469
seed:11 score:471
seed:12 score:474
seed:13 score:478
seed:14 score:478
seed:15 score:469
seed:16 score:478
seed:17 score:475
seed:18 score:476
seed:19 score:478
seed:20 score:476
seed:21 score:482
seed:22 score:472
seed:23 score:473
seed:24 score:476
seed:25 score:471
seed:26 score:478
seed:27 score:458
seed:28 score:479
seed:29 score:465
seed:30 score:474
seed:31 score:467
seed:32 score:465
seed:33 score:481
seed:34 score:472
seed:35 score:469
seed:36 score:473
seed:37 score:473
seed:38 score:465
seed:39 score:476
seed:40 score:475
seed:41 score:472
seed:42 score:482
seed:43 score:473
seed:44 score:470
seed:45 score:477
seed:46 score:486 # over 485!
seed:47 score:475
seed:48 score:475
seed:49 score:469
seed:50 score:471
seed:51 score:477
seed:52 score:473
seed:53 score:484
seed:54 score:477
seed:55 score:485 # over 485!
seed:56 score:471
seed:57 score:475
seed:58 score:473
seed:59 score:481
seed:60 score:477
seed:61 score:474
seed:62 score:470
seed:63 score:475
seed:64 score:470
seed:65 score:470
seed:66 score:468
seed:67 score:478
seed:68 score:480
seed:69 score:473
seed:70 score:478
seed:71 score:473
seed:72 score:469
seed:73 score:474
seed:74 score:473
seed:75 score:471
seed:76 score:469
seed:77 score:471
seed:78 score:486 # over 485!
seed:79 score:475
seed:80 score:473
seed:81 score:474
seed:82 score:473
seed:83 score:473
seed:84 score:469
seed:85 score:471
seed:86 score:477
seed:87 score:478
seed:88 score:479
seed:89 score:475
seed:90 score:480
seed:91 score:482
seed:92 score:482
seed:93 score:472
seed:94 score:469
seed:95 score:466
seed:96 score:474
seed:97 score:472
seed:98 score:483
seed:99 score:479

ということで、3回も485以上が出ました。seed=46, score=486 のグラフがこちらです。

show_routes(routes)

キタ━━━(゚∀゚)━━━!!(3回目)

無事に天空と太陽の神になることができました。

感想

通常の競技プログラミングでは、例えば「6秒以内」というように実行時間が指定されています。ビネクラ杯は、制限時間が1ヶ月ですので、秋葉原でPCパーツを買って組むところから始めたり、1週間くらいダラダラとサイコロを振り続けたり、いろいろなアプローチができます。プログラミングはもっと自由であるべきだ。と、大きな子どもは考えています。

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