忍者ブログ
[1] [2] [3] [4] [5] [6] [7] [8] [9]

DATE : 2017/03/30 (Thu)
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。


DATE : 2010/08/28 (Sat)

Google Developer Day 2010のDevQuizで出題された「Google Maps API」を解いた際に使用したソースコードです。言語にはJavaScriptを使用しました。動作確認はWindows版Firefox 3.6.8で行っています。APIキーは、xxxxと伏せてあります。

この時点で、もう一方の選択問題である「2-legged OAuth」はすでに解けていました。しかし「2-legged OAuth」は詰まりつつも2時間ほどで解けてしまったので競争率が高そうなこと、「Google Maps API」の方が3問あって得点がより高そうなことから、本問題にも取り組んでみました。

Google Maps APIを使うのは初めてだったので、Google Maps APIから辿れる「Google Maps JavaScript API V2 Reference」をなんとなく見てみると、GDirectionsがなんとなく使えそうなことを発見しました。使えそうなサンプルコードはないかとGoogle Maps API Examplesを覗くと、Processing DirectionsがGDirectionsを使っていたので、そのサンプルコードを改変しながら本問題に取り組み始めました。

入力1、2は以下のソースコードを使いました。なんとなくA*アルゴリズムっぽいものを実装してみました(クローズリストを全然活用してないので、A*ではありません)。移動時間の計算でGoogle Maps APIに問い合わせると非同期で答えが返ってくるため、グローバル変数を多用したかなり見づらいコードになってしまいました。

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
    "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"  xmlns:v="urn:schemas-microsoft-com:vml">
  <head>
    <meta http-equiv="content-type" content="text/html; charset=utf-8"/>
    <title>Dev Quiz Google Maps 入力1、2用</title>
    <script src=" http://maps.google.com/?file=api&amp;v=2.x&amp;key=xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
      type="text/javascript"></script>
    <script type="text/javascript">
    // GDirections
    var gdir
    // 経由地のリスト
    var wayPoints
    // 開始地点
    var startPoint

    // 調査対象のリスト
    var openList
    // 現在で最も小さな移動時間
    var currentLowestCost
    // 現在で最も低い移動コストを持つノードのリスト
    var currentLowestCostNodes
    // 現在のノード
    var currentNode
    // 現在の隣接ノードのリスト
    var currentNeighborhoodNodes
    // 現在調査中のノード
    var currentTargetNode
    // 移動時間のキャッシュ
    var durationCache = []
    // 計算中の始点ノード
    var calculatingStartNode
    // 計算中の終点ノード
    var calculatingEndNode

    // ノードを生成する
    function Node(point, previousNode) {
        this.point = point
        this.previous = previousNode
        this.cost = 0
    }

    // 指定の要素の子要素としてテキストを設定する。
    function setText(text, elementId) {
        var textNode = document.createTextNode(text)
        var element = document.getElementById(elementId)
        element.replaceChild(textNode, element.firstChild)
    }

    // 結果を設定する。
    function setResult(resultString) {
        setText(resultString, "result")
    }

    // ログを表示する。
    function log(logString) {
        var logTextArea = document.getElementById("log")
        logTextArea.value += logString + "\n"
    }

    // Google Maps APIを呼び出した回数を表示する。
    function setRequestLog(value) {
        setText(value, "request_count")
    }

    // Google Maps APIを呼び出した際に呼び出す。
    function requestLog() {
        var value = parseInt(document.getElementById("request_count").firstChild.nodeValue, 10)
        setText(value + 1, "request_count")
    }

    // ログを消去する。
    function clearLog() {
        var logTextArea = document.getElementById("log")
        logTextArea.value = ""
        setRequestLog(0)
    }

    // ノードのリストをログに出力する。
    function logNodeList(name, nodeList) {
        var logString = name + ": ["
        for (var i = 0; i < nodeList.length; i++) {
            if (0 < i) {
                logString += ", "
            }
            logString += nodeList[i].point.name
        }
        logString += "]"
        log(logString)
    }

    // 「(緯度,経度)」の形式の文字列を作成する。
    function createPointString(point) {
        return "(" + point.latitude + "," + point.longitude + ")"
    }

    // Google Maps APIへのクエリ文字列を作成する。
    function createQuery(start, end) {
        return "from: " + createPointString(start) + " to: " + createPointString(end)
    }

    // 移動時間の計算が終わると呼び出される。
    function handleLoading() {
        if (gdir.getStatus().code == 200) {
            var durationSeconds = gdir.getDuration().seconds
            durationCache.push({
                    start: calculatingStartNode.point,
                    end: calculatingEndNode.point,
                    duration: durationSeconds})
            durationCalculated(durationSeconds)
        } else {
            setResult("error: " + gdir.getStatus().code + " on " +
                      startPoint.name + " to " + endPoint.name)
        }
    }

    // 最も低い移動コストを返す。
    function getLowestCost() {
        var lowestCost = Number.MAX_VALUE
        for (var i = 0; i < openList.length; i++) {
            if (openList[i].cost < lowestCost) {
                lowestCost = openList[i].cost
            }
        }
        return lowestCost
    }

    // 最も小さな移動コストを持つノードのリストを返す。
    function getLowestCostNodes() {
        lowestCost = getLowestCost()
        var lowestCostNodes = []
        for (var i = 0; i < openList.length; i++) {
            if (openList[i].cost == lowestCost) {
                lowestCostNodes.push(openList[i])
            }
        }
        return lowestCostNodes
    }

    // 出発点に戻ってきたか否かを返す。
    function isGoal(node) {
        return node.previous != null && node.point == startPoint
    }

    // ノードから経由地のリストを生成する。
    function getPoints(node) {
        var points = []
        do {
            points.push(node.point)
            node = node.previous
        } while (node != null)
        return points
    }

    // 結果を表示する。
    function finish(node) {
        route = getPoints(node)
        route.reverse()

        resultString = ""
        for (var i = 0; i < route.length; i++) {
            if (0 < i) {
                resultString += " "
            }
            resultString += route[i].name
        }

        setResult(resultString)
    }

    // 計算済みのリストへ移動する。
    // しかし計算済みのリストを活用しないため、ただ計算対象のリストから除くのみ。
    function moveToCloseList(node) {
        for (var i = 0; i < openList.length; i++) {
            if (openList[i] === node) {
                openList.splice(i, 1)
                break
            }
        }
    }

    // 各経由地をすべて含むリストを作成する。
    function createAllPoints() {
        var points = []
        for (var i = 0; i < wayPoints.length; i++) {
            points.push(wayPoints[i])
        }
        return points
    }

    // 指定のノードの隣接ノードのリストを返す。
    function getNeighborhoodNodes(startNode) {
        points = getPoints(startNode)
        neighborhoodPoints = createAllPoints()
        
        for (var i = 0; i < points.length; i++) {
            for (var j = 0; j < neighborhoodPoints.length; j++) {
                if (points[i].name == neighborhoodPoints[j].name) {
                    neighborhoodPoints.splice(j, 1)
                    j -= 1
                }
            }
        }

        var neighborhoodNodes = []
        if (0 < neighborhoodPoints.length) {
            for (var i = 0; i < neighborhoodPoints.length; i++) {
                neighborhoodNodes.push(new Node(neighborhoodPoints[i], startNode))
            }
        } else if (points.length == wayPoints.length) {
            neighborhoodNodes.push(new Node(startPoint, startNode))
        }
        return neighborhoodNodes
    }

    // キャッシュから距離を返す。
    // キャッシュ内に見つからない場合はnullを返す。
    function getDurationFromCache(startPoint, endPoint) {
        for (var i = 0; i < durationCache.length; i++) {
            if (startPoint.latitude == durationCache[i].start.latitude &&
                    startPoint.longitude == durationCache[i].start.longitude &&
                    endPoint.latitude == durationCache[i].end.latitude &&
                    endPoint.longitude == durationCache[i].end.longitude) {
                return durationCache[i].duration
            }
        }
        return null
    }

    // 移動時間が求まると呼び出される。
    function durationCalculated(duration) {
        log("duration is " + duration)
        currentTargetNode.cost = currentNode.cost + duration
        log("(tartget)" + currentTargetNode.point.name + " cost : " + currentTargetNode.cost)

        calculateOnNeighborhoodNodes()
    }

    // 移動コストを計算する。
    function calculateCost(startNode, endNode) {
        calculatingStartNode = startNode
        calculatingEndNode = endNode
        log("Calculate duration from " + startNode.point.name + " to " + endNode.point.name)
        var duration = getDurationFromCache(startNode.point, endNode.point)
        if (duration != null) {
            durationCalculated(duration)
        } else {
            // 最終的に、非同期にdurationCalculatedを呼び出す。
            gdir.load(createQuery(startNode.point, endNode.point),
                    {travelMode: G_TRAVEL_MODE_DRIVING})
            requestLog()
        }
    }

    // 隣接ノードのコストを計算する。
    function calculateOnNeighborhoodNodes() {
        if (0 < currentNeighborhoodNodes.length) {
            currentTargetNode = currentNeighborhoodNodes.pop()
            calculateCost(currentNode, currentTargetNode)
            openList.push(currentTargetNode)
        } else {
            calculateOnLowestCostNodes()
        }
    }

    // 最も低い移動コストを持つノードの移動コストを計算する。
    function calculateOnLowestCostNodes() {
        if (0 < currentLowestCostNodes.length && currentLowestCost == getLowestCost()) {
            currentNode = currentLowestCostNodes.pop()
            log("Current node is " + currentNode.point.name)

            if (isGoal(currentNode)) {
                finish(currentNode)
            } else {
                moveToCloseList(currentNode)
                currentNeighborhoodNodes = getNeighborhoodNodes(currentNode)
                logNodeList("Neighborhood nodes", currentNeighborhoodNodes)
                calculateOnNeighborhoodNodes()
            }
        } else {
            calculate()
        }
    }

    // 最も移動時間の短い経路を計算する。
    function calculate() {
        if (openList.length != 0) {
            currentLowestCost = getLowestCost()
            currentLowestCostNodes = getLowestCostNodes()
            calculateOnLowestCostNodes()
        } else {
             setResult("失敗")
        }
    }

    // 経路を計算する。
    function calculateRoute() {
        setResult("Calculating...")
        startPoint = wayPoints[0]
        var startNode = new Node(startPoint, null)
        log("Start node is " + startNode.point.name)
        openList = [startNode]

        calculate()
    }

    // 各経由地を取得する。
    function getWayPoints() {
        var inputTextArea = document.getElementById("input")
        var inputText = inputTextArea.value
        var wayPoints = []

        data = inputText.split(/\r?\n/)
        for (var i = 0; i < data.length; i++) {
            var elements = data[i].split(" ")
            if (elements.length == 3) {
                wayPoints.push({
                        name: elements[0],
                        latitude: elements[1],
                        longitude: elements[2]})
            }
        }

        for (var i = 0; i < wayPoints.length; i++) {
            log(wayPoints[i].name + " " +
                    wayPoints[i].latitude + " " +
                    wayPoints[i].longitude)
        }
        return wayPoints
    }

    // 初期化を行う。
    function initialize() {
        setResult("Initializing...")

        clearLog()
        log("Get waypoints...")
        wayPoints = getWayPoints()
        gdir = new GDirections(null, null)
        GEvent.addListener(gdir, "error", handleErrors)
        GEvent.addListener(gdir, "load", handleLoading)
        log("Start calculate...")
        calculateRoute()
    }

    // Google Maps APIからエラーが返ってきた場合に呼び出される。
    // 本関数は、以下のサンプルのままである。
    // http://code.google.com/intl/ja/apis/maps/documentation/javascript/v2/examples/directions-advanced.html
    function handleErrors(){
       if (gdir.getStatus().code == G_GEO_UNKNOWN_ADDRESS)
         alert("No corresponding geographic location could be found for one of the specified addresses. This may be due to the fact that the address is relatively new, or it may be incorrect.\nError code: " + gdir.getStatus().code);
       else if (gdir.getStatus().code == G_GEO_SERVER_ERROR)
         alert("A geocoding or directions request could not be successfully processed, yet the exact reason for the failure is not known.\n Error code: " + gdir.getStatus().code);
       
       else if (gdir.getStatus().code == G_GEO_MISSING_QUERY)
         alert("The HTTP q parameter was either missing or had no value. For geocoder requests, this means that an empty address was specified as input. For directions requests, this means that no query was specified in the input.\n Error code: " + gdir.getStatus().code);

       else if (gdir.getStatus().code == G_GEO_BAD_KEY)
         alert("The given key is either invalid or does not match the domain for which it was given. \n Error code: " + gdir.getStatus().code);

       else if (gdir.getStatus().code == G_GEO_BAD_REQUEST)
         alert("A directions request could not be successfully parsed.\n Error code: " + gdir.getStatus().code);
        
       else alert("An unknown error occurred.");
       
    }
    </script>

  </head>
  <body onunload="GUnload()">
  <h1>Input:</h1>
  <div>
  <textarea id="input" rows="12" cols="50"></textarea>
  <button type="button" onclick="initialize()">OK</button>

  <h1>Output:</h1>
  <div>
  <p id="result">Please input.</p>
  </div>

  <h1>Log:</h1>
  <div>
  <p>Request count: <span id="request_count">0</span></p>
  <textarea id="log" rows="20" cols="70"></textarea>
  </div>
  </body>
