In a recent post, Andreas declared his love for the programming language FORTRAN. He concluded his post with the question “Can a functional language do this as well?”, where he was referring to the efficiency of his FORTRAN solution for the goats, wolves and lion problem. He followed it up with another post where her presented a more memory efficient solution that solves the goats, wolves and lion problem for an initial forest of about 6000 animals in 45 minutes. The purpose of this post is to give an answer to Andreas’ question.

To begin with, I promise that this is my last post that deals with the goats, wolves and lions problem. The problem is an interesting one in order to put different programming languages to the test. We’ll consider programming languages in our test that we use for the implementation of our products UnRisk-Q and UnRisk FACTORY:

The Wolfram Language

I gave a functional solution to the goats, wolves and lions problem in an earlier post, which dealt with construction of a functional solution using the Wolfram Language from a didactical point of view. Efficiency was not a concern. This time, we’ll develop a more efficient functional solution by using advanced features present in the Wolfram Language.

C++ 11 and Java 8

Functional programming language constructs are now being added to existing programming languages in the same way object-oriented features were introduced to procedural languages in the 1990s. The latest versions of both C++ and Java have been extended with Lambda functions and closures.

JavaScript

JavaScript has become one of the most popular programming languages due the ubiquitousness of the web. JavaScript had support for functional programming concepts from the very beginning through first-class functions and closures.

The Rules for the Test

• The solution must make use of functional programming constructs available in the respective language.
• The implemented solutions must be adequate to the idioms, techniques and the style of the respective language. We’ll follow the principle “when in Rome, do as the Romans do”.
• The solution must not use third-party libraries.
• All solutions must be cross-platform and run on Windows, Linux and OS X.
• We’ll evaluate the solutions based on efficiency.

The following sections show a lot of code. If you are not interested in the technical details of the implemented solutions, look at formulas instead or skip ahead to the runtime comparison section.

An Efficient Solution in the Wolfram Language

Since Andreas’ FORTRAN solution did not produce the devouring strategy that led to the stable forest, just the final stable forest itself, our efficient solution in the Wolfram Language will only compute the stable forests that result from an initial forest. We’ll use a vector to represent the state of a forest consisting of counters for the three different animal species:

{17, 55, 6}

We can use vector addition to compute the next state of a forest after a meal by adding {-1,-1,+1} (a wolf devours a goat), {-1,+1,-1} (a lion devours a goat) or {+1,-1,-1} (a lion devours a wolf) to a forest state vector:

In[1]:= {17, 55, 6} + {-1, +1, -1}
Out[1]= {16, 56, 5}

In the Wolfram Language a vector addition can be performed efficiently in one step on a list of vectors:

In[2]:= {{17, 55, 6},{17, 55, 6},{17, 55, 6}} + {{-1,-1,+1},{-1,+1,-1},{+1,-1,-1}}
Out[2]= {{16, 54, 7}, {16, 56, 5}, {18, 54, 5}}

We’ll use this feature in a function Meal that applies all possible meals to a list of forest states:

Meal[forests: {_?VectorQ ..}] :=
    With[{possibleMeals = {{-1,-1,+1},{-1,+1,-1},{+1,-1,-1}}},
        DeleteCases[
            Apply[Union,
                ConstantArray[forests, Length[possibleMeals]] +
                Thread[ConstantArray[possibleMeals, Length[forests]]]
            ], {___,-1,___}
        ]
    ]

The functions ConstantArray and Thread generate lists of vectors of the same shape which can then be added with the Plus operator.

The Union takes care of eliminating duplicate forest vectors and flattening of the resulting list at the same time. The vector addition may produce invalid forest states (i.e., states where one of the animal counters drops below zero). The outermost DeleteCases uses pattern matching to filter these invalid forest states.

The remaining parts of the solution are similar to the solution from the original post:

DevouringPossible[forests: {}] := False
DevouringPossible[forests: {_?VectorQ ..}] :=
    FreeQ[forests, {___,0,___,0,___}]
StableForests[forests: {_?VectorQ ...}] :=
    Cases[forests, {___,0,___,0,___}]
FindStableForests[forest_?VectorQ] :=
    StableForests[NestWhile[Meal, {forest}, DevouringPossible]]

DevouringPossible and StableForests have been rewritten in terms of Wolfram Language pattern expressions. Download the full Wolfram Language program here.

A Functional Solution in C++ 11

We’ll now reimplement the exact same algorithm we just gave for the Wolfram Language in C++ 11. A forest state with its three animal counters can be represented as a std::array in C++:

typedef std::array<int,3> forest_t;

