My Pavlovian reflex was to attack the magic forest problem using backtracking search in Haskell - I actually did that, but soon realised that the problem does not backtrack. That got me thinking a bit more about the magic forest problem itself, and I'd like to share these insights in today's blog entry (it is called "UnRisk Insight" after all). More about the Haskell code in a later blog entry.
EDIT: I deliberately didn't read the other solutions before working this out, because I didn't want to spoil the experience of puzzle solving. Andreas Binder's post contains essentially the same idea.
The Magic Forest
Let me briefly restate the problem: In a magic forest, goats, wolfs and lions live happily together. Being a theoretical physicist - and not a great storyteller - this is how the forest looks like in my imagination:
(g, w, l).
So the state of the forest is defined by a vector containing the number of goats, wolfs and lions living in it. Well, one could say the beauty lies in the abstraction :) It turns out our forest is a pretty lively place: a "stronger" animal can devour a weaker one any time and then magically turns into the third species. That is, our forest evolves one step at a time by adding either of three vectors to it:
d1=(-1, -1, +1)
d2=(-1, +1, -1)
d3=(+1, -1, -1)
Note that each step reduces the number of two species by one and increases the third by one, so in total, each step reduces the number of animals by one. Of course, there is the additional constraint that the number of animals in each species can never drop below zero.
Classes of Forests
The whole thing's too complicated for a physicist, so let's make a coordinate transformation (I'll indicate coordinates in the transformed space by angle brackets):
<x, y, z> = <g+w, g+l, w+l>
In this space, the above transitions are just
d1' = <-2,0,0>,
d2' = <0,-2,0>,
d3' = <0,0,-2>,
but the constraint is more complicated. What this shows us is that each step reduces one coordinate by two in this space. If we let the wildlife in our little forest go along with its business, it might eventually arrive at a stable state where no devouring is possible anymore. This state must be characterised by two species being extinct, otherwise further devouring would be possible. In <x,y,z>-space this means that one coordinate must be zero, which further means that we can only make two species extinct if their total number of animals is even (because d1', d2', d3' always reduce the sum by two). There must be at least one such combination: we have two possibilities, even and odd, and three places to distribute even/odd to (goats, wolfs, lions). Let's enumerate the possibilities:
| forest class | realization 1 | realization 2 |
| <eee> | (ooo) | (eee) |
| <eoo> | (ooe) | (eeo) |
| <oeo> | (oeo) | (eoe) |
| <ooe> | (eoo) | (oee) |
The two columns on the right contain all 8 possibilities of distributing (e)ven and (o)dd numbers over the three species. Two realisations in ()-space always correspond to one possibility in <>-space, which is given in the leftmost column in the table. In <>-space, there is always at least one even number, or all three are even (that's because we need to add an even and an odd number to get an odd number in <>-space, so there can only be zero or two odd numbers).
The transformations d1, d2 and d3 all flip even to odd numbers and vice versa: that means under each of these transformations, we hop back and forth between columns two and three in the above table, but we never go to a different row. That is, there are four distinct classes of magic forests, in the sense that during its entire lifetime, a forest always stays in its class.
The "optimal" solution strategy we are trying to find is the one with the maximum number of animals surviving. As each devouring step reduces the number of animals by one, this corresponds to the shortest path to a stable forest.
Given an initial forest, we first determine the class it belongs to. For the three classes <eoo>, <oeo> and <ooe>, there is only one choice: we have to eliminate those species that belong to the even number (that's goats and wolfs for <eoo>, goats and lions for <oeo> and wolfs and lions for <ooe>). For the first class, there is an initial choice of which two species to eliminate.
Let's look at <eoo> first, <oeo> and <ooe> will work out the same. For an <eoo> forest, we know the solution will be (0, 0, u), where u is the number of lions remaining in the end. To get there, we have to get rid of goats as well as wolfs. Let m be max(g,w), i.e., the species with the greater number of animals out of the two species we want to get rid of, and assume it is the wolfs in this example. That means we have to get rid of the wolfs, and there are two transformations that bring down the number of wolfs: d1 and d3. The shortest strategy will thus contain only those two transformations, because anything that increases the number of wolfs will take us longer.
Is it possible to reach a stable state with just these two transformations? Of course, because the only possibility where neither of those two transformations is feasible is the one where both goats and lions are zero: for one, this would be a solution of the problem, but more importantly, we know that we can never get there, because this solution lies in a different forest class.
How many steps do we need to arrive at the stable state? As we are only using d1 and d3, and both of those reduce m by one, that's clearly m steps.
Bottom line for <eoo>: The optimal strategy consists of m steps and is, in general, not unique - any feasible combination of m steps of d1 and d3 that eliminates both goats and wolfs is an optimal solution. [The proof (or rejection) that all feasible combinations of m steps of d1 and d3 end up at the optimal solution is left as an exercise for the reader ;]
The forest class <eee> is special, because we can choose which of the three species is to survive. Once we have chosen that lucky species, everything goes along the same lines as for the <eoo> case. Of course, we want to choose that species such that we need a minimum number of steps: that is, we choose the species with the smallest maximum of the two remaining species.
We already know which animal survives, and the survivor's count is easily determined: the initial number of animals is N=g+w+l, the optimal solution takes m steps, and each step reduces the total number of animals by one. Thus, the number of surviving animals is N-m.
The forest given in the example was (17,55,6), and is of class <eoo>. From that it follows that we have to eliminate goats and wolfs, and lions will survive. The maximum of the number of species we want to get rid of is 55, and it corresponds to wolfs. So the optimal solution will take us 55 devouring steps, and as the total number of animals is N=17+55+6=78, there will be 78-55=23 lions left in the end.
The transformations d1, d2 and d3 all flip even to odd numbers and vice versa: that means under each of these transformations, we hop back and forth between columns two and three in the above table, but we never go to a different row. That is, there are four distinct classes of magic forests, in the sense that during its entire lifetime, a forest always stays in its class.
Solution Strategy
The "optimal" solution strategy we are trying to find is the one with the maximum number of animals surviving. As each devouring step reduces the number of animals by one, this corresponds to the shortest path to a stable forest.
Given an initial forest, we first determine the class it belongs to. For the three classes <eoo>, <oeo> and <ooe>, there is only one choice: we have to eliminate those species that belong to the even number (that's goats and wolfs for <eoo>, goats and lions for <oeo> and wolfs and lions for <ooe>). For the first class, there is an initial choice of which two species to eliminate.
Strategy for <eoo>
Let's look at <eoo> first, <oeo> and <ooe> will work out the same. For an <eoo> forest, we know the solution will be (0, 0, u), where u is the number of lions remaining in the end. To get there, we have to get rid of goats as well as wolfs. Let m be max(g,w), i.e., the species with the greater number of animals out of the two species we want to get rid of, and assume it is the wolfs in this example. That means we have to get rid of the wolfs, and there are two transformations that bring down the number of wolfs: d1 and d3. The shortest strategy will thus contain only those two transformations, because anything that increases the number of wolfs will take us longer.
Is it possible to reach a stable state with just these two transformations? Of course, because the only possibility where neither of those two transformations is feasible is the one where both goats and lions are zero: for one, this would be a solution of the problem, but more importantly, we know that we can never get there, because this solution lies in a different forest class.
How many steps do we need to arrive at the stable state? As we are only using d1 and d3, and both of those reduce m by one, that's clearly m steps.
Bottom line for <eoo>: The optimal strategy consists of m steps and is, in general, not unique - any feasible combination of m steps of d1 and d3 that eliminates both goats and wolfs is an optimal solution. [The proof (or rejection) that all feasible combinations of m steps of d1 and d3 end up at the optimal solution is left as an exercise for the reader ;]
Strategy for <eee>
The forest class <eee> is special, because we can choose which of the three species is to survive. Once we have chosen that lucky species, everything goes along the same lines as for the <eoo> case. Of course, we want to choose that species such that we need a minimum number of steps: that is, we choose the species with the smallest maximum of the two remaining species.
Number of Surviving Animals
We already know which animal survives, and the survivor's count is easily determined: the initial number of animals is N=g+w+l, the optimal solution takes m steps, and each step reduces the total number of animals by one. Thus, the number of surviving animals is N-m.
Solution for the Example Forest
The forest given in the example was (17,55,6), and is of class <eoo>. From that it follows that we have to eliminate goats and wolfs, and lions will survive. The maximum of the number of species we want to get rid of is 55, and it corresponds to wolfs. So the optimal solution will take us 55 devouring steps, and as the total number of animals is N=17+55+6=78, there will be 78-55=23 lions left in the end.
Conclusion
I'll go home now and put on my sack cloth and ashes - that took me a lot longer than the 2.5 mins it is supposed to take 16 year old students.