</html>

入力3には以下のソースコードを使いました。入力3を前述のソースコードで解こうとすると、Google Maps APIの1日のリクエスト可能数を越えてしまいました。どうも、前述のソースコードではキャッシュがうまく働いていないようでした。またこの時点で、本問題が巡回セールスマン問題に相当していることにようやく気付きました。そこで遺伝的アルゴリズムを使用して入力3の問題を解こうと思いつきました。

しかし単純に遺伝的アルゴリズムを導入してしまうと、Google Maps APIに大量にリクエストしてしまいます。なにしろ、遺伝的アルゴリズムではランダムに大量に生成した回答から優秀なものを選び出したり組み合わせたり一部を変化させたりして新しい回答を生み出し、それを何度も繰り返すわけですから。

そこで、次のような戦略を考えました。まず、遺伝的アルゴリズムで生成した回答から距離を計算します。この計算は、Google Maps APIを使わずに行います。その計算から得られた回答を元に、Google Maps APIを使って移動時間を計算します。つまり遺伝的アルゴリズムで距離による近似解を生成して、Google Maps APIで厳密解を得ようという寸法です。

距離の計算にはヒュベニの公式を使用しました。詳しくは「二地点の緯度・経度からその距離を計算する」を参照してください。Google Maps APIの測地系は世界測地系なので、ヒュベニの公式で用いられる定数も世界測地系のものを選択しました。