Our C++ solution makes heavy use of algorithms from the C++ standard library. First we’ll add two helper functions to determine if a forest is stable or invalid:

bool forest_stable(const forest_t& forest) {
    return std::count(std::begin(forest), std::end(forest), 0) >= 2;
}

bool forest_invalid(const forest_t& forest) {
    return std::any_of(std::begin(forest), std::end(forest),
        std::bind(std::less<int>(), std::placeholders::_1, 0));
}

In the C++ community there is little love for containers other than std::vector. So, to go with the flow, we’ll use a std::vector<forest_t> to represent the list of forest states. The C++ meal function that corresponds to Meal in the Wolfram Language then looks like this:

std::vector<forest_t> meal(const std::vector<forest_t>& forests) {
    static const std::array<forest_t,3> possible_meals = {{
        forest_t{{-1,-1,+1}},
        forest_t{{-1,+1,-1}},
        forest_t{{+1,-1,-1}}
    }};
    // apply possible meals to all forests
    std::vector<forest_t> next_forests;
    next_forests.reserve(forests.size() * possible_meals.size());
    for (auto meal: possible_meals) {
        forest_t next_forest;
        std::transform(std::begin(forests), std::end(forests),
            std::back_inserter(next_forests),
            [&](const forest_t& forest) {
                std::transform(std::begin(forest), std::end(forest),
                    std::begin(meal), std::begin(next_forest),
                    std::plus<int>());
                return next_forest;
            });
    }
    // filter valid forests
    auto valid_end = std::remove_if(std::begin(next_forests),
        std::end(next_forests), forest_invalid);
    // delete duplicates
    std::stable_sort(std::begin(next_forests), valid_end);
    next_forests.erase(
        std::unique(std::begin(next_forests), valid_end),
        std::end(next_forests));
    return next_forests;
}

The heavy lifting in this function is done by the template algorithm std::transform and a C++ lambda function that performs the vector addition.

Because std::unique only removes consecutive duplicate elements, we have to sort the vector of forest states first in order to place identical ones next to each other. The function is an example for an application of the erase-remove idiom in C++.

Here are the C++ versions of DevouringPossible, StableForests and FindStableForests:

bool devouring_possible(const std::vector<forest_t>& forests) {
    return !forests.empty() && std::none_of(std::begin(forests),
        std::end(forests), forest_stable);
}

std::vector<forest_t> stable_forests(const std::vector<forest_t>& forests) {
    std::vector<forest_t> stable_forests;
    std::copy_if(std::begin(forests), std::end(forests),
        std::back_inserter(stable_forests), forest_stable);
    return stable_forests;
}

std::vector<forest_t> find_stable_forests(const forest_t& forest) {
    std::vector<forest_t> forests = { forest };
    while (devouring_possible(forests)) {
        forests = meal(forests);
    }
    return stable_forests(forests);
}

Please note that the C++ solution does neither use a for loop with a counter nor contain an explicit array subscript expression.

The rest of the program consists of straightforward C++ code. Download the complete C++ 11 program here.

Functional Solution in Java 8

In Java there is no built-in constant size array type or tuple class. We’ll use a value-based class to represent a forest:

final class Forest {
    private final int goats;
    private final int wolves;
    private final int lions;

    private Forest(int goats, int wolves, int lions) {
        this.goats = goats;
        this.wolves = wolves;
        this.lions = lions;
    }

    static public Forest makeForest(int goats, int wolves, int lions) {
        return new Forest(goats, wolves, lions);
    }

    @Override
    public int hashCode() { ... }

    @Override
    public boolean equals(Object obj) { ... }

    @Override
    public String toString() { ... }

The private constructor and the factory method are straightforward. The hashCode, equals and toString methods are required by the contract of a value-based class. Their implementations are automatically created by the IDE.

    public Optional<Forest> wolfDevoursGoat() {
        if (this.goats > 0 && this.wolves > 0)
            return Optional.of(
                makeForest(this.goats - 1, this.wolves - 1, this.lions + 1));
        return Optional.empty();
    }

    public Optional<Forest> lionDevoursGoat() { ... }

    public Optional<Forest> lionDevoursWolf() { ... }

The methods wolfDevoursGoat, lionDevoursGoat and lionDevoursWolf use the new Java 8 class Optional. The type Optional makes explicit that for a given reference we may not have a value and allows for monadic processing of the enclosed value.

