勇者の道標

レベル5

勇者はPythonの古文書を小さな町でみつけました。この大陸の地図のようです。
勇者はすでに最強レベルで魔王城に乗り込んで世界を平和にすることができます。
ただし、すべての場所を訪問してフラグを解除しないといけません。

place=["SmallTown","KingdomEedoo","KingdomCity","TowerOfBeBeel","TreeOfWorldAge"]
place+=["MoonTown","TownOfWing","VillageOfPirates","ZeronMountain","LakeOfDolfine","KingdomDevil"]
posX=[62, 18, 78, 74, 14, 27, 2, 71, 66, 57, 31]
posY=[18, 27, 22, 36, 3, 21, 4, 6, 37, 29, 12]

勇者は優秀な情報分析官のあなたに早速依頼をしてきました。

「最短距離をよろしく！」

現在位置はSmallTown、座標は62,18
最終到達地点はKingdomDevil、座標は31,12
距離の求め方はよくあるint(math.sqrt((x1-x2)**2+(y1+y2)**2))です。

すべての場所を回って最終到達地点まで、勇者は最短でどれだけの距離を歩きますか？

答えは3日後ぐらいまでに、ここに載せます。itertoolsを使って半日ほど試行錯誤した結果、40行ぐらいになりました。



答えを２つほど、上は記事を書いた時に作成したもの、下は翌日高速化用に距離のリストを作成したものです。
急がば廻れのような結果になってます。

import copy
import itertools
import time
def put(x,y,w):
    mp[y]=mp[y][:x]+w+mp[y][x+len(w):]
def lengRoute(route,writeSw):
    total=0
    if writeSw:print(place[route[0]])
    for i in range(1,len(route)):
        p0=route[i-1]
        p1=route[i]
        l=int(   ((posX[p0]-posX[p1])**2+(posY[p0]-posY[p1])**2)**0.5 )
        total+=l
        if writeSw:
            print(l)
            print( place[route[i]] )
    return total
def algo_4():
    bestRoute=[]
    bestL=10000
    c=len(place)
    seq = tuple([j for j in range(1,c-1)])
    allPath=list(itertools.permutations(seq, c-2))
    for i in allPath:
        route=[0]+list(i)+[c-1]
        l=lengRoute(route,False)
        if bestL>l:
            bestL=l
            bestRoute=copy.deepcopy(route)
    print("最短距離",bestL)
    lengRoute(bestRoute,True)
place=["SmallTown","KingdomEedoo","KingdomCity","TowerOfBeBeel","TreeOfWorldAge"]
place+=["MoonTown","TownOfWing","VillageOfPirates","ZeronMountain","LakeOfDolfine","KingdomDevil"]
posX=[62, 18, 78, 74, 14, 27, 2, 71, 66, 57, 31]
posY=[18, 27, 22, 36, 3, 21, 4, 6, 37, 29, 12]
mp=["."*100 for i in range(40)]
for i in range(len(place)):put(posX[i],posY[i],place[i])
for i in mp:print(i)
start_time = time.time()
algo_4()
print(time.time()-start_time)





import itertools
import time
def put(x,y,w):
    mp[y]=mp[y][:x]+w+mp[y][x+len(w):]
def matrix():
    r=[]
    for p0 in range(len(place)):
        r.append([int( ((posX[p0]-posX[p1])**2+(posY[p0]-posY[p1])**2)**0.5 ) for p1 in range(len(place))])
    return r
def leng3(p0,p1,p2,p3):
    return int( ((posX[p0]-posX[p1])**2+(posY[p0]-posY[p1])**2)**0.5 )+int( ((posX[p2]-posX[p1])**2+(posY[p2]-posY[p1])**2)**0.5 )+int( ((posX[p2]-posX[p3])**2+(posY[p2]-posY[p3])**2)**0.5 )
def matrix4():
    r=[]
    for p0 in range(len(place)):
        r1=[]
        for p1 in range(len(place)):
            r2=[]
            for p2 in range(len(place)):
                r2.append([ leng3(p0,p1,p2,p3) for p3 in range(len(place)) ])
            r1.append(r2)
        r.append(r1)
    return r

def lengRoute(route):
    t=0
    for i in range(3,len(route)-1,3):t+=arrLength4[route[i]][route[i-1]][route[i-2]][route[i-3]]
    t+=arrLength[route[-1]][route[-2]]
    return t

def routeWrite(route):
    print(place[route[0]])
    for i in range(1,len(route)):print(str(arrLength[route[i]][route[i-1]])+chr(10)+chr(13)+place[route[i]])
def algo_5():
    c=len(place)
    seq = tuple([j for j in range(1,c-1)])
    allPath=list(itertools.permutations(seq, c-2))
    #(bestL,bestI)=min((lengRoute([0]+list(i)+[c-1]),i)for i in allPath)
    bestL,bestI=10000,()
    for i in allPath:
        l=lengRoute([0]+list(i)+[c-1])
        if bestL>l:bestL,bestI=l,i

    print("最短距離",bestL)
    routeWrite([0]+list(bestI)+[c-1])
place=["SmallTown","KingdomEedoo","KingdomCity","TowerOfBeBeel","TreeOfWorldAge"]
place+=["MoonTown","TownOfWing","VillageOfPirates","ZeronMountain","LakeOfDolfine","KingdomDevil"]
posX=[62, 18, 78, 74, 14, 27, 2, 71, 66, 57, 31]
posY=[18, 27, 22, 36, 3, 21, 4, 6, 37, 29, 12]
start_time = time.time()
arrLength=matrix()
arrLength4=matrix4()
mp=["."*100]*40
for i in range(len(place)):put(posX[i],posY[i],place[i])
for i in mp:print(i)
algo_5()
print("**time**",time.time()-start_time)

syntax2html