Fast Functional Goats, Lions and Wolves

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.

Running Times Of Functional Solutions

By looking at the plot and the table we can draw some immediate conclusions:

  • Performance-wise, C++ trounces all the other programming languages in the test. The C++ program processes around 5 million forests per second on a single core, whereas the Wolfram Language program tops out at around 250 thousand forests.

  • There is a huge performance gap between the group of statically typed languages (C++, FORTRAN, Java) and the group of dynamically typed languages (JavaScript, Wolfram Language). The optimizations that the compiler can derive from having type information available at compile time still gives statically typed languages an edge over dynamically typed languages.

  • The performance of the Wolfram Language and JavaScript are roughly on par.

From the different running times, we can compute an average speedup that can be attained by moving from a higher level language to a lower level language:

From To Speedup
Java C++ 4.0
JavaScript Java 6.1
Wolfram Language Java 6.5
JavaScript C++ 22.4
Wolfram Language C++ 24.2

Of course these numbers cannot be generalized, they only apply to the tested programs. Also note that FORTRAN is not included in the list, because no sane person would switch to FORTRAN from another programming language voluntarily.

Conclusion

We can give the following answer to Andreas’ question “Can a functional language do this as well?” from this post. The computation time of all developed functional solutions is below two seconds for an initial forest of (117, 155, 106) animals. So the answer has to be “yes”.

Posted by at
Labels: