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.

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 ?
• There is a pretty simple solution: (0,0) -> (3,0) -> (0,3) -> (3,3) -> (2,4) This is most likely also the best solution. – Vogel612 Oct 8 '17 at 12:35
• 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. – Barry Carter Oct 8 '17 at 13:30
• Some of the math behind this puzzle is explained in this video: youtu.be/0Oef3MHYEC0 – siegi Oct 10 '17 at 9:32
• are you allowed to empty a jug? – Jonah Oct 11 '17 at 23:28
• @Vogel612 that's not a solution since the task requires the second bottle to contain the 2. – Roland Illig Sep 11 '19 at 2:54

• 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?