遺伝的アルゴリズムで用いられる遺伝子の構造は次のようにしました。基本的には、出発点・終点を除いた経由地からなるリストを用意し、そのリスト内の番号のリストです。しかし、次のような工夫を行いました。まず、終点の一歩手前の経由地は、それまでの経由地が決まれば一意に決まるため除きます。さらにリスト内の番号については、出発点・終点を除いて同じ経由地が出てくることはないため、これまでの経由地をリストから除いた状態での番号としました。こうすることで、同じ経由地を2度回るような明らかに非効率的な遺伝子を排除できました。

これまでの考えを取り込んだソースコードは以下のとおりです。

なお、後ほど確認してみたのですが本コードに入力1、2を使用すると、エラーで停止してしまいます。修正しようとも思ったのですが、問題を解いた時点のソースコードからの修正は最小限にしたかったためそのままにしてあります。

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
    "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"  xmlns:v="urn:schemas-microsoft-com:vml">
  <head>
    <meta http-equiv="content-type" content="text/html; charset=utf-8"/>
    <title>Dev Quiz Google Maps 入力3用</title>
    <!-- 参考: http://groups.google.com/group/google-maps-api/browse_thread/thread/58f5a3503da859e1 -->
    <script type="text/javascript">
        tick = function() { }
    </script>
    <script src=" http://maps.google.com/?file=api&amp;v=2.x&amp;key=xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
      type="text/javascript"></script>
    <script type="text/javascript">

    // GDirections
    var gdir
    // 経由地の配列
    var wayPoints
    // 距離を格納した配列
    var distances
    // 遺伝子の配列
    var genes
    // 移動時間の配列
    var durations = []
    // Google Mapsによって移動時間の計算が終わった遺伝子を格納する配列
    var calculatedGene

    // 距離計算に使うための定数など
    // 参考 : http://yamadarake.web.fc2.com/trdi/2009/report000001.html
    var a = 6378137.000
    var b = 6356752.314140
    var e = Math.sqrt((Math.pow(a, 2) - Math.pow(b, 2)) / Math.pow(a, 2))
    var mNumerator = a * (1 - Math.pow(e, 2))
    // 度からラジアンへの変換
    var toRad = 180 / Math.PI

    // GAに関する設定
    // 遺伝子の数
    var POP_SIZE = 2000
    // 世代数
    var MAX_ITERATION = 100
    // エリートの数
    var ELETE_RATE = 0.2
    // 突然変異が発生する可能性
    var MUTATION_PROBABILITY = 0.1

    // Google Maps APIにリクエストする最大数
    var MAX_REQUEST = 100

    // 指定のElementにTextノードを設定する。
    function setText(text, elementId) {
        var textNode = document.createTextNode(text)
        var element = document.getElementById(elementId)
        element.replaceChild(textNode, element.firstChild)
    }

    // 結果を設定する。
    function setResult(resultString) {
        setText(resultString, "result")
    }

    // ログを表示する。
    function log(logString) {
        var logTextArea = document.getElementById("log")
        logTextArea.value += logString + "\n"
    }

    // Google Mapsに対してリクエストした回数を設定する。
    function setRequestLog(value) {
        setText(value, "request_count")
    }

    // Google Mapsに対してリクエストしたことを記録する。
    function requestLog() {
        var value = parseInt(document.getElementById("request_count").firstChild.nodeValue, 10)
        setText(value + 1, "request_count")
    }

    // ログを削除する。
    function clearLog() {
        var logTextArea = document.getElementById("log")
        logTextArea.value = ""
        setRequestLog(0)
    }

    // startからendまでの距離を計算する。
    function getDistance(start, end) {
        x1 = start.latitude * toRad
        y1 = start.longitude * toRad
        x2 = end.latitude * toRad
        y2 = end.longitude * toRad
        dx = x1 - x2
        dy = y1 - y2
        muy = (y1 + y2) / 2
        w = Math.sqrt(1 - (Math.pow(e, 2) * Math.pow(Math.sin(muy), 2)))
        m = mNumerator / Math.pow(w, 3)
        n = (a / w)
        return Math.sqrt(Math.pow(dy * m, 2) + Math.pow(dx * n * Math.cos(muy), 2))
    }

    // 指定の遺伝子が表現する経路全体の距離を計算する。
    function calculateDistance(gene, wayPoints) {
        var currentWayPoints = wayPoints.slice(1, wayPoints.length)
        var distance = 0
        var start = wayPoints[0]
        for (var i = 0; i < gene.length; i++) {
            var geneIndex = gene[i]
            var end = currentWayPoints[geneIndex]
            distance += getDistance(start, end)
            currentWayPoints.splice(geneIndex, 1)
            start = end
        }
        end = currentWayPoints[0]
        distance += getDistance(start, end)
        start = end
        end = wayPoints[0]
        distance += getDistance(start, end)

        return distance
    }

    // 遺伝子の各要素の値を範囲に収まるように調節する。
    function tidyGene(gene, wayPoints) {
        var max_number = wayPoints.length - 1
        for (var i = 0; i < gene.length; i++) {
            gene[i] %= max_number
            max_number--
        }
    }

    // 遺伝子を作成する。
    function createInitialGenes(wayPoints, popSize) {
        var geneLength = wayPoints.length - 2
        var genes = []
        for (var i = 0; i < popSize; i++) {
            var a_gene = []
            for (var index = 0; index < geneLength; index++) {
                a_gene.push(Math.floor(Math.random() * (geneLength - 1)))
            }
            tidyGene(a_gene, wayPoints)
            genes.push(a_gene)
        }
        return genes
    }

    // 「(緯度,経度)」の形式の文字列を生成する。
    function createPointString(point) {
        return "(" + point.latitude + "," + point.longitude + ")"
    }

    // Google Mapsのルート計算が終わると呼び出される。
    function handleLoading() {
        if (gdir.getStatus().code == 200) {
            var durationSeconds = gdir.getDuration().seconds
            durations.push({gene: calculatedGene, duration: durationSeconds})
            calculateDurations()
        } else {
            setResult("error: " + gdir.getStatus().code + " on " +
                      startPoint.name + " to " + endPoint.name)
        }
    }

    // テキストボックスから出発点・経由地を取得する。
    function getWayPoints() {
        var inputTextArea = document.getElementById("input")
        var inputText = inputTextArea.value
        wayPoints = []

        data = inputText.split(/\r?\n/)

        for (var i = 0; i < data.length; i++) {
            var elements = data[i].split(" ")
            if (elements.length == 3) {
                wayPoints.push({
                        name: elements[0],
                        latitude: elements[1],
                        longitude: elements[2]})
            }
        }

        for (var i = 0; i < wayPoints.length; i++) {
            log(wayPoints[i].name + " " +
                    wayPoints[i].latitude + " " +
                    wayPoints[i].longitude)
        }
        return wayPoints
    }

    // 距離を比較する。
    function compareDistance(x, y) {
        return x.distance - y.distance
    }

    // 遺伝子に突然変異を起こす。
    function mutate(source_gene, wayPoints) {
        var gene = []
        gene = gene.concat(source_gene)
        gene[Math.random() * (gene.length - 1)] = Math.random() * 9
        tidyGene(gene, wayPoints)
        return gene
    }

    // 遺伝子を交叉させる。
    function crossover(source_gene1, source_gene2, wayPoints) {
        var gene = []
        // 以下の式の-3は、交叉の結果生まれた遺伝子が、source_gene1, source_gene2の
        // いずれかと一致しないようにするためである。
        // それぞれの-1の内訳は、以下のとおりである。
        // 1) インデックスの範囲を超えないようにするため。
        // 2) 生成された遺伝子がsource_gene2と等しくならないようにするため。
        // 3) (+1も含む)生成された遺伝子がe1source_genと等しくならないようにするため。
        var gene1SeparatePoint = Math.floor((Math.random() * (source_gene1.length - 3)) + 1)
        gene = gene.concat(
                source_gene1.slice(0, gene1SeparatePoint))
        gene = gene.concat(
                source_gene2.slice(gene1SeparatePoint, source_gene2.length))

        tidyGene(gene, wayPoints)
        return gene
    }

    // 遺伝子から距離を計算し、昇順に並べる。
    // 戻り値は、プロパティにdistance, geneを持つオブジェクトのリストである。
    function rankDistances(genes, wayPoints) {
        var currentDistances = []
        for (var i = 0; i < genes.length; i++) {
            var a_gene = genes[i]
            currentDistances.push({
                distance: calculateDistance(a_gene, wayPoints),
                gene: a_gene})
        }
        currentDistances.sort(compareDistance)

        return currentDistances
    }

    // エリートな遺伝子を1つ取得する。
    function getEleteGene(distances, eleteCount) {
        return distances[Math.floor(Math.random() * (eleteCount - 1))].gene
    }

    // 遺伝子同士が等しいか否かを返す。
    function isGeneEquals(gene1, gene2) {
        for (var i = 0; i < gene1.length; i++) {
            if (gene1[i] != gene2[i]) {
                return false
            }
        }
        return true
    }

    // 遺伝子の、重複を含まないリストを返す。
    function filterGene(distances) {
        var currentGenes = []
        var index = 0
        while (currentGenes.length < MAX_REQUEST && index < distances.length) {
            var currentDistance = distances[index]
            var inserted = false
            for (var i = 0; i < currentGenes.length; i++) {
                if (isGeneEquals(currentDistance.gene, currentGenes[i])) {
                    inserted = true
                    break
                }
            }
            if (!inserted) {
                currentGenes.push(currentDistance.gene)
            }
            index++
        }
        return currentGenes
    }

    // 移動時間を比較する。
    function compareDurations(x, y) {
        return x.duration - y.duration
    }

    // 遺伝子を出力値に変換する。
    function decodeGene(gene) {
        var first = true
        var currentWayPoints = wayPoints.slice(1, wayPoints.length)
        var decodedString = wayPoints[0].name
        for (var i = 0; i < gene.length; i++) {
            var wayPointIndex = gene[i]
            decodedString += " " + currentWayPoints[wayPointIndex].name
            currentWayPoints.splice(wayPointIndex, 1)
        }
        decodedString += " " + currentWayPoints[0].name + " " + wayPoints[0].name
        return decodedString
    }

    // すべての遺伝子について移動時間を計算し終えると呼び出される。
    function durationCompleted() {
        durations.sort(compareDurations)
        setResult(decodeGene(durations[0].gene))
    }

    // 移動時間を計算する。
    function calculateDurations() {
        var index = durations.length
        if (genes.length <= index) {
            durationCompleted()
            return
        }
        var aGene = genes[index]
        var targetWayPoints = [createPointString(wayPoints[0])]
        var currentWayPoints = wayPoints.slice(1, wayPoints.length)
        for (var i = 0; i < aGene.length; i++) {
            var wayPointIndex = aGene[i]
            targetWayPoints.push(
                    createPointString(currentWayPoints[wayPointIndex]))
            currentWayPoints.splice(wayPointIndex, 1)
        }
        targetWayPoints.push(createPointString(currentWayPoints[0]))
        targetWayPoints.push(createPointString(wayPoints[0]))

        calculatedGene = aGene
        gdir.loadFromWaypoints(targetWayPoints, {travelMode: G_TRAVEL_MODE_DRIVING})
        requestLog()
    }

    // 最短の移動時間となる経由地の順序を計算する。
    function calculate(wayPoints) {
        var currentGenes = createInitialGenes(wayPoints, POP_SIZE)
        var eleteCount = POP_SIZE * ELETE_RATE

        for (var iteration = 0; iteration < MAX_ITERATION; iteration++) {
            var currentDistances = rankDistances(currentGenes, wayPoints)
            currentGenes.splice(0, currentGenes.length)
            var index = 0;
            while (currentGenes.length < eleteCount) {
                var currentElete = currentDistances[index].gene
                var inserted = false
                for (var listIndex = 0; listIndex < currentGenes.length; listIndex++) {
                    if (isGeneEquals(currentGenes[listIndex], currentElete)) {
                            inserted = true
                            break
                        }
                }
                if (!inserted) {
                    currentGenes.push(currentDistances[index].gene)
                }
                index++
            }
            for (var i = 0; i < (POP_SIZE - currentGenes.length); i++) {
                if (Math.random() < MUTATION_PROBABILITY) {
                    currentGenes.push(
                            mutate(getEleteGene(currentDistances, eleteCount),
                                wayPoints))
                } else {
                    var gene1 = getEleteGene(currentDistances, eleteCount)
                    var gene2 = getEleteGene(currentDistances, eleteCount)
                    currentGenes.push(crossover(gene1, gene2, wayPoints))
                }
            }

            log("iteration: " + iteration +
                    ", best distance: " + currentDistances[0].distance +
                    " gene: " + currentDistances[0].gene.length)
        }
        distances = rankDistances(currentGenes, wayPoints)

        log("iteration end. best distance: " + distances[0].distance)

        genes = filterGene(distances)
        calculateDurations()
    }

    // 初期化する。
    function initialize() {
        setResult("Initializing...")

        clearLog()
        log("Get waypoints...")
        var wayPoints = getWayPoints()
        gdir = new GDirections(null, null)
        GEvent.addListener(gdir, "error", handleErrors)
        GEvent.addListener(gdir, "load", handleLoading)
        log("Start calculate...")
        calculate(wayPoints)
    }
    
    // Google Maps APIからエラーが返ってきた場合に呼び出される。
    // 本関数は、以下のサンプルのままである。
    // http://code.google.com/intl/ja/apis/maps/documentation/javascript/v2/examples/directions-advanced.html
    function handleErrors(){
       if (gdir.getStatus().code == G_GEO_UNKNOWN_ADDRESS)
         alert("No corresponding geographic location could be found for one of the specified addresses. This may be due to the fact that the address is relatively new, or it may be incorrect.\nError code: " + gdir.getStatus().code);
       else if (gdir.getStatus().code == G_GEO_SERVER_ERROR)
         alert("A geocoding or directions request could not be successfully processed, yet the exact reason for the failure is not known.\n Error code: " + gdir.getStatus().code);
       
       else if (gdir.getStatus().code == G_GEO_MISSING_QUERY)
         alert("The HTTP q parameter was either missing or had no value. For geocoder requests, this means that an empty address was specified as input. For directions requests, this means that no query was specified in the input.\n Error code: " + gdir.getStatus().code);

       else if (gdir.getStatus().code == G_GEO_BAD_KEY)
         alert("The given key is either invalid or does not match the domain for which it was given. \n Error code: " + gdir.getStatus().code);

       else if (gdir.getStatus().code == G_GEO_BAD_REQUEST)
         alert("A directions request could not be successfully parsed.\n Error code: " + gdir.getStatus().code);
        
       else alert("An unknown error occurred.");
       
    }
    </script>

  </head>
  <body onunload="GUnload()">
  <h1>Input:</h1>
  <div>
  <textarea id="input" rows="12" cols="50"></textarea>
  <button type="button" onclick="initialize()">OK</button>

  <h1>Output:</h1>
  <div>
  <p id="result">Please input.</p>
  </div>

  <h1>Log:</h1>
  <div>
  <p>Request count: <span id="request_count">0</span></p>
  <textarea id="log" rows="20" cols="70"></textarea>
  </div>
  </body>
