Skip to content

Instantly share code, notes, and snippets.

@chapel

chapel/1-output-new.txt

Last active Aug 29, 2015
Embed
What would you like to do?
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…
$ node new-magicForest.js 2017 2055 2006
total forests: 6128
{ goats: 0, wolves: 0, lions: 4023 }
total time: 20ms
// 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
// See http://unriskinsight.blogspot.com/2014/06/fast-functional-goats-lions-and-wolves.html
// Sascha Kratky (kratky@unrisk.com), 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');
})
}
// See http://unriskinsight.blogspot.com/2014/06/fast-functional-goats-lions-and-wolves.html
// Sascha Kratky (kratky@unrisk.com), 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');
})
}
@sakra

This comment has been minimized.

Copy link

@sakra sakra commented Jun 6, 2014

The function in new-magicForest.js contains a bug:

function getForestKey(forest) {
  return this.goats + ':' + this.wolves + ':' + this.lions;
}

It does not compute the key for the argument forest.

@clux

This comment has been minimized.

Copy link

@clux clux commented Jun 6, 2014

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.

@adamhaile

This comment has been minimized.

Copy link

@adamhaile adamhaile commented Jun 6, 2014

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.

@chapel

This comment has been minimized.

Copy link
Owner Author

@chapel chapel commented Jun 6, 2014

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.

@chapel

This comment has been minimized.

Copy link
Owner Author

@chapel chapel commented Jun 6, 2014

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