Re: Factor

About ten years ago, there was a blog post about a Goats, Wolves, and Lions puzzle that was problem #30 from the 2014 Austrian “Math Kangaroo” contest. The puzzle was kind of fun and the implementation prompted some decent follow-up at the time.

There are three species of animals in a magic forest: lions, wolves and goats. Wolves can devour goats, and lions can devour wolves and goats. ("The stronger animal eats the weaker one".) As this is a magic forest, 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.

At the very beginning, there are 17 goats, 55 wolves and 6 lions in the forest. After every meal, there is one animal fewer than before; therefore after some time, there is no devouring possible any more.

What is the maximum number of animals who can live in the forest then?

There are two versions of this puzzle: one that doesn’t give any possible answers and the kangaroo version that gives these multiple choice options:

(A) 1
(B) 6
(C) 17
(D) 23
(E) 35

The original post followed up with a description of three ways to solve the Goats, Wolves, and Lions problem and then a brute-force solution in Fortran followed by a comparison of solutions in different programming languages of which the fastest was a C++ version and then someone else described some experiments and improvements in some other languages. The best answer, maybe, was the one that described using linear programming with lpsolve for an algorithmic solution that beats all the previous versions and even reduces to a simple formula that you can calculate by hand!

I had created a solution in Factor at the time, but had never written about it. Below, I want to go over that approach it and compare it with the performance of the “fastest” C++ version.

We are going to store our forest state as an array of three integers representing the number of goats, wolves, and lions. We can build words to represent each possible next state, or f if that next state is not possible:

: wolf-devours-goat ( forest -- forest/f )
    first3 { [ pick 0 > ] [ over 0 > ] } 0&&
    [ [ 1 - ] [ 1 - ] [ 1 + ] tri* 3array ] [ 3drop f ] if ;

: lion-devours-goat ( forest -- forest/f )
    first3 { [ pick 0 > ] [ dup 0 > ] } 0&&
    [ [ 1 - ] [ 1 + ] [ 1 - ] tri* 3array ] [ 3drop f ] if ;

: lion-devours-wolf ( forest -- forest/f )
    first3 { [ dup 0 > ] [ over 0 > ] } 0&&
    [ [ 1 + ] [ 1 - ] [ 1 - ] tri* 3array ] [ 3drop f ] if ;

We can track the set of next states by adding them to a set:

: next-forests ( set forest -- set' )
    [ wolf-devours-goat [ over adjoin ] when* ]
    [ lion-devours-goat [ over adjoin ] when* ]
    [ lion-devours-wolf [ over adjoin ] when* ] tri ;

Given a sequence of forest states, we can produce the next states after a meal has occurred:

: meal ( forests -- forests' )
    [ length 3 * <hash-set> ] keep [ next-forests ] each members ;

A forest is stable if there are no goats and either no wolves or no lions, or goats and no wolves and no lions:

: stable? ( forest -- ? )
    first3 rot zero? [ [ zero? ] either? ] [ [ zero? ] both? ] if ;

We can say that devouring is possible if there are no stable forests:

: devouring-possible? ( forests -- ? )
    [ stable? ] none? ;

And maybe we want to be able to get all the stable forests:

: stable-forests ( forests -- stable-forests )
    [ stable? ] filter ;

So, to find our answer, we can just iterate, until we find our first stable forest state:

: find-stable-forests ( forest -- forests )
    1array [ dup devouring-possible? ] [ meal ] while stable-forests ;

And, now we can answer the original question – which is (D):

IN: scratchpad { 17 55 6 } find-stable-forests .
{ { 0 0 23 } }

We can compare the performance of Factor with the C++ version from that earlier blog post and see that ours is around 5.7x slower:

IN: scratchpad [ { 317 355 306 } find-stable-forests ] time .
Running time: 4.878022334 seconds
{ { 0 0 623 } }

versus

$ time ./magic_forest 317 355 306
0, 0, 623
./magic_forest 317 355 306  0.80s user 0.04s system 99% cpu 0.848 total

One of the reasons for that is we’re doing a lot of generic dispatch, not specifying types anywhere, and passing arrays around that we are accessing and allocating frequently. We could fix some of these issues and make ours faster, but ultimately approaching this as a linear programming exercise beats all the iterative approaches anyway.

Still, there are probably performance lessons to be learned here…