adamhaile · August 29, 2015 14:02
diff --git a/GoatsWolvesAndLions.js b/GoatsWolvesAndLions.js
 // Optimizing Javascript Implementation of Goats, Wolves and Lions
 // Original fun puzzle from http://unriskinsight.blogspot.com/2014/06/fast-functional-goats-lions-and-wolves.html
 //
 // Strategy:
 // 1 - we know that each move reduces the total population by 1, so the optimal
 //     solution will be the one with the least moves.  So we'll progressively
 //     explore solutions of greater depth until we find a stable forest.
 // 2 - since each move removes at most one from each animal, any solution
 //     must have a depth at least as great as the minimum of the initial animal counts.
 // 3 - the order of moves doesn't matter.  to be more precise, if there is
 //     a set of moves that produces a stable forest, then we can prove
 //     that there is also a sequence of those moves whereby no animal count
 //     goes below zero: if our selection of moves from the set
 //     reaches a point where an animal count has hit zero yet there are remaining
 //     moves in the set which would take it below zero, then there must also be a move
 //     in the remaining set that would increase the zero-count animal.  This move must
 //     be satisfiable, since we aren't at the end of the set by definition, so it
 //     can't be the case that two animals are at zero count.
 // 4 - ergo, for each depth, all we need to explore is the possible splits
 //     between move types: how many goats produced, how many wolves, how
 //     many lions.
 //
 // Runtimes:
 // Original findStableForests on (2017, 2055, 2006): 7,099.95s
 // This implementation on (2017, 2055, 2006): 0.388s
 //
 // ** Speedup: 18,299x **
 //
 // ERGO: it's still about the algorithms, not the language.
 //
 // Note: there's also an analytic solution that will solve it in constant time
 // with simple math. See my proof here: https://news.ycombinator.com/item?id=7856275 .
 //
 // EDIT: as per note from Sascha, modified to return all maximal stable forests, not just 
 // the first.  Effect on runtime is minimal: 0.377s to 0.388s.
 function findMaximalStableForest(goats, wolves, lions) {
    "use strict";
    var depth,      // current depth we're exploring.  must be at least the min of the animal counts.
        dg, dw, dl, // moves are identified by whether they produce a goat (dg), wolf (dw) or lion (dl).  dg + dw + dl == depth
        g, w, l,    // number of animals resulting from moves. g = goats + dg - dw - dl, etc.
        results = [];

    for (depth = Math.min(goats, wolves, lions); results.length == 0; depth++) {
        for (dg = 0; dg <= depth; dg++) {
            for (dw = 0; dw <= depth - dg; dw++) {
                dl = depth - dw - dg;
                g = goats + dg - dw - dl;
                w = wolves + dw - dg - dl;
                l = lions + dl - dg - dw;
                if ((g == 0 && (w == 0 || l == 0)) || (w == 0 && l == 0)) {
                    results.push([g, w, l]);
                }
            }
        }
    }

    return results;
 }
	// Optimizing Javascript Implementation of Goats, Wolves and Lions
	// Original fun puzzle from http://unriskinsight.blogspot.com/2014/06/fast-functional-goats-lions-and-wolves.html
	//
	// Strategy:
	// 1 - we know that each move reduces the total population by 1, so the optimal
	// solution will be the one with the least moves. So we'll progressively
	// explore solutions of greater depth until we find a stable forest.
	// 2 - since each move removes at most one from each animal, any solution
	// must have a depth at least as great as the minimum of the initial animal counts.
	// 3 - the order of moves doesn't matter. to be more precise, if there is
	// a set of moves that produces a stable forest, then we can prove
	// that there is also a sequence of those moves whereby no animal count
	// goes below zero: if our selection of moves from the set
	// reaches a point where an animal count has hit zero yet there are remaining
	// moves in the set which would take it below zero, then there must also be a move
	// in the remaining set that would increase the zero-count animal. This move must
	// be satisfiable, since we aren't at the end of the set by definition, so it
	// can't be the case that two animals are at zero count.
	// 4 - ergo, for each depth, all we need to explore is the possible splits
	// between move types: how many goats produced, how many wolves, how
	// many lions.
	//
	// Runtimes:
	// Original findStableForests on (2017, 2055, 2006): 7,099.95s
	// This implementation on (2017, 2055, 2006): 0.388s
	//
	// Speedup: 18,299x
	//
	// ERGO: it's still about the algorithms, not the language.
	//
	// Note: there's also an analytic solution that will solve it in constant time
	// with simple math. See my proof here: https://news.ycombinator.com/item?id=7856275 .
	//
	// EDIT: as per note from Sascha, modified to return all maximal stable forests, not just
	// the first. Effect on runtime is minimal: 0.377s to 0.388s.
	function findMaximalStableForest(goats, wolves, lions) {
	"use strict";
	var depth, // current depth we're exploring. must be at least the min of the animal counts.
	dg, dw, dl, // moves are identified by whether they produce a goat (dg), wolf (dw) or lion (dl). dg + dw + dl == depth
	g, w, l, // number of animals resulting from moves. g = goats + dg - dw - dl, etc.
	results = [];

	for (depth = Math.min(goats, wolves, lions); results.length == 0; depth++) {
	for (dg = 0; dg <= depth; dg++) {
	for (dw = 0; dw <= depth - dg; dw++) {
	dl = depth - dw - dg;
	g = goats + dg - dw - dl;
	w = wolves + dw - dg - dl;
	l = lions + dl - dg - dw;
	if ((g == 0 && (w == 0 \|\| l == 0)) \|\| (w == 0 && l == 0)) {
	results.push([g, w, l]);
	}
	}
	}
	}

	return results;
	}