</html>

さて、これまで長々としたソースコードを展開してきたわけですが、本問題への取り組みはさまざまな反省点を残しました。

まずは、Google Maps APIのドキュメントをあまりよく見ていなかったことです。DevQuiz終了後に公開されたさまざまな回答を見ると、Google Maps API Web ServicesGoogle Directions APIを使用しているコードを見かけました。ざっとAPIドキュメントを眺めた時点ではGoogle Maps JavaScript APIが目に飛び込んできたのでJavaScriptを使用したわけですが、Google Maps API Web Serviceを使用していればPythonなどのいつも自分が慣れ親しんだ言語を使用することもできました。

また実際には遺伝的アルゴリズムを使用するほどではなかったことも反省すべき点です。各経由地同士の行き帰りの移動時間をあらかじめGoogle Maps APIに問い合わせてメモリに保存しておけば良かったのです。入力1、2用のコードではキャッシュの仕組みがうまく動いていなかったこと、またこの時点で大量のJavaScriptコードを書いていて、コードの規模を縮小する方向に考えが及ばなかったことが遺伝的アルゴリズムの導入を促してしまったように思います。

このようにさまざまな反省点を残しましたが、なんとか入力3まですべて解けたので良しとしたいところではあります。

PR

DATE : 2010/08/24 (Tue)

