最速の並び順を考える~東邦連峰~

## 経緯
### 東方連峰とは

母校駒場東邦の体育祭は毎年とても盛り上がる。特に高校生全体競技「東邦連峰」の迫力は凄まじく、駒東の体育祭を代表する競技と言って良い。


<iframe width="560" height="315" src="https://www.youtube.com/embed/gzfbu4l3cbE" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>


この競技は20人の走者が順に4つある竹のどれかに登り、全員が戻ってくるまでの時間を競うリレー形式の競技である。競技が始まると4人の走者が同時に別々の竹へ向かう。そして登り終え戻ってきた走者は次の人へバトンタッチし、その人は空いている竹へ向かう。（下図参照）

![S__12156930.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2952141/966b390c-7490-6b86-7d3e-4caa653588c9.jpeg)
(この場合次走者は手前から3個目の竹を登ることになるだろう）
これを繰り返してタイムを競うのが東邦連峰である。

### 並び順が重要！！
この競技では経験的に「手前の竹にできるだけ多くの人を登らせる」という戦略が強いということが知らされていた。一番奥の竹までは30mほどあり、1番の奥の竹に向かった人がもどってくるまでに、手前の竹に2人が登り切ることもある。(最終的に手前の竹ばっかりに人が登ってもペナルティはない）。走るスピードは人によって大差ないが、登るスピードはかなりの差がある。もし登るのが遅い人が手前の竹を占有すると勿体無いのだ。並び順は誰がどこに登るかを決めるため、練習のタイムをもとにどのような並び順が最適化知っておきたいわけである。

さて今回は僕らが高校生の時に行った作戦がランダムの並び順と比べてどれぐらい早かったのかを計算する。総当たりではやはり20人の並び順は扱えなかったので、今回は9人の場合を確認した。

### 作戦
実際の東邦連峰では最後の4人(17人目~20人目）は少し特殊である。17人目は16人目が帰ってくるまで(自分より前の人が全員帰ってくるまで)待ってからスタートし、一番手前の竹に旗を掲げる。その後18人目は17人目が帰ってくるまで待ってからスタートし、手前から2個目の竹に旗を掲げる。....これを繰り返し全ての竹に旗が掲げられ、20人目が戻ってくると完走である。

私たちの作戦は「手前の棒に早いやつをどんどん入れる＋最後4人は最強4人」だった。これをコード上で再現してみる。

### 最強の4人の選び方
1\. 各メンバーの各竹を登らせた時のタイムを出す。
2\. 各竹の上位4人を選出する。
3\. それぞれの竹の上位4人のうち1人選び、仮の最強4人を作る（メンバーがかぶる場合は無視する）
4\. 仮の最強4人のタイムの最速を出す4人を真の最強の4人とする。

### 手前の棒に早いやつをどんどん入れる
一番手前の竹から戻ってきた時
=>まだ登っていない人のうち一番早い人が登る
一番手前の竹以外から戻ってきた時
=>まだ登っていない人のうち一番遅い人が登る


### コード
```python
import queue
import matplotlib.pyplot as plt
import pandas as pd
import numpy as np
import itertools
import copy
class Touhou:
    def __init__(self):
        self.data=[]

    def importdata(self,runtime,climbtime):
        #走り込みから降りるまで、一区間を走る時間、ID
        self.data.append([climbtime,runtime,len(self.data)])

    def strategy_1(self):#手前の棒に早いやつをどんどん入れる＋最後4人は最強4人
        order_by_speed=queue.PriorityQueue()
        last4=self.strategy_1_last_4_member()
        for i in last4:
            order_by_speed.put(i)
        for i in self.data:
            if not i in last4:
                order_by_speed.put(i)
        runorder=[]
        while not order_by_speed.empty():
            runorder.append(order_by_speed.get())
        return self.checktime_strategy_1(runorder)

    def fastest(self):#すべての場合を比較、20人とかは無理
        allorder = list(itertools.permutations(self.data))
        fasttime=float("inf")
        for onedata in allorder:
            time=self.checktime(list(onedata))
            if time<fasttime:
                fasttime=time
        return fasttime
        pass

    def checktime(self,runorder):
        climbing=queue.PriorityQueue()
        for where in range(4):
            runner=runorder.pop(0)
            #走り込みから降りるまで＋2＊どこいくか＊一区間を走る時間
            runtime=runner[0]+runner[1]*2*where
            #かかる時間、どこ登るか、走り込みから降りるまで、一区間を走る時間、ID
            alldata=[runtime,where]+runner
            climbing.put(alldata)
        Time=0
        while not len(runorder)==4:
            goal=climbing.get()#goalした人のalldata
            Time=goal[0]
            runner=runorder.pop(0)
            runtime=Time+runner[1]*goal[1]*2+runner[0]#出発時間＋往復＋登る時間
            alldata=[runtime,goal[1]]+runner
            climbing.put(alldata)
        while not climbing.empty():#でかい旗前
            goal=climbing.get()
            Time=goal[0]
        for where in range(4):#でかい旗
            runner=runorder.pop()
            Time+=runner[1]*where*2+runner[0]#出発時間＋往復＋登る時間
        return Time
        pass

    def checktime_strategy_1(self,runorder):
        climbing=queue.PriorityQueue()
        ansorder=[]
        runner=runorder.pop(4)#一人目
        #かかる時間、どこ登るか、走り込みから降りるまで、一区間を走る時間、ID
        alldata=[copy.deepcopy(runner[0]),0]+copy.deepcopy(runner)
        climbing.put(alldata)
        for where in range(1,4):
            runner=runorder.pop()
            #走り込みから降りるまで＋2＊どこいくか＊一区間を走る時間
            runtime=runner[0]+runner[1]*2*(where)
            #到着時刻、どこ登るか、走り込みから降りるまで、一区間を走る時間、ID
            alldata=[copy.deepcopy(runtime),where]+copy.deepcopy(runner)
            climbing.put(alldata)
        #ここまでok
        Time=0
        while True:
            goal=climbing.get()#goalした人のalldata
            print(goal)
            Time=copy.deepcopy(goal[0])
            ansorder.append([Time,copy.deepcopy(goal[1]),copy.deepcopy(goal[4])])#帰ってきた時刻、どこ登ったか、ID
            if len(runorder)==4:
                break
            if goal[1]==0:
                runner=runorder.pop(4)
            else:
                runner=runorder.pop()
            runtime=Time+runner[1]*goal[1]*2+runner[0]#出発時間＋往復＋登る時間
            alldata=[copy.deepcopy(runtime),copy.deepcopy(goal[1])]+copy.deepcopy(runner)
            climbing.put(alldata)
        while not climbing.empty():#でかい旗前
            goal=climbing.get()
            print(goal)
            Time=copy.deepcopy(goal[0])
            ansorder.append([Time,goal[1],goal[4]])#帰ってきた時刻、どこ登ったか、ID
        for where in range(4):#でかい旗
            runner=runorder.pop()
            print(runner)
            Time+=copy.deepcopy(runner[1]*where*2+runner[0])#出発時間＋往復＋登る時間
            ansorder.append([Time,where,runner[2]])#帰ってきた時刻、どこ登ったか、ID
        return [Time,ansorder]

    def strategy_1_last_4_member(self):#最後4人の最速を考える
        good_staff=[[] for _ in range(4)]
        order_by_speed=queue.PriorityQueue()
        for i in range(4):#どの柱を登るか
            order_by_speed.queue.clear()
            for j in self.data:
                runtime=j[0]+i*2*j[1]
                newdata=[runtime]+j
                order_by_speed.put(newdata)
            for k in range(4):
                a=order_by_speed.get()
                good_staff[i].append(a)
        fasttime=float("inf")
        fastorder=[]
        for i in good_staff[0]:
            for j in good_staff[1]:
                for k in good_staff[2]:
                    for l in good_staff[3]:
                        if (i[3]-j[3])*(i[3]-k[3])*(i[3]-l[3])*(j[3]-k[3])*(j[3]-l[3])*(k[3]-l[3])!=0:#同じ人いないか確認
                            time=i[0]+j[0]+k[0]+l[0]
                            if time<fasttime:
                                fasttime=time
                                fastorder=[i,j,k,l]
        for i in range(4):
            fastorder[i].pop(0)
        return fastorder

    def fastestgraph(self):
        allorder = list(itertools.permutations(self.data))
        X=[]
        Y=[]
        Fastest=[-1,float("inf")]
        strategy_1_time=self.strategy_1()[0]
        superfast=0
        for i in range(len(allorder)):
            time=self.checktime(list(allorder[i]))
            X.append(i)
            Y.append(time)
            if time<strategy_1_time:
                superfast+=1
        print("strategy 1 は上位"+str(superfast/len(allorder)*100)+"%　です")
        plt.scatter(X,Y,s=0.01)
        plt.show()


t=Touhou()
file=pd.read_csv("data.csv")
x=np.array(file["runtime"],dtype=float)
y=np.array(file["climbtime"],dtype=float)
for i in range(len(x)):
    t.importdata(x[i],y[i])
t.fastestgraph()
```
```csvs:data.csv
runtime,climbtime
1.5,13
2.0,15
1.7,14
1.8,15
2.0,11
3.0,13
1.5,15
2.0,15
1.5,12
```
### 結果

```
[14.0, 0, 14.0, 1.7, 2]
[19.0, 1, 15.0, 2.0, 7]
[23.0, 2, 15.0, 2.0, 1]
[25.8, 3, 15.0, 1.8, 3]
[29.0, 0, 15.0, 1.5, 6]
[13.0, 3.0, 5]
[13.0, 1.5, 0]
[12.0, 1.5, 8]
[11.0, 2.0, 4]
strategy 1 は上位1.9488536155202825%　です
```
![Figure_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2952141/fdf143e7-2d6b-2b19-7b26-dd2408acc469.png)

少なくともこの範囲では上位1割に含まれており、良い作戦だったといえる。
グラフで良い並び順に偏りがないか確認したが、わからなかった。

### 今後
実際に20人の場合だとどうだろうか？
=>遺伝的アルゴリズムの利用？？　機械学習を勉強したら再挑戦したい。