    public Stream<Forest> meal() {
        List<Forest> nextForests = new ArrayList<>(3);
        this.wolfDevoursGoat().ifPresent(forest -> nextForests.add(forest));
        this.lionDevoursGoat().ifPresent(forest -> nextForests.add(forest));
        this.lionDevoursWolf().ifPresent(forest -> nextForests.add(forest));
        return nextForests.stream();
    }

The meal method of the Forest class returns all possible following forest states as a Stream. Streams are another new concept introduced with Java 8. Streams can be seen as lazily constructed Collections, where the production of the elements can be postponed until client code demands it. Furthermore a stream allows for sequential aggregate operations as shown in the implementation of the static method meal for a list of forest states:

static List<Forest> meal(List<Forest> forests) {
    return forests.stream().flatMap(Forest::meal).
        distinct().collect(Collectors.toList());
}

Using a monadic flatMap operation on the stream of current forest states, first the set of possible follower forest states is computed, then duplicate forests are eliminated with a distinct filter and finally the resulting forest states are collected in a new list.

The methods devouringPossible and stableForests and findStableForests are also implemented in terms of Streams:

static boolean devouringPossible(List<Forest> forests) {
    return !forests.isEmpty() &&
        !forests.stream().anyMatch(Forest::isStable);
}

static List<Forest> stableForests(List<Forest> forests) {
    return forests.stream().filter(Forest::isStable).collect(Collectors.toList());
}

static public List<Forest> findStableForests(Forest forest) {
    List<Forest> initialForests = Collections.singletonList(forest);
    Optional<List<Forest>> solution =
        Stream.iterate(initialForests, MagicForest::meal).filter(
            forests->!devouringPossible(forests)).findFirst();
    return solution.isPresent()?
        stableForests(solution.get()) :
        Collections.emptyList();
}

Download the complete Java 8 program here.

Functional Solution in JavaScript

As we have done for the Java solution, we define a class to represent a forest in JavaScript. Here is the constructor function:

function Forest(goats, wolves, lions) {
   this.goats = goats;
   this.wolves = wolves;
   this.lions = lions;
}

We add methods for the three different possible meals …

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() { ... }
Forest.prototype.lionDevoursWolf = function() { ... }

… and a meal method by assignment to the Forest prototype object:

Forest.prototype.meal = function() {
    return [this.wolfDevoursGoat(),
            this.lionDevoursGoat(),
            this.lionDevoursWolf()].filter(
        function(f) { return f !== null; })
}

The meal function for a list of forests makes use of the JavaScript array methods forEach and filter:

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

Here are the JavaScript versions of DevouringPossible, StableForests and FindStableForests:

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

Download the complete JavaScript program here.

Runtime Comparison

Without further ado, we present the running times of the different programs for sample input forests ranging from 80 to 6000 animals:

Goats	Wolves	Lions	Forests processed	C++ 11	Java 8	JavaScript	Wolfram Language	FORTRAN
17	55	6	3,636	0.01s	0.24s	0.04s	0.03s	0.01s
117	155	106	517,236	0.05s	0.62s	1.49s	1.95s	0.10s
217	255	206	2,600,836	0.35s	1.46s	8.70s	10.54s	0.96s
317	355	306	7,254,436	1.20s	3.58s	25.59s	29.94s	4.58s
417	455	406	15,478,036	2.74s	8.30s	56.90s	63.61s	11.45s
517	555	506	28,271,636	5.09s	16.40s	109.72s	118.32s	22.23s
617	655	606	46,635,236	9.14s	28.40s	187.80s	195.53s	38.59s
717	755	706	71,568,836	14.50s	45.75s	307.35s	301.94s	61.16s
817	855	809	104,072,436	20.25s	67.64s	467.59s	444.28s	92.78s
917	955	906	145,146,036	28.77s	100.73s	655.53s	627.07s	131.90s
1,017	1,055	1,006	195,789,636	39.71s	141.98s	898.48s	864.35s	180.12s
2,017	2,055	2,006	1,448,575,636	335.07s	1,352.33s	7,099.95s	7,526.00s	1,602.23s

Thanks to Andreas for providing me with the FORTRAN source code for his two-dimensional solution. The running times of his solution have been added to the table.

The results were obtained by using the following tools:

• MacBook Pro Mid 2010, equipped with a 2.66 GHz Intel Core i7 (“Arrandale”) processor and 8 GB 1067 MHz DD3 memory.
• OS X 10.9.3.
• C++ compiler Clang 3.4 with libc++.
• Oracle Java JDK 1.8.0_05-b13.
• JavaScript engine Google V8 3.25.30.
• Mathematica 9.0.1 for Wolfram Language.
• GNU Fortran 4.8.2.
• given times are wall-clock time measured with the shell command time and the function AbsoluteTiming for Wolfram Language code.

The following plot shows the data from the table. In this plot, the running time of the largest forest with 6000 animals has been omitted to avoid outliers.