5.1 Missionaries and Cannibals

Refal is a language oriented toward construction and manipulation of certain objects which are represented by Refal expressions. Control structure of a Refal program is very simple and straightforward: pattern matching and substitution. It is the structure of the objects manipulated by the program that carries the burden of keeping all pertinent information. Successful programming in Refal is primarily a successful choice of the basic data structures. Representation of the problem to be solved in terms of Refal expressions is the first and the most important part of Refal programming. This representation must, firstly, be transparent to the human eye and, secondly, allow us to express the main operations on data in terms of transformation of objects according to some simple patterns. If these two requirements are met, you have good chances to write a Refal program which will be both compact, readable, and easy to debug.

Consider the well-known problem ``Missionaries and Cannibals''. Three missionaries and three cannibals come to the bank of a river and see a boat. They want to cross the river. The boat, however, can carry no more than two people. There is a further restriction. At no time should the number of cannibals on either bank of the river (including the moored boat) exceed the number of missionaries (because the missionaries would then be overpowered and eaten). How (if at all) is it possible to cross the river?

The general method of solving such problems is:

  1. Define the set of all possible situations, or states, implied by the problem (the space of states). One state must be defined as initial. And there must be a criterion to tell whether a state is acceptable as a solution to the problem (the goal to achieve).
  2. Define the set of possible moves that we can make toward the solution of the problem. A move is an operation which transforms one (current) state of affairs into another (next) state. Usually not every move will be possible in every state, but for each state there will be a subset of admissible moves.
  3. These two sets define a tree of achievable states, which has the initial situation as its root. We now must search this graph to find a path (if any) which leads to a solution.

How shall we represent situations in our problem? Sub-expressions in Refal represent sub-systems of the overall system. Our system clearly includes two main sub-systems: the left and the right banks of the river. Thus we can use the pattern:

  (e.Left-bank)(e.Right-bank) 

Atomic objects can be represented by Refal symbols. We shall use 'M' for a missionary and 'C' for a cannibal. The situation where there are three missionaries and one cannibal on the left bank, and two cannibals on the right bank can then be represented as

  ('MMMC')('CC')

Since the order in which people are listed is of no significance, three missionaries and one cannibal can also be represented as 'CMMM' , 'MCMM' , etc. Should we leave this freedom of representation or is it better to fix a definite order? The latter is clearly preferable. We should anticipate the use of our Refal representations in patterns. With an arbitrary order of symbols, we shall use the pattern e1'M'e2 to determine whether there are missionaries on a given bank. This pattern includes an open e-variable which means a scan of the expression. If we agree to list missionaries before cannibals, the same can be done with the simpler pattern 'M'e1 . To find out whether there is at least one cannibal we use e1'C' , and to find out whether both kinds of humans are there, 'M'e1'C' . We are exploiting here the fact that there are only two kinds of people.

We now must take care of the boat. One way is to include it as a symbol 'B' in the contents of the corresponding bank, say:

  ('MMMC')('BCC')
However, this will not be very convenient. To abstract from the location of the boat, we will have to use two patterns:
  ('B'e1)(e2) = (e1)(e2);
  (e1)('B'e2) = (e1)(e2);
The boat should not be counted as equal with humans; its location is an independent dimension. A better idea is to add one symbol -- 'L' or 'R' to indicate whether the boat is on the left or on the right bank. We shall assume that the whole company comes to the left bank of the river. Then the representation of the initial situation (state) is:
  L(e.Left-bank)(e.Right-bank) 
NOTE:  We used characters to stand for missionaries and cannibals (note the quotes), but identifiers L and R for the position of the boat. This is not of great importance. Usually the program looks better when those elements which may form sequences are represented by characters, while the elements which are used individually are represented by identifiers.

We now turn to the set of possible moves. A move is a crossing of the river in a boat. Since the boat can take no more than two people, and cannot go by itself, there are five possible moves which we will represent by their sequential numbers in the following table:

  Move   The boat takes:
1 two missionaries
2 two cannibals
3 a missionary and a cannibal
4 a missionary
5 a cannibal

Not all moves are physically possible in every state. For instance, if the boat is on the left bank and there is only one missionary on this bank, then move 1 is impossible. But even if a move is possible, we must still check that it is admissible, i.e., does not result in manslaughter. Since a move is a transformation of the current state, we define:

  * Move
  * <Move s.Move e.State> == s.New-State
  Move { sM eS = <Admiss <Try sM eS>>; }

