Matrix67 2011->2012 Maze

Matrix67.2011-2012.Maze.js

// v2.0，避免一个for (in)，速度大幅度提高，但graph的构造不如之前优雅，优化了hash，总代码量几乎没有增加，加了点注释。
var ops = ['+7', '/2', '*3', '-5'];
var graph = [
    [{e:0,n:1}, {e:1,n:1}],
    [{e:0,n:0}, {e:1,n:0}, {e:2,n:2}, {e:3,n:2}],
    [{e:2,n:1}, {e:3,n:1}]
]; // 第一维是顶点，第二维是出边，e是边的id，n是指向的顶点。
graph.forEach(function(vex, i){
    vex.forEach(function(edge, j){
        edge.f = new Function('val', 'return val' + ops[edge.e]); // 把边构造成一个function
    })
});

var now = {
    pos: 0, // 当前所在位置
    last: -1, // 上一次经过的边
    from: false, // 上一次状态
    ret: 2011 // 当前结果
};
function calcHash(node){
    return node.ret*100 + node.pos*10 + node.last; // pos和last都是个位数，以此构造hash。初始last=-1，刚好不会和任何中间状态碰撞。
}
var queue = [now], finish = 2, dest = 2012, visited = {};
console.time('search');
while (queue.length > 0){
    now = queue.shift(); // 宽搜
    var pos = now.pos, last = now.last, ret = now.ret, path = now.path;
    if (pos == finish && ret == dest) break;
    var hash = calcHash(now);
    if (visited[hash]) continue; // 访问过，剪枝
    visited[hash] = true;
    for (var i = 0; i < graph[pos].length; ++i){
        var node = graph[pos][i], edge = node.e, to = node.n;
        if (edge == 1 && ret % 2 == 1) continue; // 奇数不/2
        if (edge == last) continue; // 不走回头路，丑特斯邦威
        var move = {
            pos: to,
            last: edge,
            from: now,
            ret: node.f(ret)
        };
        queue.push(move);
    }
}
var path = ['=2012'];
while (now){
    path.push(ops[now.last]); // 通过last回溯出完整路径
    now = now.from;
}
console.log('2011' + path.reverse().join(''));
console.timeEnd('search');

Matrix67.2011->2012.Maze.js

var ops = ['+7', '/2', '*3', '-5'];
var fns = ops.map(function(op, i){
    return new Function('val', 'return val' + op);
});
var graph = [
    {0:1, 1:1},
    {0:0, 1:0, 2:2, 3:2},
    {2:1, 3:1}
]; // {边:指向}
var now = {
    pos: 0, // 当前所在位置
    last: -1, // 经过的边
    from: false,
    ret: 2011 // 当前结果
};
function calcHash(node){
    return node.ret * 10 + node.last;
}
var queue = [now], finish = 2, dest = 2012, visited = [{},{},{}];
visited[calcHash[now]] = true;
console.time('search');
while (queue.length > 0){
    now = queue.shift();
    var pos = now.pos, last = now.last, ret = now.ret, path = now.path;

    if (pos == finish && ret == dest) {
        break;
    }
    for (var edge in graph[pos]){
        var fn = fns[edge], to = graph[pos][edge];
        if (edge == 1 && ret % 2 == 1) continue; // 奇数不/2
        if (edge == last) continue;
        var move = {
            pos: to,
            last: edge,
            from: now,
            ret: fn(ret)
        }, hash = calcHash(move);
        if (visited[to][hash]) continue;
        visited[to][hash] = true;
        queue.push(move);
    }
}
var path = ['=2012'];
while (now){
    path.push(ops[now.last]);
    now = now.from;
}
console.log('2011' + path.reverse().join(''));
console.timeEnd('search');