Functional Goats, Wolves and Lions

Using the Wolfram Language as a programming language, we are going to develop a program that solves the goats, wolves and lions problem in a functional programming style. At the time of this writing the only publicly available implementation of the Wolfram language is for the Raspberry Pi.

Unlike procedural and object-oriented programming, functional programming lets you approach problems in a bottom-up fashion. By adding functions, you build the language up toward your program. For the given puzzle, we will just use individual sentences from the specification of the problem and turn these into corresponding functions that build up our program.

"There are three species of animals in a magic forest: lions, wolves and goats. At the very beginning, there are 17 goats, 55 wolves and 6 lions in the forest."


We need a model for a forest in our language. The Wolfram language contains an expression called association which suits our need to model a forest perfectly. It represents an association between keys and values. The keys will be the different species in the forest; the values will be number of animals:
<|"Goats" -> 17, "Wolves" -> 55, "Lions" -> 6|>

"A correct answer contains the number of animals left and a devouring strategy leading to this number."


Because the solution needs to contain the devouring strategy, we also add a "strategy" key to our model of a forest. The value will be list of meals leading to the number of animals in the given forest. This lets us define the initial forest in the following way:
initialForest = <|"Goats"->17,"Wolves"->55,"Lions"->6,"Strategy"->{}|>;

Note that our model of a forest is only complete with respect to the given problem we have to solve. We do not add trees to make the tree huggers happy. We do not add an evil witch, either, although one could argue that any magic forest must be the home of an evil witch.

"A wolf, after having devoured a goat, is transmuted into a lion; a lion, after having devoured a goat, is transmuted into a wolf; and a lion having devoured a wolf becomes a goat."


In the context of the puzzle, a meal is an action that changes the state of the forest. Thus it seems natural to model a meal as a function which returns the new state of a forest given an existing forest state. In functional programming data is immutable, therefore we create a new association expression representing the state of the forest after the meal.

WolfDevoursGoat[forest_Association]:=
If[forest["Wolves"]>0 && forest["Goats"]>0,
  <|"Goats"->forest["Goats"]-1,
    "Wolves"->forest["Wolves"]-1,
    "Lions"->forest["Lions"]+1,
    "Strategy"->Append[forest["Strategy"],WolfDevoursGoat]|>,
  (*Else*)
  {}
]

The function WolfDevoursGoat first checks if this form of meal is possible at all and if it is, returns a new forest state by adjusting the animal counters and adding itself to the strategy list. Let's run the function on the initial forest:

In[1]:= WolfDevoursGoat[initialForest]
Out[1]= <|"Goats"->16,"Wolves"->54,"Lions"->7,"Strategy"->{WolfDevoursGoat}|>

We can now define functions for the other two forms of meals LionDevoursGoat and LionDevoursWolf in a similar fashion.

For a given forest, three different form of meals can be applied to it. We add a Meal function which lets us compute all possible forests that may be result from a given forest after a meal:

Meal[forest_Association] := Flatten[{
    WolfDevoursGoat[forest], LionDevoursWolf[forest], LionDevoursGoat[forest]
  }]

The possible forests are returned in a list. Let's run the functions on the initial forest:

In[2]:= Meal[initialForest]
Out[2]= {
<|"Goats"->16,"Wolves"->54,"Lions"->7,"Strategy"->{WolfDevoursGoat}|>,
<|"Goats"->18,"Wolves"->54,"Lions"->5,"Strategy"->{LionDevoursWolf}|>,
<|"Goats"->16,"Wolves"->56,"Lions"->5,"Strategy"->{LionDevoursGoat}|>
}

After the initial meal we are now dealing with a list of forests. Therefore we add another version of the Meal function which also works for a list of forests:

Meal[forests : {_Association ..}] := 
    Flatten[Map[Meal, forests]]

The functions just maps the Meal function for a single forest to all forests in the given list and the flattens out the result. We can now do a nested invocation of the Meal function:

In[3]:= Meal[Meal[initialForest]]
Out[3]= {
<|"Goats"->15,"Wolves"->53,"Lions"->8,"Strategy"->{WolfDevoursGoat,WolfDevoursGoat}|>,
<|"Goats"->17,"Wolves"->53,"Lions"->6,"Strategy"->{WolfDevoursGoat,LionDevoursWolf}|>,
<|"Goats"->15,"Wolves"->55,"Lions"->6,"Strategy"->{WolfDevoursGoat,LionDevoursGoat}|>,
<|"Goats"->17,"Wolves"->53,"Lions"->6,"Strategy"->{LionDevoursWolf,WolfDevoursGoat}|>,
<|"Goats"->19,"Wolves"->53,"Lions"->4,"Strategy"->{LionDevoursWolf,LionDevoursWolf}|>,
<|"Goats"->17,"Wolves"->55,"Lions"->4,"Strategy"->{LionDevoursWolf,LionDevoursGoat}|>,
<|"Goats"->15,"Wolves"->55,"Lions"->6,"Strategy"->{LionDevoursGoat,WolfDevoursGoat}|>,
<|"Goats"->17,"Wolves"->55,"Lions"->4,"Strategy"->{LionDevoursGoat,LionDevoursWolf}|>,
<|"Goats"->15,"Wolves"->57,"Lions"->4,"Strategy"->{LionDevoursGoat,LionDevoursGoat}|>
}