The function Try will transform the state. If the move is impossible in the given state, the new, fictitious, state will be represented by the symbol Imposs. Admiss will check that the resulting state satisfies the requirements. If it does, the function will leave the state unchanged. If the requirements are not satisfied, it will replace the state by Imposs . Here is a simple and straightforward definition of Try which uses pattern-matching abilities of Refal and is abundant with comments:

  * Try a move 
  Try {
  * Boat on left bank
  * MM crossing
     1 L('MM'e1)(e2) = R(e1)('MM'e2);
  * CC crossing
     2 L(e1'CC')(e2) = R(e1)(e2'CC');
  * MC crossing
     3 L(e1'MC'e2)(e3) = R(e1 e2)('M'e3'C');
  * M crossing
     4 L('M'e1)(e2) = R(e1)('M'e2);
  * C crossing
     5 L(e1'C')(e2) = R(e1)(e2'C');
  * Boat on right bank
  * MM crossing
     1 R(e1)('MM'e2) = L('MM'e1)(e2);
  * CC crossing
     2 R(e1)(e2'CC') = L(e1'CC')(e2);
  * MC crossing
     3 R(e1)('M'e2'C') = L('M'e1'C')(e2);
  * M crossing
     4 R(e1)('M'e2) = L('M'e1)(e2);
  * C crossing
     5 R(e1)(e2'C') = L(e1'C')(e2);
  * Otherwise move impossible
     s.Mv eS = Imposs;
        }

The admissibility function checks that the ``no-eating condition'' is met on both banks:

  * Admissibility of the move
  Admiss {
     s.Side(eL)(eR), 
            <No-eat eL>: T, <No-eat eR>: T =
   	         s.Side(eL)(eR);   
     eS = Imposs;
          }
   
  * No eating missionaries
  No-eat {
  *1. Both missionaries and cannibals are present
     'M'e1'C' = <Compare e1>;
  * Otherwise OK
     e1 = T; }
   
  * Both M and C on the bank.Compare the numbers.
  Compare {
     'C'e1 = F;
     'M'e1'C' = <Compare e1>;
     e1 = T; }

The tree of achievable states has states as its nodes and moves as edges. A move and the resulting state can be nicely combined into one unit which we shall refer to as a link:

  (s.Move'='e.State) 
where the equality sign is inserted solely for readability. To fit the initial state into this format, we shall see it as resulting from the fictitious primordial move with the special code . The tree of states begins as follows:
  (0 = Sinit)(1 = S1)(1 = S11)...
                     (2 = S12)...
                     ...
                     (5 = S15)...
             (2 = S2)(1 = S21)...
                     (2 = S22)...
             ...

We shall adopt the depth-first method of searching this tree and a simple fixed order of moves to try: 1, 2, etc. to 5. Then we do not really need to work with a tree structure. We can keep only the chain of links which makes up the path from the root to the current node.

Let us call the searching function Search . It is called at the beginning of the program with the initial link as the argument:

  $ENTRY Go { =
           <Search (0'='L('MMMCCC')())>; };
Now we want to consider all possible cases we can encounter in the search.

The problem is solved when the state in the last link is our goal state. We have the sentence:

  e1 (s.M'='R()('MMMCCC')) =  
        <Path e1 (s.M'='R()('MMMCCC'))>;
Then we only have to print the solution nicely, which will be the business of the function Path .

This sentence will be tried first. As long as it does not work we continue the search and lengthen our path by adding a new link resulting from move 1 :

  e1 (sM'='eS) = 
      <Search e1 (sM'='eS) (1'='<Move 1 eS>)>;

Now that we have written it, we see that the last state in the path may be Imposs . Therefore, before lengthening the path we must find out whether the last state is an admissible state or Imposs , and in the latter case take the corresponding action. As always in Refal, the sentence (or sentences) for the special case when eS is Imposs must precede the sentence(s) for the general case.

If the result of the last move is Imposs , we try the next move, i.e., replace the last link as follows:

  e1 (s.Mp'='eS)(s.M'='Imposs), 
                     <+ s.M 1>: s.Mn = 
          <Search e1 (s.Mp'='eS)
                     (s.Mn'='<Move s.Mn eS>)>;
This assumes, however, that s.M is less than 5. If it is 5 then there are no more moves available, and we must backtrack, i.e., remove the last link and take the next move (if possible) in the preceding link. To take the next move in the preceding link according to the general rule we replace its state by Imposs :
  e1 (s.Mp'='eS) (5'='Imposs) =  
             <Search e1 (s.Mp'='Imposs)>;

Having written a Refal sentence, i.e., a replacement rule, one should analyze it with the goal of seeing if there are possible exceptions from it. We have been using this method above and we should use it now again. If the preceding link is the initial link, i.e., s.Mp is 0, then there is no way to backtrack and we must declare that the problem has no solution:

  (0'='eS) (5'='Imposs) = 
       <Prout 'The problem has no solution'>;

There is one more situation which we must consider. When we achieve a state that has already been passed before, i.e., can be found in one of the links of the path, we do not want to examine its continuations because they are being examined as continuations of the previous entry of this state. Thus we replace a repeated state by Imposs :

  e1 (s.Mp'='eS) e2 (s.M'='eS) =
     <Search e1 (s.Mp'='eS) e2 (s.M'='Imposs)>;

