naoya_t@topcoder

MAPS API

15:03 |

• A地点を出発し、A地点に戻ってくる
• A地点→B地点, B地点→A地点 では所要時間が異なる場合がある（と問題文で教えてくれていた）
• 全部で最大10地点 → 経路候補は全部で9!通りしかない。permutation全部調べても余裕でしょ　→Gaucheで簡単なスクリプトを書いた
• APIから所要時間を引っ張ってくるのが面倒だった
• xmlきれいなのでsedで抜いてきたとか
• ソース全部まとめてアップロードしてエラーが起きないとは思えなかった（ZIPのバイナリをだらだらと表示しかねないと思った）ので、gaucheで書いた肝の部分のみアップ

APIを叩いて結果をXMLで取得するAWKスクリプト

BEGIN {
  M=0
#  awk -f lookup.awk -v level=1 < level1.dat
#  awk -f lookup.awk -v level=2 < level2.dat
#  awk -f lookup.awk -v level=3 < level3.dat
}

{
  split($0,ar," ")

  name[M] = ar[1]
  lat[M] = ar[2]
  long[M] = ar[3]

  M++
}

END{
  for(i=0;i<M;i++){
    for(j=0;j<M;j++){
      if (i==j) continue;
      cmd = sprintf("wget \"http://maps.google.com/maps/api/directions/xml?origin=%9.6f,%10.6f&destination=%9.6f,%10.6f&language=ja&sensor=false\" -O level%d_from%02d_to%02d.xml", lat[i],long[i], lat[j],long[j], level,i,j)
      system(cmd)
      print cmd
    }
  }
}

• XMLから必要なデータを抽出しS式化する過程はsedのワンライナーで書いた（そして忘れた）ので省略

(use srfi-1)
(use util.combinations)

;;
;; level 3
;;
(define cities
        #(
                ("東京タワー" 35.658570 139.745484)
                ("首里城" 26.216991 127.719362)
                ("松山城" 33.842035 132.764806)
                ("青葉城跡" 38.251127 140.855294)
                ("五条大橋" 34.995682 135.767890)
                ("日光東照宮" 36.758051 139.598899)
                ("日本銀行" 35.686839 139.771438)
                ("海ほたる" 35.464380 139.874407)
                ("日本科学未来館" 35.619415 139.776550)
                ("東京大学" 35.712940 139.759590)
                ))

;;
;; 各点間の所要時間は別スクリプトでAPIを呼び出して調べました。
;;
(define durations-data
        '(
        ((0 . 1) . 150131)
        ((0 . 2) . 40217)
        ((0 . 3) . 18011)
        ((0 . 4) . 21655)
        ((0 . 5) . 9716)
        ((0 . 6) . 821)
        ((0 . 7) . 2365)
        ((0 . 8) . 1071)
        ((0 . 9) . 1314)
        ((1 . 0) . 150327)
        ((1 . 2) . 121112)
        ((1 . 3) . 165946)
        ((1 . 4) . 129338)
        ((1 . 5) . 158930)
        ((1 . 6) . 150307)
        ((1 . 7) . 151256)
        ((1 . 8) . 150658)
        ((1 . 9) . 150769)
        ((2 . 0) . 40689)
        ((2 . 1) . 121187)
        ((2 . 3) . 56308)
        ((2 . 4) . 19700)
        ((2 . 5) . 49292)
        ((2 . 6) . 40669)
        ((2 . 7) . 41618)
        ((2 . 8) . 41020)
        ((2 . 9) . 41131)
        ((3 . 0) . 18369)
        ((3 . 1) . 166422)
        ((3 . 2) . 56508)
        ((3 . 4) . 37946)
        ((3 . 5) . 14511)
        ((3 . 6) . 18114)
        ((3 . 7) . 20094)
        ((3 . 8) . 18732)
        ((3 . 9) . 18043)
        ((4 . 0) . 21981)
        ((4 . 1) . 129354)
        ((4 . 2) . 19440)
        ((4 . 3) . 37600)
        ((4 . 5) . 30584)
        ((4 . 6) . 21961)
        ((4 . 7) . 22910)
        ((4 . 8) . 22312)
        ((4 . 9) . 22423)
        ((5 . 0) . 9730)
        ((5 . 1) . 159016)
        ((5 . 2) . 49102)
        ((5 . 3) . 14135)
        ((5 . 4) . 30540)
        ((5 . 6) . 9475)
        ((5 . 7) . 11455)
        ((5 . 8) . 10093)
        ((5 . 9) . 9404)
        ((6 . 0) . 937)
        ((6 . 1) . 150406)
        ((6 . 2) . 40492)
        ((6 . 3) . 17702)
        ((6 . 4) . 21930)
        ((6 . 5) . 9407)
        ((6 . 7) . 2379)
        ((6 . 8) . 1085)
        ((6 . 9) . 854)
        ((7 . 0) . 2658)
        ((7 . 1) . 151693)
        ((7 . 2) . 41779)
        ((7 . 3) . 19913)
        ((7 . 4) . 23217)
        ((7 . 5) . 11618)
        ((7 . 6) . 2559)
        ((7 . 8) . 2291)
        ((7 . 9) . 3112)
        ((8 . 0) . 1189)
        ((8 . 1) . 150658)
        ((8 . 2) . 40744)
        ((8 . 3) . 18444)
        ((8 . 4) . 22182)
        ((8 . 5) . 10149)
        ((8 . 6) . 1090)
        ((8 . 7) . 1912)
        ((8 . 9) . 1643)
        ((9 . 0) . 1170)
        ((9 . 1) . 150703)
        ((9 . 2) . 40789)
        ((9 . 3) . 17837)
        ((9 . 4) . 22227)
        ((9 . 5) . 9542)
        ((9 . 6) . 681)
        ((9 . 7) . 2816)
        ((9 . 8) . 1522)
                ))

(define M (vector-length cities))

(define shortest-time 999999999999999999)
(define shortest-route '())

(permutations-for-each
 (lambda (p)
;;       (print p) maybe 1 minute
   (let1 route (cons 0 (append p '(0)))
     (let loop ((a (car route)) (rest (cdr route)) (res '()))
       (if (null? rest)
           (let1 time (apply + (reverse! res))
             (when (< time shortest-time)
               (set! shortest-time time)
               (set! shortest-route route)))
                 (let* ((key (cons a (car rest)))
                        (dur (cdr (assoc key durations-data))))
                   (loop (car rest) (cdr rest) (cons dur res)))))))
 (iota (- M 1) 1))

(format #t "~a\t~d\n"
  (string-join
    (map (lambda (ix) (car (vector-ref cities ix))) shortest-route)
    " ")
  shortest-time)