Speeding Up Goats, Wolves and Lions By 18,800x

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;
}