Now we have to collect all six sentences in the right order. Together with other function definitions (we leave it to the reader to figure out how the function Path works), we have the following program:


  * Missionaries and Cannibals
  $ENTRY Go { =
       <Search (0'='L('MMMCCC')())>; };
   
  Search {
  *1. The goal found
    e1 (s.M'='R()('MMMCCC')) =  
              <Path e1 (s.M'='R()('MMMCCC'))>;
  *2. Impossible state. No backup. No solution.
    (0'='eS) (5'='Imposs) = 
           <Prout 'The problem has no solution'>;
  *3. Impossible state. No next move. Back up.
    e1 (s.Mp'='eS) (5'='Imposs) =  
                  <Search e1 (s.Mp'='Imposs)>;
  *4. Impossible state. Do next move.
    e1 (s.Mp'='eS)(s.M'='Imposs), 
                       <+ s.M 1>: s.Mn =
            <Search e1 (s.Mp'='eS)
                       (s.Mn'='<Move s.Mn eS>)>;
  *5. Repeated state. Equate to impossible.
    e1 (s.Mp'='eS) e2 (s.M'='eS) =
        <Search e1 (s.Mp'='eS) e2 (s.M'='Imposs)>;
  *6. Down the tree.
    e1 (s.M'='eS) = 
         <Search e1 (s.M'='eS) (1'='<Move 1 eS>)>;
        }
   
  * Move
  Move { eS = <Admiss <Try eS>>; }
   
  * Try a move 
  Try {
  * Boat on left bank
  * MM crossing
     1 L('MM'e1)(e2) = R(e1)('MM'e2);
  * CC crossing
     2 L(e1'CC')(e2) = R(e1)(e2'CC');
  * MC crossing
     3 L(e1'MC'e2)(e3) = R(e1 e2)('M'e3'C');
  * M crossing
     4 L('M'e1)(e2) = R(e1)('M'e2);
  * C crossing
     5 L(e1'C')(e2) = R(e1)(e2'C');
  * Boat on right bank
  * MM crossing
     1 R(e1)('MM'e2) = L('MM'e1)(e2);
  * CC crossing
     2 R(e1)(e2'CC') = L(e1'CC')(e2);
  * MC crossing
     3 R(e1)('M'e2'C') = L('M'e1'C')(e2);
  * M crossing
     4 R(e1)('M'e2) = L('M'e1)(e2);
  * C crossing
     5 R(e1)(e2'C') = L(e1'C')(e2);
  * Otherwise move impossible
     s.M eS = Imposs;
        }
   
  * Admissibility of the move
  Admiss {
    s.Side(eL)(eR), <Noeat eL>:T, <Noeat eR>:T =
   	          s.Side(eL)(eR);   
    eS = Imposs;
         }
   
  * No eating missionaries
  Noeat {
  *1. Both missionaries and cannibals are present
    'M'e1'C'= <Compare e1>;
  * Otherwise OK
     e1 = T; }
   
  * Both M and C on the bank.Compare the numbers.
  Compare {
     'C'e1 = F;
     'M'e1'C'= <Compare e1>;
     e1 = T; }
   
  * Print the path leading to the goal
  Path {
     (0'='eS) e2 = 
      <Prout 'The initial state:            'eS>
      <Path e2>;
     (s.M'='s.Side eS) e2, 
          <Look-up s.M In <Table>>: e.Who =
          <Prout e.Who ' crossing to  's.Side 
                ' bank:  state ' s.Side eS>
          <Path e2>;
      = ;      
        }
   
  Look-up { sM In e1 sM(e.Who) e2 = e.Who }
  Table { = 
       1('MM') 2('CC') 3('MC') 4('M ') 5('C ') }

Let us name the file with this program mmmccc.ref . Translate by refc and run:

  refgo mmmccc -nt
(the flags will cause a printout of the number of Refal steps and the time used). The output is:
  The initial state:              L (MMMCCC)()
  CC crossing to  R  bank:  state R (MMMC)(CC)
  C  crossing to  L  bank:  state L (MMMCC)(C)
  CC crossing to  R  bank:  state R (MMM)(CCC)
  C  crossing to  L  bank:  state L (MMMC)(CC)
  MM crossing to  R  bank:  state R (MC)(MMCC)
  MC crossing to  L  bank:  state L (MMCC)(MC)
  MM crossing to  R  bank:  state R (CC)(MMMC)
  C  crossing to  L  bank:  state L (CCC)(MMM)
  CC crossing to  R  bank:  state R (C)(MMMCC)
  M  crossing to  L  bank:  state L (MC)(MMCC)
  MC crossing to  R  bank:  state R ()(MMMCCC)
Exercise 5.1 * The effort necessary to find a solution (as well as the solution itself) depends on the order in which possible moves are tried. We have used the same order of moves when the boat is on the left and right banks. However, these orders may be different. Modify the program above by changing the order of moves so that it runs faster and slower than our program.
Footnotes:
  1. There are no answers to exercises in this chapter.