Skip to content

Instantly share code, notes, and snippets.

@kaizhu256

kaizhu256/bucket-solution.html

Created May 21, 2015 22:13
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kaizhu256/9fb665bf848b110b540c to your computer and use it in GitHub Desktop.
Save kaizhu256/9fb665bf848b110b540c to your computer and use it in GitHub Desktop.
Download ZIP
Raw
bucket-solution.html
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>
generalized-bucket-solution [2015.5.22-a]
</title>
<link rel="stylesheet" href="http://kaizhu256.github.io/assets/utility2.css">
<style>
* {
box-sizing: border-box;
}
body {
background-color: #fff;
font-family: Helvetical Neue, Helvetica, Arial, sans-serif;
}
body > div {
margin-top: 20px;
}
textarea {
font-family: monospace;
height: 256em;
width: 100%;
}
.jslintOutputPre {
color: #f00;
}
.testReportDiv {
display: none;
}
.marginTop10 {
margin-top: 10px;
}
</style>
</head>
<body>
<div class="ajaxProgressDiv" style="display: none;">
<div class="ajaxProgressBarDiv ajaxProgressBarDivLoading" >loading</div>
</div>
<h1 >generalized-bucket-solution [2015.5.22-a]</h1>
<h3>solution to generalized bucket problem, along with tests and soluction</h3>
<div class="marginTop10">initial bucket state</div>
<input class="marginTop10 stateInitial" type=string value="[[2,0],[5,0]]"></input><br>
<div class="marginTop10">target volume</div>
<input class="marginTop10 targetVolume" type=string value="4"></input><br>
<button class="marginTop10" onclick="local.onButtonClick()">find solution</button>
<pre class="solution" style="border: 1px;">
</pre>
<div>source code (edit to live-test)</div>
<textarea class="istanbulInputTextarea jslintInputTextarea">
/*jslint
browser: true,
node: true
*/
(function () {
"use strict";
var local;
local = window.local = {};
local.utility2 = window.utility2;
local.onButtonClick = function () {
local.findBucketSolution({
log: function (text) {
document.querySelector('.solution').innerText = text;
},
stateInitial: JSON.parse(document.querySelector('.stateInitial').value),
targetVolume: JSON.parse(document.querySelector('.targetVolume').value)
});
};
local.transformState = function (options, state) {
/*
* this function will apply the appropriate operation on the state,
* e.g. fill bucket or pour one bucket into another
*/
var bucketList, diff, ii, jj, key;
options.operationCounter += 1;
// if solution is already found, then do nothing
if (options.stateFinal) {
return;
}
// if state already exists in options.stateDict, then do nothing
key = JSON.stringify(state);
if (options.stateDict[key] !== undefined) {
return;
}
// save state
options.stateDict[key] = options.depth;
// copy bucketList to prevent side-effect
bucketList = JSON.parse(key)[0];
ii = state[2];
jj = state[3];
switch (state[1]) {
// fill bucket ii with water
case 1:
bucketList[ii][1] = bucketList[ii][0];
break;
// pour water from bucket ii to bucket jj
case 2:
diff = Math.min(bucketList[jj][0] - bucketList[jj][1], bucketList[ii][1]);
bucketList[jj][1] += diff;
bucketList[ii][1] -= diff;
break;
}
// save bucketList to history
key = JSON.stringify(bucketList);
if (!options.historyDict[key]) {
options.historyDict[key] = state;
options.bucketListList.push(bucketList);
for (ii = 0; ii < bucketList.length; ii += 1) {
// optimization - if a lower step history is found then save it
if (bucketList[ii][1] === options.targetVolume) {
options.stateFinal = bucketList;
return;
}
}
}
};
local.recurse = function (options) {
/*
this function will breadth-first, recursively
1. fill a bucket with water,
2. or pour water from one bucket to another
3. until either all bucket states have been exhausted, or a solution has been found
*/
var tmp, ii, jj;
tmp = options.bucketListList;
options.bucketListList = [];
tmp.forEach(function (bucketList) {
for (ii = 0; ii < bucketList.length; ii += 1) {
// run all cases of filling a bucket for the given depth
local.transformState(options, [bucketList, 1, ii]);
// run all cases of moving water from one bucket to another at the given depth
for (jj = 0; jj < bucketList.length; jj += 1) {
local.transformState(options, [bucketList, 2, ii, jj]);
}
}
});
if (options.bucketListList.length) {
options.depth += 1;
local.recurse(options);
}
};
local.findBucketSolution = function (options) {
/*
this function will try to find a solution for options.targetVolume,
with initial bucket state options.stateInitial,
*/
var outputLog, tmp;
// init options
options = options || {};
// handle incomplete data
if (!options.stateInitial || !options.targetVolume) {
return options;
}
options.historyDict = {};
options.stateDict = options.stateDict || {};
options.bucketListList = [options.stateInitial];
options.depth = 0;
options.log = options.log || console.log.bind(console);
options.operationCounter = 0;
options.timeBegin = Date.now();
outputLog = '';
// start operation
local.recurse(options);
// if solution exists, then create it
if (options.stateFinal) {
outputLog += ('solution found after ' + options.depth + ' steps and ' +
options.operationCounter + ' operations\n');
options.solution = [[options.stateFinal, null]];
tmp = JSON.stringify(options.stateFinal);
// retrace solution from options.historyDict
while (true) {
if (tmp === JSON.stringify(options.stateInitial)) {
break;
}
tmp = options.historyDict[tmp];
if (!tmp) {
break;
}
options.solution.unshift(tmp);
tmp = JSON.stringify(tmp[0]);
}
options.solution.forEach(function (state, ii) {
var bucket1, bucket2, stateJson;
bucket1 = (state[0][state[2]] || [])[0];
bucket2 = (state[0][state[3]] || [])[0];
ii += 1;
stateJson = JSON.stringify(state[0]);
switch (state[1]) {
case 1:
outputLog += (ii + '. ' + stateJson + ' fill bucket ' + bucket1 + '\n');
break;
case 2:
outputLog += (ii + '. ' + stateJson + ' pour bucket ' + bucket1 +
' into bucket ' + bucket2 + '\n');
break;
default:
outputLog += (ii + '. ' + stateJson + ' - final state' + '\n');
}
});
} else {
outputLog += ('no solution found after ' + options.depth + ' steps and ' +
options.operationCounter + ' bucket operations' + '\n');
}
// save timeElapsed
options.timeEnd = Date.now();
options.timeElapsed = options.timeEnd - options.timeBegin;
outputLog += ('total time elapsed - ' + options.timeElapsed + ' ms' + '\n');
options.log(outputLog);
return options;
};
local.modeTest = true;
local.testCase_findBucketSolution_default = function (onError) {
/*
this function will test findBucketSolution's default handling behavior
*/
var result;
// test null data handling
result = local.findBucketSolution(null);
// validate no solution found
local.utility2.assert(!result.solution, result.solution);
// test trivial solution
result = local.findBucketSolution({
stateInitial: [[1, 0]],
targetVolume: 1
});
// validate solution
local.utility2.assert(JSON.stringify(result.solution) === JSON.stringify([
[[[1, 0]], 1, 0],
[[[1, 1]], null]
]), result.solution);
// test no solution handling behavior
result = local.findBucketSolution({
stateInitial: [[1, 0]],
targetVolume: 2
});
// validate no solution found
local.utility2.assert(!result.solution, result.solution);
// test 2 buckets problem
result = local.findBucketSolution({
stateInitial: [[2, 0], [5, 0]],
targetVolume: 4
});
// validate solution
local.utility2.assert(JSON.stringify(result.solution) === JSON.stringify([
[[[2, 0], [5, 0]], 1, 0],
[[[2, 2], [5, 0]], 2, 0, 1],
[[[2, 0], [5, 2]], 1, 0],
[[[2, 2], [5, 2]], 2, 0, 1],
[[[2, 0], [5, 4]], null]
]), result.solution);
// test 3 buckets problem
result = local.findBucketSolution({
stateInitial: [[3, 0], [5, 0], [11, 0]],
targetVolume: 9
});
// validate solution
local.utility2.assert(JSON.stringify(result.solution) === JSON.stringify([
[[[3, 0], [5, 0], [11, 0]], 1, 0],
[[[3, 3], [5, 0], [11, 0]], 2, 0, 1],
[[[3, 0], [5, 3], [11, 0]], 1, 2],
[[[3, 0], [5, 3], [11, 11]], 2, 2, 1],
[[[3, 0], [5, 5], [11, 9]], null]
]), result.solution);
onError();
};
window.utility2.testRun(local);
}());
</textarea>
<pre class="jslintOutputPre"></pre>
<div class="testReportDiv"></div>
<div class="istanbulCoverageDiv"></div>
<script src="http://kaizhu256.github.io/assets/istanbul-lite.js"></script>
<script src="http://kaizhu256.github.io/assets/jslint-lite.js"></script>
<script src="http://kaizhu256.github.io/assets/utility2.js"></script>
<script>
window.utility2 = window.utility2 || {};
window.utility2.envDict = {
npm_package_description: "solution to generalized bucket problem, along with tests and soluction",
npm_package_name: "generalized-bucket-solution",
npm_package_version: "2015.5.22-a"
};
document.querySelector(
".istanbulInputTextarea"
).addEventListener("keyup", function () {
window.jslint_lite.jslintTextarea();
window.istanbul_lite.coverTextarea();
});
if (!window.utility2.modeTest) {
window.jslint_lite.jslintTextarea();
window.istanbul_lite.coverTextarea();
}
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment