7
\$\begingroup\$

Puzzle Question :

Giving 2 bottle of water. The capacity of the first one was 3 liter and the second one is 4 liter. They are all empty at first : (0,0). Each move only allow to do only one action at time.

Find out the move to get the second bottle have 2 liter of water and the first one can be anything (not overflow or negative) : (n,2) and n in [0,3].

Short version : (0,0) > Do something > (n,2), n in [0,3]

Requirement :

  • Print out the first met target path (depend on generate tree approach)
  • Print out all target path to target
  • My Code :

    $(document).ready(function() {
    var BOTTLE1_WATER_CAPACITY = 3;
    var BOTTLE2_WATER_CAPACITY = 4;
    var chart = null; // No chart has been draw
    
    function queue() {
        this.originalStack = [];
        this.dequeueStack = [];
    
        this.enqueue = function(value) {
            if (!value)
                throw new Error("Invalid value. Can't enequeue");
            this.originalStack.push(value);
        };
    
        this.enqueueArray = function(array) {
            if (!(array instanceof Array))
                throw new Error("Invalid value. Can't enqueue");
            for (var i = 0, length = array.length; i < length; i++) this.enqueue(array[i]);
        };
    
        this.dequeue = function() {
            if (!this.dequeueStack.length) {
                for (var i = 0, length = this.originalStack.length; i < length; i++)
                    this.dequeueStack.push(this.originalStack.pop());
            }
    
            var childNode = this.dequeueStack.pop();
            return (childNode) ? childNode : new Error("Queue is empty");
        };
    }
    
    function Node(_Bottle1Water, _Bottle2Water, _ParentNode) {
    
        var getOverFlowWater = function(fillWater, currentWater, maxWater) {
            var overflow = (fillWater + currentWater) - maxWater;
            return (overflow > 0) ? overflow : 0;
        };
    
        this.childNode = [];
        this.ParentNode = (_ParentNode instanceof Node) ? _ParentNode : null;
        this.Bottle1Water = _Bottle1Water;
        this.Bottle2Water = _Bottle2Water;
        this.isParentOfTargetNode = false;
        this.getChildNode = function() {
            if (!this.childNode.length) {
                //Hoist
                var overflow;
                //Fill full
                if (this.Bottle1Water < 3)
                    this.childNode.push(
                        new Node(
                            3, this.Bottle2Water, this));
    
                if (this.Bottle2Water < 4)
                    this.childNode.push(
                        new Node(
                            this.Bottle1Water, 4, this));
    
                //Remove all water
                if (this.Bottle1Water > 0)
                    this.childNode.push(
                        new Node(
                            0, this.Bottle2Water, this));
    
                if (this.Bottle2Water > 0)
                    this.childNode.push(
                        new Node(
                            this.Bottle1Water, 0, this));
    
                //Fill water to another bottle
                if (this.Bottle1Water > 0 &&
                    this.Bottle2Water < 4) {
                    overflow = getOverFlowWater(
                        this.Bottle1Water,
                        this.Bottle2Water,
                        BOTTLE2_WATER_CAPACITY
                    );
    
                    this.childNode.push(
                        new Node(
                            overflow, this.Bottle2Water +
                            this.Bottle1Water - overflow, this));
                }
    
                if (this.Bottle2Water > 0 &&
                    this.Bottle1Water < 3) {
                    overflow = getOverFlowWater(
                        this.Bottle2Water,
                        this.Bottle1Water,
                        BOTTLE1_WATER_CAPACITY
                    );
                    this.childNode.push(
                        new Node(
                            this.Bottle1Water +
                            this.Bottle2Water - overflow, overflow, this));
                }
            }
    
            return this.childNode;
        };
    
        this.toString = function() {
            return "(" + this.Bottle1Water + "," + this.Bottle2Water + ")";
        };
    
        this.equal = function(Node) {
            return (this.Bottle1Water === Node.Bottle1Water &&
                this.Bottle2Water === Node.Bottle2Water);
        };
    
        this.isCycleNode = this.isCycleNode || function(afterDequeueArr) {
            for (var i = 0, length = afterDequeueArr.length; i < length; i++)
                if (this.equal(afterDequeueArr[i])) {
                    this.isCycleNode = true;
                    return true;
                }
    
            this.isCycleNode = false;
            return false;
        };
    
        this.isTargetNode = this.isTargetNode || function() {
            this.isTargetNode = (this.Bottle2Water === 2);
            return this.isTargetNode;
        };
    
        this.setParentOfTargetNode = function() {
            if (this.isTargetNode) {
                var cur = this.ParentNode;
                while (cur) {
                    cur.isParentOfTargetNode = true;
                    cur = cur.ParentNode;
                }
            }
        };
    }
    
    var BFS_MapAllPath = (function(initNode, callBack) {
        this.RootNode = initNode;
        this.TargetNode = [];
    
        //Attempt to implement queue using 2 stack
        var afterDequeueArr = [];
        _queue = new queue();
        _queue.enqueue(this.RootNode);
    
        var NodeReturnByQueue = _queue.dequeue();
        while (!(NodeReturnByQueue instanceof Error)) {
            if (NodeReturnByQueue.isTargetNode()) {
                this.TargetNode.push(NodeReturnByQueue);
                //Trace back to it's parent and set it as target path ()
                NodeReturnByQueue.setParentOfTargetNode();
            }
    
            if (!NodeReturnByQueue.isCycleNode(afterDequeueArr)) {
                var childNode = NodeReturnByQueue.getChildNode();
                _queue.enqueueArray(childNode);
            }
    
            afterDequeueArr.push(NodeReturnByQueue);
            NodeReturnByQueue = _queue.dequeue();
        }
    
        return {
            RootNode: this.RootNode,
            TargetNode: this.TargetNode
        };
    
    })(new Node(0, 0));
    
    function getEarliestPathAsString() {
        var TargetNode = BFS_MapAllPath.TargetNode[0];
        var childNodeString = "";
    
        //Trace from childNode to RootNode element
        while (TargetNode) {
            childNodeString = TargetNode.toString() + " > " + childNodeString;
            TargetNode = TargetNode.ParentNode;
        }
    
        return childNodeString.substring(0, childNodeString.length - 3);
    }
    
    function getAllTargetAsPathString() { //Complicated string
        var childNodeArr = BFS_MapAllPath.TargetNode;
        var childNodeString = "";
    
        for (var i = childNodeArr.length - 1; i > -1; i--) {
    
            childNodeString = childNodeArr[i].toString() + "\n" + childNodeString;
    
            var cur = childNodeArr[i];
            while ((cur = cur.ParentNode)) {
                childNodeString = cur.toString() + " > " + childNodeString;
            }
    
            childNodeString = "SOLUTION " + (i + 1) + " : " + childNodeString;
        }
    
        return childNodeString;
    }
    
    }
    
    
    $("#btnGetEaliestPath").click(function() {
        $("#txtGetEaliestPath").val(getEarliestPathAsString());
    });
    
    $("#btnGetAllTargetPath").click(function() {
        $("#txtGetAllTargetPath").val(getAllTargetAsPathString());
    });
    

    View this in CodePen.

    Additional question :

    I know this is review code section. But i tempted to post it anyway.

    • What is the shortest/fastest way to solve it ?
    • Is there any heuristic available for this puzzle ?
    \$\endgroup\$
    • 1
      \$\begingroup\$ There is a pretty simple solution: (0,0) -> (3,0) -> (0,3) -> (3,3) -> (2,4) This is most likely also the best solution. \$\endgroup\$ – Vogel612 Oct 8 '17 at 12:35
    • \$\begingroup\$ en.wikipedia.org/wiki/Water_pouring_puzzle may provide a start re general issues, and googling "water jug problem" (no quotes) may provide additional references. \$\endgroup\$ – Barry Carter Oct 8 '17 at 13:30
    • 1
      \$\begingroup\$ Some of the math behind this puzzle is explained in this video: youtu.be/0Oef3MHYEC0 \$\endgroup\$ – siegi Oct 10 '17 at 9:32
    • \$\begingroup\$ are you allowed to empty a jug? \$\endgroup\$ – Jonah Oct 11 '17 at 23:28
    • 1
      \$\begingroup\$ @Vogel612 that's not a solution since the task requires the second bottle to contain the 2. \$\endgroup\$ – Roland Illig Sep 11 at 2:54
    3
    \$\begingroup\$

    Observations

    • Your algorithm uses a brute force with backtracking and history, which is a nice verification method to get all paths that don't include any cycles.
    • As you can see, there are 2 solutions. Each solution requires to use a flow from one bottle to the other. One bottle is the main bottle that you fill with water and move its content to the other.
      1. (0,0) - (3,0) - (0,3) - (3,3) - (2,4) - (2,0) - (0,2)
      2. (0,0) - (0,4) - (3,1) - (0,1) - (1,0) - (1,4) - (3,2)
    • I'm surprised to see your brute force does not exit early in the top path, starting with filling the 3 liter bottle, when reaching (0, 2). Is this as designed?

    Bruce managed a variant with 3 and 5 gallon, but they didn't show us how in the movie (it's the same principle). How would Chuck have done it?

    \$\endgroup\$

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

    Not the answer you're looking for? Browse other questions tagged or ask your own question.