【每日一题】- 2019-09-11 - 水壶问题

[azl397985856]

给你一个装满水的 8 升满壶和两个分别是 5 升、3 升的空壶，请想个优雅的办法，使得其中一个水壶恰好装 4 升水，每一步的操作只能是倒空或倒满。

[xiongcaihu]

/**
 * 思路：
 * 每个容器有两个选择，比如：A,可以倒入B,或者倒入C
 * 同样，B可以倒入A，也可以倒入C
 * 那么每次就有8种可能
 * 
 * 每产生一种可能，顺着这种可能的结果，继续去遍历更多可能
 * 那么，将会产生很多解，这些解，有些会是重复的，这个时候需要记录，这里用cache
 * 
 * 然后，还有当前深度搜索的分支如果没有结束，会涉及到已经visited的结果，这些结果需要记录，用totalPath
 * 
 * @returns
 */
function findContainer() {
    var totalPath = new Set();
    var cache = new Map();
    var rel = splitH2O({
        c8: 8,
        c5: 0,
        c3: 0
    }, totalPath, cache);
    if (rel) {
        return Array.from(totalPath);
    }
    return false;
}

function splitH2O({
    c8,
    c5,
    c3
}, totalPath, cache) {
    var path = `${c8}${c5}${c3}`;
    if (totalPath.has(path)) {
        return false;
    }

    if (cache.has(path)) {
        return cache.get(path);
    }

    totalPath.add(path);
    if (c8 == 4 || c5 == 4 || c3 == 4) {
        return true;
    }

    var limits = [8, 5, 3];

    for (var i = 0; i < limits.length; i++) {
        for (var j = 0; j < limits.length; j++) {
            if (j == i) continue;
            var rel = moveH2oToOther(limits[i], limits[j], {
                c8,
                c5,
                c3
            });
            rel = splitH2O(rel, totalPath, cache);
            if (rel) return true;
        }
    }

    totalPath.delete(path);
    cache.set(path, false);
    return false;
}

function moveH2oToOther(limitsA, limitsB, all) {
    a = all[`c${limitsA}`];
    b = all[`c${limitsB}`];

    if (limitsB - b > a) {
        all[`c${limitsA}`] = 0;
        all[`c${limitsB}`] = b + a;
        return all;
    } else {
        all[`c${limitsA}`] = a - (limitsB - b);
        all[`c${limitsB}`] = limitsB;
        return all;
    }
}

[azl397985856]

/**
 * 思路：
 * 每个容器有两个选择，比如：A,可以倒入B,或者倒入C
 * 同样，B可以倒入A，也可以倒入C
 * 那么每次就有8种可能
 * 
 * 每产生一种可能，顺着这种可能的结果，继续去遍历更多可能
 * 那么，将会产生很多解，这些解，有些会是重复的，这个时候需要记录，这里用cache
 * 
 * 然后，还有当前深度搜索的分支如果没有结束，会涉及到已经visited的结果，这些结果需要记录，用totalPath
 * 
 * @returns
 */
function findContainer() {
    var totalPath = new Set();
    var cache = new Map();
    var rel = splitH2O({
        c8: 8,
        c5: 0,
        c3: 0
    }, totalPath, cache);
    if (rel) {
        return Array.from(totalPath);
    }
    return false;
}

function splitH2O({
    c8,
    c5,
    c3
}, totalPath, cache) {
    var path = `${c8}${c5}${c3}`;
    if (totalPath.has(path)) {
        return false;
    }

    if (cache.has(path)) {
        return cache.get(path);
    }

    totalPath.add(path);
    if (c8 == 4 || c5 == 4 || c3 == 4) {
        return true;
    }

    var limits = [8, 5, 3];

    for (var i = 0; i < limits.length; i++) {
        for (var j = 0; j < limits.length; j++) {
            if (j == i) continue;
            var rel = moveH2oToOther(limits[i], limits[j], {
                c8,
                c5,
                c3
            });
            rel = splitH2O(rel, totalPath, cache);
            if (rel) return true;
        }
    }

    totalPath.delete(path);
    cache.set(path, false);
    return false;
}

function moveH2oToOther(limitsA, limitsB, all) {
    a = all[`c${limitsA}`];
    b = all[`c${limitsB}`];

    if (limitsB - b > a) {
        all[`c${limitsA}`] = 0;
        all[`c${limitsB}`] = b + a;
        return all;
    } else {
        all[`c${limitsA}`] = a - (limitsB - b);
        all[`c${limitsB}`] = limitsB;
        return all;
    }
}

你的代码真有特色

[lvguofeng1303]

认领