Google Developer Day 2010のDevQuizで出題された「2-legged OAuth」を解いた際に使用したソースコードです。一部、xxxxと伏せてある部分があります。言語にはPythonを使用しました。

OAuthでのアクセスを実現するために、oauth2モジュールを使用しました。

どのような署名を求めていたのかが失敗時のレスポンスのbodyに書かれていたため、その内容とOAuth 1.0のRFCとをにらめっこした結果、なんとか解けました。

#!/usr/bin/env python

import oauth2 as oauth
import time
import urllib2

uri = 'http://gdd-2010-quiz-japan.appspot.com/oauth/xxxxxxxxxxxxxxxxxxxxx'

params = {
    'oauth_timestamp': int(time.time()),
    'oauth_nonce': oauth.generate_nonce(),
    'hello': 'world'
}

consumer = oauth.Consumer(
        key = 'xxxxxxxxxxxxxxxxxxxxxxxx', secret = 'xxxxxxxxxxxxxxxxxxxxxxxx')

params['oauth_consumer_key'] = consumer.key

request = oauth.Request(method = 'POST', url = uri, parameters = params)

signature_method = oauth.SignatureMethod_HMAC_SHA1()
request.sign_request(signature_method, consumer, None)

header = request.to_header('devquiz')

http_request = urllib2.Request(uri, 'hello=world', header)
try:
    response = urllib2.urlopen(http_request)
