先日CodeIQで結城 浩さんが出題していた星間飛行ルートを作ろう！に挑戦したのでその解答をポストします。あとついでに今回の問題で使われたデータをarbor.jsを使って可視化したのでそれも載せておきます。
結果は満点の5点でした。わーい。
問題の概要
今回の問題は、特定のポイントを経由し、目的地までたどり着くルートを算出するというものでした。ルートはWeb APIから1件ずつしか取得出来ない仕様となっており、また取得出来るデータはA->Bという一方向のルートとなります。解き方としては、startの星から行ける星のデータをWeb APIから取得して、その星から行ける星のデータを取得して…という操作を繰り返して特定のポイントを経由して目的地にたどり着く形となります。
利用言語、環境について
今回は普段使ってない言語でやろう、という事でRubyを使いました。問題を解くのに必要なのはhttp通信周りや配列操作だけだったので特に問題なく解けました。
処理概要とソース
処理としては指定した星から行ける直行便のリストを取得して、その中にゴールがあるまで読み込み続けるというものでした。Routeクラスを作り、各ルートをお互い繋げる事で、startから目的地までのルート情報を保持出来る様にしています。大体30分程度で書きました。
require 'net/http'
#start 5426528869786
#deep 4363616111476
#deeper 5092488161056
#deepest 8838746292440
class DirectFlightRoute
@id
@routes
attr_accessor :id, :routes
end
class Route
@prev
@current
def initialize
end
attr_accessor :prev, :current
end
class RouteResolver
@@API_ROOT = "http://133.242.134.37"
@@API_PATH = "/deepest.cgi?"
@@ID = "id"
@@NTH = "nth"
@allRouteData
attr_accessor :allRouteData
def initialize
@allRouteData = []
end
def getDirectFlight(id, nth)
url = URI.parse(@@API_ROOT)
req = Net::HTTP::Get.new(@@API_PATH + @@ID + "=" + id + "&" + @@NTH + "=" + nth.to_s)
res = Net::HTTP.start(url.host, url.port) {|http|
http.request(req)
}
if res.code.eql?("200")
return res.body.chomp()
end
return "-3"
end
def getDirectFlightList(id)
result = []
nht = 0
while true
df = getDirectFlight(id, nht)
puts "df:"+nht.to_s + ":" + df
if "0".eql?(df)
break
end
if !"-3".eql?(df)
result.push(df)
nht += 1
else
puts "error -3"
end
sleep 1
end
puts id+":"+result.to_s
directFlightRoutes = DirectFlightRoute.new
directFlightRoutes.id = id
directFlightRoutes.routes = result
@allRouteData.push(directFlightRoutes)
return result
end
def isConflictRoute?(node, id)
while node.prev != nil
prev = node.prev
if prev.current == id
return true
end
node = prev
end
return false
end
def isAlready?(id)
#答えのルートを得る場合は以下4行をコメントアウトする
#@allRouteData.each{|route|
# if route.id.eql?(id)
# return true
# end
#}
return false;
end
def resolveRoute(start, goal)
result = []
candidates = []
startRoute = Route.new
startRoute.current = start
candidates.push(startRoute)
while !candidates.empty?
candidate = candidates.pop()
directFlightList = getDirectFlightList(candidate.current)
directFlightList.each{|df|
#ゴールに到達した?
#※全ルートを得る場合はコメントアウト
if goal.eql? df
node = candidate
result.unshift df
result.unshift node.current
while node.prev != nil
n = node.prev
result.unshift n.current
node = n
end
return result
end
#既に登場したか?
if !isConflictRoute?(candidate, df)
if !isAlready?(df)
newRoute = Route.new
newRoute.current = df
newRoute.prev = candidate
candidates.push(newRoute)
end
end
}
end
return result
end
def resolve(routes)
result = ["dummy"]
routes.each{|r|
route = resolveRoute(r[0], r[1])
result = result.slice(0, result.size-1).concat(route)
}
return result
end
end
routeResolver = RouteResolver.new
results = routeResolver.resolve([["5426528869786", "4363616111476"],["4363616111476", "5092488161056"],["5092488161056","8838746292440"]])
puts "result-------------------------------"
puts results.to_s
得られた結果
上記プログラムで以下のルートデータを取得する事が出来ました。想定された答えより大分ながーいルートです。手当たり次第で探索したので無駄なルートを沢山通っています。
["5426528869786", "2484466449149", "4326837688991", "6021351385219", "8814668496374", "1074912512567", "7560374248806", "8217940346560", "6159521237181", "6248392538888", "5792719602457", "7713050646130", "6493203887111", "3014332099928", "4363616111476", "2615115005762", "3492704769369", "6101275938556", "5793542169547", "4217007177539", "2970040126310", "6218636660558", "1563577571047", "8742972189444", "8433634935614", "8564585174926", "6730551897632", "8279347398297", "5813746423067", "3459654931377", "8244481309445", "8279056819547", "8054128267676", "7401422935060", "5099100039591", "5471056644598", "7892247098840", "8479078158931", "8986753372139", "6137149535463", "7934869824134", "7782150475311", "4498551666547", "6023249450084", "7014829010728", "7322686465928", "5702278445116", "2864141700776", "8735695204612", "5174811483802", "5873652513502", "3536542280812", "6178493999671", "8188288894326", "7797971735921", "3971331745645", "5485131078541", "3876548341627", "1588698186896", "4656064657053", "3065937285535", "3437245100188", "5833671447983", "6714942513619", "7049674030681", "5813482662518", "2547413633555", "2966922227746", "1843019516033", "5092488161056", "8250347815782", "4775196002726", "8784346813978", "8636102321011", "8345370958267", "8787239992833", "7230764147984", "8701256641199", "8682011082922", "8225271457185", "8179247968273", "8573279739883", "8025149145454", "7840395069634", "6925571750184", "7706339201843", "6159786607508", "8108466497204", "6912947983983", "6870921135953", "6931349063153", "5848253839570", "7170473222416", "8033311672835", "7194628242299", "6762287044283", "8526665430645", "7116209295800", "7652884912454", "3101910152403", "5985346038182", "8741714209435", "6199888663851", "4597865188910", "5692390052367", "3545866022750", "6449164628142", "8978032168895", "4946412662661", "3840068516051", "4205606644588", "5256084349572", "6201473389311", "6146124596038", "3943178099168", "7758274483738", "6085641567012", "5596295380961", "6707581077767", "5717371807428", "6040500266078", "2109165486888", "5260999957124", "4491504900204", "2223936654310", "3575202947166", "3070747769765", "2812280975542", "4940548870566", "5576554716124", "2152647356070", "2994428026714", "3031196364476", "5591596393385", "5865952095146", "8838746292440"]
直行便データを全て取得してソーシャルグラフを描く
なんか適当にクロールしてたらゴールにたどり着いたので、折角だし星間の関係を可視化したいよなと思って、上のスクリプトを少しいじって全ての星の直行便データを取り出してグラフ書こうと考えたわけです。
arbor.jsでグラフを描く
得られたデータは1162件ありました。このデータをarbor.jsにちょろっと食わせると良い感じにグラフ化してくれます。実際arbor.jsで動くものも見れます。 (※動作超重い可能性があるので注意して下しあ)
http://ec2-54-214-204-32.us-west-2.compute.amazonaws.com/codeiq_deepest/
仕掛けられた罠達
グラフを見てみるとループする参照の仕方をする星達がごちゃっと塊になった領域がありますね。動く方を追いかけるとわかりますが、deepとdeeperの間にある"1814964223463"も袋小路になってドサッと発散してるのが分かります。
図を見た上で探索する方法を検討する分には割と簡単ですが、APIだけしか公開されていない状態だとなかなか気付けないかもしれないですね。
おわりに
おもろかった。
0 件のコメント:
コメントを投稿