2013年8月6日火曜日

ディーペスト問題の星間直行便のソーシャルグラフをarbor.jsで描いたよ

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

 先日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"も袋小路になってドサッと発散してるのが分かります。
 
  • ループする星たち
  • 相互参照する星に突き当たるとループしてしまう事になります。既に通った星に行くルートは除外する処理を入れる必要があります。
  • 発散する星
  • 例えば"1814964223463"とかいう星はnthをいくら大きくしても終端を表す"0"が返ってきません。グラフの方では花の様になっている星が発散する星です。他の星は大体10件程度しか直行便が無いので、取得数の制限をすれば回避する事が出来ます。
     
    図を見た上で探索する方法を検討する分には割と簡単ですが、APIだけしか公開されていない状態だとなかなか気付けないかもしれないですね。


    おわりに


     おもろかった。