except urllib2.HTTPError, e:
    print e.read()
print response.info()

DATE : 2010/04/04 (Sun)

subprocessモジュールを使うと、Pythonからコマンドを実行できて便利です。以下のように指定すると、シェルスクリプトも実行できます。

import subprocess

subprocess.call("""
<command1> <argument1 ...>
<command2> <arguemnt2 ...>
""", shell = True)

しかし、シェル組み込みのコマンド(sourceなど)を使用する場合は、executable引数を指定しないと、実行時にエラーとなる可能性があります。executable引数を指定しない場合、subprocessモジュールは、Unix系の環境では/bin/shをシェルとして使用します。

ディストリビューションによって/bin/shにリンクされているシェルが異なります。例えば、Red Hat系ではbashなことが、Debian系ではdashなことが多いようです。

そのため、executable引数にそのシェルのパスを指定しないと、他のディストリビューションにPythonスクリプトを移行した際に急に動かなくなるという現象が起こります(;´Д`)実際に体験しました

先程のスクリプトをexecutable引数を用いたものに書き直すと、次のようになります(以下の例では、bashに依存するスクリプトの場合です)。実際には、ディストリビューションによってシェルの場所も/bin配下にあったり/usr/bin配下にあったりする場合があるので、executable引数に渡す文字列は定数扱いにしておいた方がメンテナンスしやすいかと思います。

import subprocess

BASH = '/bin/bash'

subprocess.call("""
<command1> <argument1 ...>
<command2> <arguemnt2 ...>
""", shell = True, executable = BASH)

DATE : 2010/01/13 (Wed)

ある日、大文字が含まれているかもしれない文字列を全て小文字に統一したいという目的からJava SE 6のAPIドキュメントをなんとなく眺めていました。すると、String.toLowerCase()の解説に次のような記述がありました。

注: このメソッドはロケールに依存するため、ロケールが単独で解釈されるような文字列に使用すると、予期せぬ結果を引き起こすことがあります。例として、プログラミング言語識別子、プロトコルキー、HTML タグがあります。たとえば、トルコ語ロケールの "TITLE".toLowerCase() は "t?tle" を返します。ここで、「?」は点のないラテン小文字の I の文字です。ロケールに依存しない文字列の正しい結果を取得するには、toLowerCase(Locale.ENGLISH) を使用します。

つまりトルコ語ロケールの環境下では、小文字変換で「TITLE」は「title」にならず、大文字変換でも「title」は「TITLE」になりません。トルコ語(Wikipedia)に掲載されているトルコ語でのアルファベッドによると、トルコ語では「i」が「İ」(上に点のあるI)、「I」が「ı」(点のないi)に変換されます。

するとロケールによって変換結果が異なっては困る処理でString.toLowerCase()およびString.toUpperCase()を使用すると、ロケールによっては正しく動作しないという現象が発生します。この問題を解決するには、APIドキュメントにもあるとおり、引数にLocale.ENGLISHを指定して、変換対象のロケールを指定できるString.toLowerCase(Locale)やString.toUpperCase(Locale)を使用します。

それでは大文字・小文字を区別せずに比較するString.equalsIgnoreCase(String)はどうなのでしょうか。結論から言えば、String.equalsIgnoreCase(String)はどのロケールであっても結果が同じとなります。

String.equalsIgnoreCase(String)のAPIドキュメントには以下のような記述があります。

この String とほかの String を比較します。大文字と小文字は区別されません。長さが同じで、2 つの文字列内の対応する文字が大文字と小文字の区別なしで等しい場合、2 つの文字列は大文字と小文字の区別なしで等しいと見なされます。

次のどれかに該当する場合に、c1 と c2 という 2 つの文字は大文字小文字の区別なしで等しいと見なされます。

  • 2 つの文字が等しい (== 演算子による比較)
  • Character.toUpperCase(char) メソッドをそれぞれの文字に適用すると同じ結果になる
  • Character.toLowerCase(char) メソッドをそれぞれの文字に適用すると同じ結果になる

String.equalsIgnoreCase(String)で用いられているのは、String.toLowerCase(), String.toUpperCase()ではなくCharacter.toLowerCase(char), Character.toUpperCase(char)です。

Character.toLowerCase(char)のAPIドキュメントには以下のように書かれています。

UnicodeData ファイル内のケースマッピング情報を使用して、文字引数を小文字に変換します。

(中略)

通常、String.toLowerCase() は、文字を小文字にマップするときに使用する必要があります。String ケースマッピングメソッドは、Character ケースマッピングメソッドと比べて複数の利点があります。String ケースマッピングメソッドは、ロケール依存のマッピング、コンテキスト依存のマッピング、および 1:M 文字マッピングを実行できるのに対し、Character ケースマッピングメソッドはそのようなマッピングを実行できません。

ここで重要なのは「通常、String.toLowerCase() は」で始まる部分です。ここにString.toLowerCase()とCharacter.toLowerCase(char)の違いが明記されています。

つまりCharacter.toLowerCase(char), Character.toUpperCase(char)はロケールに依存せず、どのようなロケールでも同じ結果となります。そのためString.equalsIgnoreCase(String)も同様にロケールに依存せず、どのようなロケールでも同じ結果となると言えます。

初めはメソッド名が同じなので、String.toLowerCase(), String.toUpperCase()とCharacter.toLowerCase(char), Character.toUpperCase(char)とが同じと勘違いしてしまいました。

(;^ω^)クラス名やメソッド名が似ているからと言って処理が同じだと判断せずに、ドキュメントはきちんと読むべきでした。


DATE : 2009/11/05 (Thu)

※ 本記事は、北陸アンカンファレンス2009で発表した内容を文章にまとめたものです。

はじめに

本記事では、Windows上でiTunesをスクリプトから操作できるように、以下の情報を提供します。

  1. スクリプトからiTunesに対してどのような操作ができるのか
  2. iTunesをスクリプトから操作するために必要となるもの
  3. スクリプトの例
  4. 「iTunes COM Interface Documentation」の見方
  5. スクリプトを書く上での注意事項

なお本記事の対象はWindowsで、対応する「iTunes COM Interface Documentation」のバージョンは8.1.0.52 です。MacOSに関しては扱いません。なおMacOSではOSA(Open Scripting Architecture)に対応したスクリプト言語からiTunesを操作できるようです。

スクリプトからiTunesに対してどのような操作ができるのか

以下の操作が、スクリプトから可能です。

  • プレイヤーの状態の取得(再生中か否か、選択しているトラックなど)
  • プレイヤーの操作(再生開始、停止、スキップなど)
  • (音楽、ビデオなどにかかわらず)ライブラリの編集(トラックの情報の編集、プレイリストの作成など)
  • Podcastの購読・更新

アプリケーション関係やGenius関係以外はだいたい操作できると思います。

iTunesをスクリプトから操作するために必要となるもの。

iTunesをスクリプトから操作するには、以下のものが必要です。

  • iTunes
  • スクリプトの実行環境
  • iTunes COM for Windows SDK

COM(Component Object Model)にアクセス可能であれば、スクリプトの言語は問いません。

iTunes COM for Windows SDKは、以下の手順で入手できます(Apple IDが必要です)。

  1. Apple Developer Connectionにログインする。
  2. 「Downloads」を開く。
  3. 「Developer Tools」を開く。
  4. 「iTunes COM for Windows SDK」をダウンロード。

スクリプトの例

ここでは、ライブラリ内の曲の情報をコンソールに出力する例を示します。

以下の手順で、ライブラリから曲の情報を取り出します。

  1. iTunesのCOMオブジェクトを取得する。
  2. iTunesからライブラリを取得する。
  3. ライブラリ内の1曲ごとに
    1. 曲の情報を1行に出力する。

この手順をPython(Python 2.6)で表現すると以下のようになります(;´∀`)Pythonなのは、ただ単に自分がいつも使っている言語だからです。なおPythonでCOMを取得するには、Pythonの実行環境にくわえて「Python for Windows extensions」も必要です。

