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…

1-output-new.txt

$ node new-magicForest.js 2017 2055 2006
total forests: 6128
{ goats: 0, wolves: 0, lions: 4023 }
total time: 20ms

2-output-orig.txt

// 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

new-magicForest.js

// 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');
  })
}

orig-magicForest.js

// 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');
  })
}

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.

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.

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.

You are correct about the order @curveship, definitely just luck.