平々毎々(アーカイブ)

はてなダイアリーのアーカイブです。

「レイトン教授」というのはNintendo DS向け“頭の体操”ゲームのシリーズ名。すでに3作リリースされてる。

レイトン教授ってなによ? - Life Goes On で解かれてしまった ;-)
同じような枝刈りには行き着いていたんだけど……ということで、javascript版。


あ、これはa-a'から先に探索しているけど、ちょっと変えればc-c'から探索するようにできると思う。

(追記)後の自分が分からなくならないように、コードのことを書いておこう。

function Node(name) {
    this.name = name;
    this.nextNodes = [];
    this.link = function(node) {
        if (node.nextNodes) {
            this.nextNodes.push(node);
            node.nextNodes.push(this);
        }
    }
    this.toString = function() { /* snip */ }
}

Node型を定義したけど、逆に面倒くさくなったかも。初期化とかが。

function State() {
    this.ways = [];
    // snip
    this.getNextStates = function() {
        for (var i in this.ways) {
            if (!this._reachable(i)) return [];
        }
        for (var i in this.ways) {
            if (this._reached(i)) continue;
            var way = this.ways[i];
            var current = way[way.length - 1];
            var result = [];
            for (var j in current.nextNodes) {
                var next = current.nextNodes[j];
                if (this._visited(next)) continue;
                result.push(this._move(i, next));
            }
            return result;
        }
        returun [];
    }
    // snip
}

盤面の探索状況をあらわすState型と、次の盤面候補を返すgetNextStates関数。waysは色ごとのNode配列(ジャグ配列)。ここには書いてないけど、開始ノードの配列 starts と、終了ノードの配列 goals の2つをState.prototypeにセットしておく必要がある。

var model = {
    initialized: false,
    count: 0,
    nodes: [],
    states: null,
    state: null,
    removeState: null,
    addState: null,
    ready: function() {
        this.state = this.removeState();
        this.count++;
    },
    go: function() {
        var nextStates = this.state.getNextStates();
        for (var i in nextStates) {
            this.addState(nextStates[i]);
        }
    }
}

モデル。後で初期化するフィールドをここで定義することには意味がないんだけど、IDEのために一応書いておいた。ready と go を繰り返し呼び出すことで探索する(関数名がひどいし、よく考えたら2関数に分ける必然性はなかったな)。statesとaddStateとremoveStateは外から注入するのだけど、ここをスタックにすればDFSだし、キューにすればBFS。