Looking at the result, there seem to be similar forests in the result list. After two meals we may end up with 17 goats, 55 wolves and 4 lions in two different ways. The strategies {LionDevoursGoat, LionDevoursWolf} and {LionDevoursWolf, LionDevoursGoat} lead to the same number of animals for each species. Since we only have to return a single strategy that leads to a solution, there is no point in keeping more then one forest with the same number of animals for each species in the list. We thus redefine our Meal function for lists to eliminate duplicates:

ForestEqualQ[forest1_Association,forest2_Association]:=
    forest1["Wolves"] == forest2["Wolves"] && 
    forest1["Goats"]  == forest2["Goats"] && 
    forest1["Lions"]  == forest2["Lions"]
Meal[forests:{_Association..}]:=
    DeleteDuplicates[Flatten[Map[Meal,forests]],ForestEqualQ]

The ForestEqualQ function is a helper function which compares two forests for equality by extracting the species counts and comparing them with each other. The Meal function now uses the function DeleteDuplicates to eliminate redundant forests.


"After every meal, there is one animal fewer than before; therefore after some time, there is no devouring possible any more."


Our job now is to nest Meal invocations until no devouring is possible any more. A DevouringPossible function can be easily defined in terms of the Meal function we already have. Devouring for a given forest is only possible if the Meal function returns a non-empty set of new forests:

DevouringPossible[forest_Association]:=
    Meal[forest]!={}

For a list of forests, devouring is possible if for all underlying forests devouring is still possible. Otherwise we must have found the solution. Again we use Map to apply the DevouringPossible to each forest in the list, then we use Apply and And to compute the final Boolean result.

DevouringPossible[forests:{_Association..}]:=
    Apply[And,Map[DevouringPossible,forests]]

When devouring is no longer possible, we can extract a solution, i.e., a stable forest from the list of forest. We do that with a StableForests function:

StableForests[forests : {_Association ..}] :=
    Select[forests, Composition[Not, DevouringPossible]]

Given these functions the final function to compute the result almost writes itself :

FindStableForests[forest_Association]:=
    StableForests[NestWhile[Meal,forest,DevouringPossible]]

Starting from a single forest, we nest invocations of Meal with NestWhile while devouring is still possible. Then we extract the solution with StableForests.


"A correct answer contains the number of animals left."


In[4]:= FindStableForests[initialForest]
Out[4]= {<|"Goats" -> 0, "Wolves" -> 0, "Lions" -> 23,
  "Strategy" -> {WolfDevoursGoat, WolfDevoursGoat, WolfDevoursGoat,
    WolfDevoursGoat, WolfDevoursGoat, WolfDevoursGoat,
    WolfDevoursGoat, WolfDevoursGoat, WolfDevoursGoat,
    WolfDevoursGoat, WolfDevoursGoat, WolfDevoursGoat,
    WolfDevoursGoat, WolfDevoursGoat, WolfDevoursGoat,
    WolfDevoursGoat, WolfDevoursGoat, LionDevoursWolf,
    WolfDevoursGoat, LionDevoursWolf, WolfDevoursGoat,
    LionDevoursWolf, WolfDevoursGoat, LionDevoursWolf,
    WolfDevoursGoat, LionDevoursWolf, WolfDevoursGoat,
    LionDevoursWolf, WolfDevoursGoat, LionDevoursWolf,
    WolfDevoursGoat, LionDevoursWolf, WolfDevoursGoat,
    LionDevoursWolf, WolfDevoursGoat, LionDevoursWolf,
    WolfDevoursGoat, LionDevoursWolf, WolfDevoursGoat,
    LionDevoursWolf, WolfDevoursGoat, LionDevoursWolf,
    WolfDevoursGoat, LionDevoursWolf, WolfDevoursGoat,
    LionDevoursWolf, WolfDevoursGoat, LionDevoursWolf,
    WolfDevoursGoat, LionDevoursWolf, WolfDevoursGoat,
    LionDevoursWolf, WolfDevoursGoat, LionDevoursWolf,
    WolfDevoursGoat}|>}

