Eloquent JavaScript #07# Project: A Robot

const roads = [
    "Alice‘s House-Bob‘s House", "Alice‘s House-Cabin",
    "Alice‘s House-Post Office", "Bob‘s House-Town Hall",
    "Daria‘s House-Ernie‘s House", "Daria‘s House-Town Hall",
    "Ernie‘s House-Grete‘s House", "Grete‘s House-Farm",
    "Grete‘s House-Shop", "Marketplace-Farm",
    "Marketplace-Post Office", "Marketplace-Shop",
    "Marketplace-Town Hall", "Shop-Town Hall"
];

function buildGraph(edges) {
    // graph的存储格式类似于
    // graph.place_a: [place_b, place_c]
    // 表示由a能够直接到达b或者c
    let graph = Object.create(null);

    function addEdge(from, to) {
        // 首先判断该起点有没有被添加
        if(graph[from] == null) {
            graph[from] = [to];
        } else {
            graph[from].push(to);
        }
    }

    // ‘Alice‘s House-Bob‘s House‘.split("-")
    // → [‘Alice‘s House‘, ‘Bob‘s House‘]
    for(let [from, to] of edges.map(r => r.split("-"))) {
        addEdge(from, to);
        addEdge(to, from);
    }

    return graph;
}

const roadGraph = buildGraph(roads);

/**
 * 不要条件反射地把每个概念都搞成对象，
 * 这样的程序通常是难以理解和维护的。
 * 相反，用最小的数值集合来描述村庄&机器人
 * 状态就可以了。
 */

class VillageState {
    constructor(place, parcels) {
        this.place = place;
        this.parcels = parcels;
    }

    move(destination) {
        // move表示机器人的一次移动。
        // 首先检查是否存在一条从当前位置this.place到目的地destination的路
        // 如果不存在就说明不是合法的移动，返回旧的VillageState。
        // 如果存在，就更新机器人的当前位置，也就是更新VillageState.place
        // 为destination，当然同时需要更新包裹的状态：1-还没被机器人拿到
        // 的包裹不去管它，2-拿到的包裹则更新当前位置place（目的地address不改变）
        // 3-最后过滤掉已经送到的包裹（目的地就在本地）
        // PS. 整个move方法实际上是重造了一个VillageState，并没改变旧的
        // VillageState对象
        if(!roadGraph[this.place].includes(destination)) {
            return this;
        } else {
            let parcels = this.parcels.map(p => {
                if(p.place != this.place) return p;
                return {
                    place: destination,
                    address: p.address
                };
            }).filter(p => p.place != p.address);
            return new VillageState(destination, parcels);
        }
    }
}

/**
 * 可以用Object.freeze冻结对象
 * 所有对该对象属性的写入操作会被忽略
 * 这需要计算机做一些额外工作
 * let object = Object.freeze({value: 5});
    object.value = 10;
    console.log(object.value);
    // → 5
 */

/**
 * But the most important limit 
 * on what kind of systems we can build 
 * is how much we can understand. 
 * Anything that makes your code easier 
 * to understand makes it possible 
 * to build a more ambitious system.
 * 写程序最重要的限制是我们能够理解多少
 */

// robot实际上是一个函数接口，
// 该函数输入state和memory
// 输出决策action用于实际移动
// 这样写就能够动态更改策略了。
function runRobot(state, robot, memory) {
    for(let turn = 0;; turn++) {
        if(state.parcels.length == 0) {
            console.log(`Done in ${turn} turns`);
            break;
        }
        let action = robot(state, memory);
        state = state.move(action.direction);
        memory = action.memory;
        console.log(`Moved to ${action.direction}`);
    }
}

function randomPick(array) {
    let choice = Math.floor(Math.random() * array.length);
    return array[choice];
}

// 最愚蠢但有效的策略--随机决定下一个方向。
// 虽然这里只有一个参数，但是js允许传
// 入更多（或者更少）的参数。在这里，传入的
// memeory被忽略了
function randomRobot(state) {
    return {
        direction: randomPick(roadGraph[state.place])
    };
}

// 初始化
VillageState.random = function(parcelCount = 5) {
    let parcels = [];
    for(let i = 0; i < parcelCount; i++) {
        let address = randomPick(Object.keys(roadGraph));
        let place;
        do {
            place = randomPick(Object.keys(roadGraph));
            // 包裹的起点和终点不可以是同一个地方
        } while (place == address);
        parcels.push({
            place,
            address
        });
    }
    return new VillageState("Post Office", parcels);
};

// runRobot(VillageState.random(), randomRobot);
// 版本一，步数不稳定

// runRobotAnimation(VillageState.random(), randomRobot); 
// 作者写的动画版本，相当直观酷炫。。

// 第二个策略：事先指定一条可以通过所有地点的路线
// 走两遍就可以确保投递所有邮件
const mailRoute = [
    "Alice‘s House", "Cabin", "Alice‘s House", "Bob‘s House",
    "Town Hall", "Daria‘s House", "Ernie‘s House",
    "Grete‘s House", "Shop", "Grete‘s House", "Farm",
    "Marketplace", "Post Office"
];

// [a,b,c].slice(1) 
// → [b,c]
// [a,b,c].slice(1, 2) 
// → [b] // 包括start不包括end
function routeRobot(state, memory) {
    if(memory.length == 0) {
        memory = mailRoute;
    }
    // memory类似于队列
    // 等价: return {direction: memory.shift(), memory: memory}
    return {
        direction: memory[0],
        memory: memory.slice(1)
    };
}

// runRobot(VillageState.random(), routeRobot, []);
// 版本二，最多26步

/**
 * The problem of finding a route 
 * through a graph is a typical search problem. 
 * We can tell whether a given solution (a route) 
 * is a valid solution, but we can’t directly compute
 * the solution the way we could for 2 + 2. 
 * Instead, we have to keep creating potential solutions 
 * until we find one that works.
 */

// 返回一点到另一点的最短路线，参考：C++ 电路布线/最短路径问题
function findRoute(graph, from, to) {
    let work = [{at: from, route: []}]; // 其实也是个队列
    for(let i = 0; i < work.length; i++) {
        let {at, route} = work[i]; // 原来还可以这样赋值。。
        for(let place of graph[at]) {
            // 搜索四周围，如果找到了目的地就直接+1返回。
            if(place == to) return route.concat(place);
            if(!work.some(w => w.at == place)) { // 判断点是否已经入队
                work.push({at: place, route: route.concat(place)});
            }
        }
    }
}

function goalOrientedRobot({place, parcels}, route) {
    // 首先判断当前制定的路线走完没有，
    // 走完就重新制定下一条路线
    // 逐个包裹处理（当然也有可能顺
    // 路完成其它包裹的fetch和投递）
    if(route.length == 0) {
        let parcel = parcels[0];
        if(parcel.place != place) {
            // 制定取包裹路线
            route = findRoute(roadGraph, place, parcel.place);
        } else {
            // 制定投递路线
            route = findRoute(roadGraph, place, parcel.address);
        }
    }
    return {direction: route[0], memory: route.slice(1)};
}


runRobot(VillageState.random(), goalOrientedRobot, []);
// 版本三，平均十来步的样子