Last active
August 29, 2015 14:02
-
-
Save chapel/1c038b2bf64b3037aaea to your computer and use it in GitHub Desktop.
UPDATE: I was wrong and my implementation has a critical bug and was lucky that the order I chose came to the correct answer. Leaving everything here for historical purposes. I modified the example JS script to use a more efficient way of processing the "forests". I also modified it to be run with Node.js. Based on: http://unriskinsight.blogspot…
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| $ node new-magicForest.js 2017 2055 2006 | |
| total forests: 6128 | |
| { goats: 0, wolves: 0, lions: 4023 } | |
| total time: 20ms |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // I didn't actually run this, as I didn't want to wait two hours | |
| $ node orig-magicForest.js 2017 2055 2006 | |
| total forests: 1448575636 | |
| { goats: 0, wolves: 0, lions: 4023 } | |
| total time: 7099950ms |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // See http://unriskinsight.blogspot.com/2014/06/fast-functional-goats-lions-and-wolves.html | |
| // Sascha Kratky ([email protected]), uni software plus GmbH & MathConsult GmbH | |
| // | |
| // run with node: | |
| // node magicForest.js 117 155 106 | |
| var totalForests = 0; | |
| function Forest(goats, wolves, lions) { | |
| totalForests += 1; | |
| this.goats = goats; | |
| this.wolves = wolves; | |
| this.lions = lions; | |
| } | |
| Forest.prototype.wolfDevoursGoat = function() { | |
| if (this.goats > 0 && this.wolves > 0) | |
| return new Forest(this.goats - 1, this.wolves - 1, this.lions + 1); | |
| else | |
| return null; | |
| } | |
| Forest.prototype.lionDevoursGoat = function() { | |
| if (this.goats > 0 && this.lions > 0) | |
| return new Forest(this.goats - 1, this.wolves + 1, this.lions - 1); | |
| else | |
| return null; | |
| } | |
| Forest.prototype.lionDevoursWolf = function() { | |
| if (this.lions > 0 && this.wolves > 0) | |
| return new Forest(this.goats + 1, this.wolves - 1, this.lions - 1); | |
| else | |
| return null; | |
| } | |
| // I got rid of Forest.prototype.meal since it made it | |
| // more complicated than it had to be. In fact | |
| // just by manually pushing the new forests into an | |
| // array vs creating a new array and filtering for null | |
| // entries I almost split the total time in half | |
| Forest.prototype.meal = function () {}; | |
| Forest.prototype.isStable = function() { | |
| if (this.goats === 0) return (this.wolves === 0) || (this.lions === 0); | |
| return (this.wolves === 0) && (this.lions === 0); | |
| } | |
| Forest.prototype.toString = function() | |
| { | |
| return "[goats=" + this.goats + ", wolves=" + this.wolves + ", lions=" + this.lions + "]"; | |
| } | |
| Forest.compare = function(forest1, forest2) { | |
| var cmp = forest1.goats-forest2.goats; | |
| if (cmp !== 0) return cmp; | |
| cmp = forest1.wolves-forest2.wolves; | |
| if (cmp !== 0) return cmp; | |
| return forest1.lions-forest2.lions; | |
| } | |
| function getForestKey(forest) { | |
| return this.goats + ':' + this.wolves + ':' + this.lions; | |
| } | |
| function meal(forests) { | |
| var forestMap = {}; | |
| return forests.reduce(function (nextForests, forest) { | |
| // Calling these directly is just simpler, since I | |
| // am using them here | |
| var wolfForest = forest.wolfDevoursGoat(); | |
| var lionForest = forest.lionDevoursGoat(); | |
| var lionWolfForest = forest.lionDevoursWolf(); | |
| // Creating an array to hold them before | |
| // adding them to the nextForests array | |
| var forests = []; | |
| var key = getForestKey(wolfForest); | |
| // Using a map is both more accurate and faster than | |
| // sorting then filtering to remove duplicates | |
| if (wolfForest && !forestMap[key]) { | |
| forestMap[key] = true; | |
| forests.push(wolfForest); | |
| } | |
| key = getForestKey(lionForest); | |
| if (lionForest && !forestMap[key]) { | |
| forestMap[key] = true; | |
| forests.push(lionForest); | |
| } | |
| key = getForestKey(lionWolfForest); | |
| if (lionWolfForest && !forestMap[key]) { | |
| forestMap[key] = true; | |
| forests.push(lionWolfForest); | |
| } | |
| return Array.prototype.concat.apply(nextForests, forests); | |
| }, []); | |
| } | |
| function devouringPossible(forests) { | |
| return forests.length > 0 && !forests.some(function(f) { return f.isStable(); }); | |
| } | |
| function stableForests(forests) { | |
| return forests.filter(function(f) { return f.isStable(); }); | |
| } | |
| function findStableForests(forest) { | |
| var forests = [forest]; | |
| while (devouringPossible(forests)) { | |
| forests = meal(forests); | |
| } | |
| return stableForests(forests); | |
| } | |
| var args = process.argv.slice(2); | |
| if (args.length !== 3 || args.some(isNaN)) { | |
| console.log('USAGE: node magicForest.js <goats> <wolves> <lions>'); | |
| } else { | |
| console.time('total time'); | |
| var initialForest = new Forest( | |
| parseInt(args[0]), | |
| parseInt(args[1]), | |
| parseInt(args[2]) | |
| ); | |
| findStableForests(initialForest).forEach(function (f) { | |
| console.log('total forests:', totalForests); | |
| console.log(f); | |
| console.timeEnd('total time'); | |
| }) | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // See http://unriskinsight.blogspot.com/2014/06/fast-functional-goats-lions-and-wolves.html | |
| // Sascha Kratky ([email protected]), uni software plus GmbH & MathConsult GmbH | |
| // | |
| // run with node: | |
| // node magicForest.js 117 155 106 | |
| var totalForests = 0; | |
| function Forest(goats, wolves, lions) { | |
| totalForests += 1; | |
| this.goats = goats; | |
| this.wolves = wolves; | |
| this.lions = lions; | |
| } | |
| Forest.prototype.wolfDevoursGoat = function() { | |
| if (this.goats > 0 && this.wolves > 0) | |
| return new Forest(this.goats - 1, this.wolves - 1, this.lions + 1); | |
| else | |
| return null; | |
| } | |
| Forest.prototype.lionDevoursGoat = function() { | |
| if (this.goats > 0 && this.lions > 0) | |
| return new Forest(this.goats - 1, this.wolves + 1, this.lions - 1); | |
| else | |
| return null; | |
| } | |
| Forest.prototype.lionDevoursWolf = function() { | |
| if (this.lions > 0 && this.wolves > 0) | |
| return new Forest(this.goats + 1, this.wolves - 1, this.lions - 1); | |
| else | |
| return null; | |
| } | |
| Forest.prototype.meal = function() { | |
| return [this.wolfDevoursGoat(), this.lionDevoursGoat(), this.lionDevoursWolf()].filter( | |
| function(f) { return f !== null; }) | |
| } | |
| Forest.prototype.isStable = function() { | |
| if (this.goats === 0) return (this.wolves === 0) || (this.lions === 0); | |
| return (this.wolves === 0) && (this.lions === 0); | |
| } | |
| Forest.prototype.toString = function() | |
| { | |
| return "[goats=" + this.goats + ", wolves=" + this.wolves + ", lions=" + this.lions + "]"; | |
| } | |
| Forest.compare = function(forest1, forest2) { | |
| var cmp = forest1.goats-forest2.goats; | |
| if (cmp !== 0) return cmp; | |
| cmp = forest1.wolves-forest2.wolves; | |
| if (cmp !== 0) return cmp; | |
| return forest1.lions-forest2.lions; | |
| } | |
| function meal(forests) { | |
| var nextForests = []; | |
| forests.forEach(function(forest) { | |
| nextForests.push.apply(nextForests, forest.meal()) | |
| }); | |
| // remove duplicates | |
| return nextForests.sort(Forest.compare).filter(function(forest, index, array) { | |
| return (index === 0 || Forest.compare(forest, array[index - 1]) !== 0); | |
| }); | |
| } | |
| function devouringPossible(forests) { | |
| return forests.length > 0 && !forests.some(function(f) { return f.isStable(); }); | |
| } | |
| function stableForests(forests) { | |
| return forests.filter(function(f) { return f.isStable(); }); | |
| } | |
| function findStableForests(forest) { | |
| var forests = [forest]; | |
| while (devouringPossible(forests)) { | |
| forests = meal(forests); | |
| } | |
| return stableForests(forests); | |
| } | |
| var args = process.argv.slice(2); | |
| if (args.length !== 3 || args.some(isNaN)) { | |
| console.log('USAGE: node magicForest.js <goats> <wolves> <lions>'); | |
| } else { | |
| console.time('total time'); | |
| var initialForest = new Forest( | |
| parseInt(args[0]), | |
| parseInt(args[1]), | |
| parseInt(args[2]) | |
| ); | |
| findStableForests(initialForest).forEach(function (f) { | |
| console.log('total forests:', totalForests); | |
| console.log(f); | |
| console.timeEnd('total time'); | |
| }) | |
| } |
yeah, the forestMap will only ever contain one entry with key "undefined:undefined:undefined", explaining the massive speedup.
Interestingly, it still arrives at the correct answer.
It gets the right answer by luck: if you see my proof in the HN comments, the optimal solution is to have wolves eat goats as long as they can, then alternate b/w lions eating wolves and wolves eating the resultant goat. B/c of the sequence of meals defined here (line 71-3), that happens to be the sequence followed. If you switched the sequence, it would find a solution, but not the optimal one.
Author
That's embarrassing. Thanks for finding the bug, indeed with the fix it is not as fast. I am curious as to how it arrives to the correct answer with the bug. Would be interesting to trace.
Author
You are correct about the order @curveship, definitely just luck.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The function in
new-magicForest.jscontains a bug:It does not compute the key for the argument
forest.