We see from the output above that 23 lions are left in a stable forest.
On an Intel Core 2 Duo machine, the function takes around 1.5 seconds to deliver the solution.


"A correct answer contains the a devouring strategy leading to this number."


Although the strategy can be easily extracted from the result of the FindStableForests function, we want to deliver the strategy in proper style. Since we are dealing with a magic forest, an appropriate style is to deliver it as a fairy tale:
MakeFairyTale[forest_Association] := With[{
   beginning = {
    "Once upon a time there was a forest.\n",
    StringTemplate[
    "In the forest there lived `Goats` goats, `Wolves` wolves and `Lions` lions.\n"
    ]},
   middle = TemplateExpression[
     ReplaceAll[TemplateSlot["Strategy"],
      {WolfDevoursGoat -> 
        "Then a wolf devoured a goat and turned into a lion.\n", 
       LionDevoursGoat -> 
        "Then a lion devoured a goat and was transmuted to a wolf.\n",
       LionDevoursWolf -> 
        "Then a lion devoured a wolf and became a goat.\n"}]
     ],
   end = TemplateObject[{
      TemplateIf[TemplateSlot["Goats"] > 0, 
       StringTemplate[
        "The remaining `Goats` goats lived happily ever after."]],
      TemplateIf[TemplateSlot["Wolves"] > 0, 
       StringTemplate[
        "The remaining `Wolves` wolves lived happily ever after."]],
      TemplateIf[TemplateSlot["Lions"] > 0, 
       StringTemplate[
        "The remaining `Lions` lions lived happily ever after."]]
      }]
   },
  StringJoin[{
    TemplateApply[beginning, forest], 
    TemplateApply[{middle, end}, First[FindStableForests[forest]]]
    }]
  ]
In[5]:= MakeFairyTale[initialForest]
Out[5]= "Once upon a time there was a forest.
In the forest there lived 17 goats, 55 wolves and 6 lions.
Then a wolf devoured a goat and turned into a lion.
Then a wolf devoured a goat and turned into a lion.
Then a wolf devoured a goat and turned into a lion.
Then a wolf devoured a goat and turned into a lion.
Then a wolf devoured a goat and turned into a lion.
Then a wolf devoured a goat and turned into a lion.
Then a wolf devoured a goat and turned into a lion.
Then a wolf devoured a goat and turned into a lion.
Then a wolf devoured a goat and turned into a lion.
Then a wolf devoured a goat and turned into a lion.
Then a wolf devoured a goat and turned into a lion.
Then a wolf devoured a goat and turned into a lion.
Then a wolf devoured a goat and turned into a lion.
Then a wolf devoured a goat and turned into a lion.
Then a wolf devoured a goat and turned into a lion.
Then a wolf devoured a goat and turned into a lion.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
Then a lion devoured a wolf and became a goat.
Then a wolf devoured a goat and turned into a lion.
The remaining 23 lions lived happily ever after."

You can download a Mathematica notebook which contains all the code presented in this post. This notebook will be executable with Mathematica 10.

"A correct answer contains the proof that this is the maximal possible number of animals left."


We know:
(1) The lion is the king of the jungle.
(2) A jungle is a kind of forest.
(3) 23 is a magic number that movies have been made about.
(4) Thus from (1), (2) and (3), we know that 23 lions must be the maximal possible number of animals left in a magic forest.

Some Observations on the Functional Solution


Being true to functional programming spirit, the solution presented does not use any procedural loop constructs or variables. In the Wolfram Language, function parameters (e.g., forest) which may look like variables are actually constants. The only variable in the whole notebook is initialForest, which was just added as a convenience.

Note that in the solution there isn't a single recursive function invocation. It's possible to solve the given problem with a super terse recursive function, which will make the code look smart but whose drawback is that it will make the code unreadable. Recursion is an overused feature in functional programming. Niklaus Wirth said it best in his classic book "ALGORITHMS+DATA STRUCTURES=PROGRAMS": "The lesson to draw is to avoid the use of recursion when there is an obvious solution by iteration. ... The lesson is that algorithms which by their nature are recursive rather than iterative should be formulated as recursive procedures." For example, modeling a list as a recursive data structure is a very bad idea, which ultimately killed a programming language.

Also note that we deliberately avoided taking any mathematical shortcuts in the given solution. For example, the DevouringPossible function could be written more efficiently by testing if only one species is left. The program is fast enough without applying mathematical optimizations like these and again the program would only become a lot less readable. On top of that, adding unnecessary mathematical optimizations may add subtle bugs which may go undetected over years.