# iTunesのCOMオブジェクトを取得する。
import win32com.client
itunes = win32com.client.Dispatch("iTunes.Application")

# iTunesからライブラリを取得する。
musicLibrary = itunes.LibraryPlaylist

# ライブラリ中の1曲ごとに
for aTrack in musicLibrary.Tracks:
    # 曲の情報を1行に出力する。
    print "%s, %s, %s" % (aTrack.Artist, aTrack.Name, aTrack.Album)

上記のスクリプトで最も重要なのは以下の部分です。

itunes = win32com.client.Dispatch("iTunes.Application")

(※ 以下では、「itunes」変数を、iTunesから初めに取得したCOMオブジェクトが入っている変数とします)

この部分は、iTunesからCOMを取り出す処理を行っています。つまりここからすべてが始まると言えます。「win32com.client.Dispatch」の部分はスクリプト言語によって変わりますが、「iTunes.Application」の部分はどのスクリプト言語であっても変わりません。

さて、iTunesからCOMを取り出す部分がすべての始まりだと言うことはわかりました。それでは、それから様々な操作を行うには、どのようにすればよいのでしょうか。その答えが「iTunes COM Interface Documentation」に書かれています。

「iTunes COM Interface Documentation」の見方

iTunes COM Interface Documentationを開くと、まず目に飛び込んでくるのがインタフェースやクラスの一覧です。

この中にある、「IiTunes」が、iTunesから初めに取得できるCOMオブジェクトとなります。つまり、まず「IiTunes」インタフェースからドキュメントを読んでいくと、スクリプトを使ってiTunesで何ができるのかわかります。

ところが、このiTunes COM Interface DocumentationはC言語向けに書かれており、スクリプトから使用する場合には若干理解しづらい書き方がされています。例えば、プレイリストを表すオブジェクトを生成する、IiTunesインタフェースのCreatePlaylistメソッドは以下のように記述されています。

HRESULT CreatePlaylist ([in] BSTR playlistName, [out, retval] IITPlaylist **iPlaylist)

スクリプトから使う際には、以下のように読むと使い方が理解しやすくなります。(ただし、スクリプトによっては以下のような理解では使えないものもあるかもしれません。しかし少なくとも、VBAやJScript、Ruby、Pythonでは以下のように理解しても問題はありません)。

  • 「HRESULT」は無視する。
  • 「CreatePlaylist」はメソッド名。
  • 「[in]」はメソッドの引数。
  • 「BSTR」は文字列型。
  • 「[out, retval]」はメソッドの戻り値。
  • 「IITPlaylist」はIITPlaylistインタフェース

つまり、プレイリストを生成するには以下のようにメソッド呼び出しを行います。

createdPlaylist = itunes.CreatePlaylist("New Playlist Name")

なお「BSTR」は文字列型を表しています。他にも「VARIANT_BOOL」や「long」、「DATE」などの型があります。このあたりは、スクリプト言語のどの型に相当するのかその名前から想像が付くと思います。

トラックのコレクションを表すIITTrackCollectionなどのxxxxCollectionインタフェースにも注意が必要です(例えば、「itunes.LibraryPlaylist.Tracks」で取得できるオブジェクトはIITTrackCollectionインタフェースを持っています)。言語によっては、これらxxxxCollectionインタフェースがそのスクリプト言語内でのコレクションにマッピングされることがあります。スクリプト言語内のコレクションにマッピングされた場合、xxxxCollectionインタフェースの、指定したインデックスの要素を返す「Item」プロパティは読み替えが必要です。具体的には次のようになります。

# ライブラリから初めの1曲を取り出すコード例

# IITTackCollectionがコレクションオブジェクトにマッピングされる言語の場合、
# このコードはうまく動作しない
aFirstTrack = itunes.LibraryPlaylist.Tracks.Item(1)

# 以下のように読み替えなければならない
aFirstTrack = itunes.LibraryPlaylist.Tracks[0]

スクリプトを書く上での注意事項

iTunesのCOMでは、インデックスが「1」から始まる点に注意が必要です。

ところが、処理系によってはそのスクリプト言語内のコレクションにマッピングする際に、インデックスを補正して0始まりに修正する場合があります(例えばこれまでのコード例のように、Pythonでは0始まりとして扱えます)。それはそれで便利なのですが、気をつけなければならない点があります。コレクションにマッピングされる「Item」プロパティはインデックスが0始まりとして扱えますが、それ以外は1始まりとして扱わなければなりません。例えば、IITTrackCollectionには「ItemByPlayOrder」という指定したインデックスで再生順にトラックを返すメソッドがあります。このメソッドはItemプロパティとは異なり、コレクションにマッピングされる対象外のためインデックスは1始まりとなります。具体的には次のようになります。

# ライブラリから初めの1曲を取り出すコード例

# IITTackCollectionがコレクションオブジェクトにマッピングされる言語の場合、
# このコードはうまく動作するが
aFirstTrack = itunes.LibraryPlaylist.Tracks[0]
# 次のコードはうまく動作しない
aFirstTrack = itunes.LibraryPlaylist.Tracks.ItemByPlayOrder(0)

# コレクションにマッピングされないプロパティは、インデックスが1から始まる
aFirstTrack = itunes.LibraryPlaylist.Tracks.ItemByPlayOrder(1)

つまり、コレクションへのマッピングの際にインデックスを0始まりに補正するスクリプト処理系でメソッドの引数にインデックスを渡す必要がある場合は、インデックスが1始まりであることを念頭に置いて処理しなければなりません。

最後に

以上、iTunesをスクリプトから操作する方法について簡単に説明してきました。iTunes自体のUIはとても良くできており、手動での操作でもかなりのことができます。ところが再生回数の変更やレートの一括変更など、細かいところではスクリプトの得意とする面もあります。またiTunes外からiTunesを操作するアプリケーションも数多く存在します。そう言った面では、アイディア次第でiTunesをさらに面白く活用することも可能ではないかと思います。

謝辞

北陸アンカンファレンス2009にて、本セッションを聞きに来てくださった方々、つたない説明ながらも熱心にお聞きくださり、誠にありがとうございました。

忍者ブログ [PR]
ブログ内検索
最近の状況
リンク
カレンダー
02 2017/03 04
S M T W T F S
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
使用許諾
最新コメント
(08/15)
(05/04)
(03/06)
(03/04)
(09/25)
最新トラックバック
T/O
(11/05)
ブログ内検索
最近の状況
リンク
カレンダー
02 2017/03 04
S M T W T F S
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
使用許諾
最新コメント
(08/15)
(05/04)
(03/06)
(03/04)
(09/25)
最新トラックバック
T/O
(11/05)