Whether it is a wolf, a goat, and a cabbage, or one of the many variations on this scenario, keeping the participants safe during passage is part of the classic river crossing logic puzzle [1]. Humans find a solution to these brainteasers by trial and error. Computers, on the other hand, determine the solution by exploring trees of interlinked state sequences, eventually arriving at the desired final state by following one of many different available paths [2].

Before crossing the river, the ferryman, the wolf, the goat, and the cabbage are initially on the west bank. The ferryman can only take one of the three candidates into the boat and cross over to the east bank. During the crossing, he has to take care not to leave the wolf and goat alone on the bank, because the wolf would eat the goat. The same applies to the goat and the cabbage, as goats like to eat cabbage.

The riddle seems unsolvable at first. For example, once the ferryman has crossed the river with the goat and returns on an empty run, the only choice he has is between the wolf and the cabbage as the next candidate. However, neither will get along with the goat on the other bank. The trick is that the ferryman can also carry passengers on the return journey, thus ensuring that he never leaves a dangerous combination (goat/cabbage or wolf/goat) unattended.

Ferry Algorithm

In order to solve this teaser with an algorithm, the program has to model the problem as a sequence of states that assign the candidates to either the west or the east bank. In the initial state, the ferryman, wolf, goat, and cabbage are all sitting on the west bank, and the east bank is empty. In a possible second state, the goat sits on the east bank, while the wolf, cabbage, and ferryman are on the west bank after the ferryman has completed his return journey.

Each state maps the two banks, with each bank accommodating a number of candidates. From a given state, the system can switch to one or more subsequent states, some of which are not allowed, for example, because the wolf and goat would be left unattended on the same bank.

Starting from the initial state, the algorithm tries out all possible subsequent states to determine whether they are permissible. If a state checks out, the algorithm searches for further subsequent states on this basis, and so the merry dance continues. If the program at some point finds itself in a state in which all the candidates are sitting on the east bank, the puzzle is solved. The program then outputs the recorded path that led to this state, and the astounded user can now marvel at a solution to the problem.

Depth or Breadth First

In the diagram in Figure 1, the algorithm starts with the state at the top, where all participants (W = wolf, G = goat, C = cabbage, F = ferryman) are located in the left part of the rectangle (i.e., on the west bank). If the algorithm then moves to the next node bottom left, it finds a state where the cabbage and ferryman are on the east bank. On the left bank, you have the wolf and the goat – but this is impermissible according to the rules, so the algorithm discards this state (shown with a red X) and naturally doesn't progress to any subsequent states from this dead end.

Figure 1: The algorithm moves from the initial state (on top) through all possible subsequent states and discards impermissible ones.

There are two strategies for traversing the states in this tree structure: breadth first and depth first. Breadth first discovers all direct subsequent states of a state before it drills deeper into their successors. Depth-first, on the other hand, drills as deep as it can, visiting children and grandchildren, before it visits siblings at the same level.

In this river crossing puzzle, the goal is to find a solution with as few steps as possible, so breadth first is the right approach, since depth first might find a much too complicated solution.

Once the algorithm is determined, the programming can begin. For the sake of clarity, the code is divided into several listings [3]. If you want to start right away, launch the problem solver with the instructions in Listing 1, which compiles the code without any additional external libraries (i.e., with plain vanilla Go).

01 $ go build solver.go passenger.go sort.go sort.go shore.go state.go
02 $ ./solver

Listing 2 models the passengers and the ferryman using integer values defined by const. The =iota assignment tells the compiler to assign the integer values 0, 1, ... to the constants Goat, Wolf, and so on. In order to be able to convert them back into strings for the user's entertainment, the String() method on the Passenger type defines a slice of strings. Given one of the previously defined constants, the function reaches into the slice to pull out the corresponding string element, because elements in Go's string slices are handily indexed from   onward, just like the =iota-defined integer constants. In general, a String() method in Go is used to convert self-defined types into strings as soon as they are found in a string context – for example, if Printf() wants to output types as strings with "%s".

01 package main
02
03 type Passenger int
04
05 const (
06   Goat Passenger = iota
07   Wolf
08   Cabbage
09   Ferryman
10 )
11
12 func (p Passenger) String() string {
13   return []string{"Goat", "Wolf",
14     "Cabbage", "Ferryman"}[p]
15 }

Next, Listing 3 defines Shore as a data structure to represent a river bank including its methods. The passengers array stores the waiting passengers within the Shore structure starting in line 8. All elements are of the Passenger type – that is, they are represented as named integer constants defined in Listing 2 (e.g., "Wolf"). Both Listing 2 and Listing 3 define the same main package; therefore they can both reference each other's data structures.

01 package main
02
03 import (
04   "fmt"
05   "sort"
06 )
07
08 type Shore struct {
09   passengers []Passenger
10 }
11
12 func (s Shore) String() string {
13   sort.Sort(Passengers(s.passengers))
14   return fmt.Sprintf("%s", s.passengers)
15 }
16
17 func (s Shore) Copy() Shore {
18   c := Shore{}
19   c.passengers = make([]Passenger,
20     len(s.passengers))
21   copy(c.passengers, s.passengers)
22   return c
23 }
24
25 func (s *Shore) Add(p Passenger) {
26   s.passengers = append(s.passengers, p)
27 }
28
29 func (s *Shore) Remove(p Passenger) {
30   result := []Passenger{}
31   for _, passenger := range s.passengers {
32     if passenger != p {
33       result = append(result, passenger)
34     }
35   }
36   s.passengers = result
37 }
38
39 func (s *Shore) Move(p Passenger,
40                      t *Shore) {
41   s.Remove(p)
42   t.Add(p)
43 }
44
45 func (s Shore) Has(p Passenger) bool {
46   for _, passenger := range s.passengers {
47     if passenger == p {
48       return true
49     }
50   }
51   return false
52 }
53
54 func (s Shore) IsValid() bool {
55   if s.Has(Ferryman) {
56     return true
57   }
58   if s.Has(Wolf) && s.Has(Goat) {
59     return false
60   }
61   if s.Has(Goat) && s.Has(Cabbage) {
62     return false
63   }
64   return true
65 }

Deep Copies

Go won't automatically copy the deeper parts of a nested data structure. To create a deep copy, the programmer has to manually define the necessary steps, and, for example, explicitly copy arrays that reside within the structure. The Copy() method starting in line 17 of Listing 3 acts on a given Shore object and first initializes a new, empty object. It then uses make to allocate a passenger array of the same length in the copy, and then uses the built-in copy() function to copy the elements from the original to the copy, after which it returns the latter to the caller. With this Shore helper function, the caller can easily duplicate game states and build new ones from existing ones by inflicting gradual changes.

To assign new passengers to a particular Shore object, to remove them again, to move them to a new shore side, or to query whether a passenger is stationed on a particular shore, Listing 3 provides the methods Add(), Remove(), Move(), and Has() in lines 25 to 52. For example, a state object can later select one of its shore sides and use west.Has(Wolf) to retrieve a Boolean response (true/false) to the question as to whether the wolf is present.

The implementation shows a disadvantage of choosing an array as the data structure for storing passengers. To see if a certain passenger is present, a for loop has to run through all elements until it either finds them or returns false at the end if the search is unsuccessful. Removing a passenger actually tears a hole in the array, which a for loop then has to laboriously patch again by rebuilding the array without the removed passenger as shown in line 31. Alternatively, a map would provide faster access, but it has the disadvantage that the data stored in it is unsorted and has to be sorted later for display purposes.

The IsValid() method starting in line 54 checks whether the passengers present on a shore side are in compliance with the game rules or contradict them in any way. It more or less implements the algorithm's business logic. If the ferryman is present on one side, this is a valid state, because even wolf and goat get along just fine as long as there is a supervisor present. But if the ferryman is missing in this case, IsValid() in line 59 returns false, because the wolf would devour the goat without further ado. The same applies to the goat and the cabbage, when the method returns false if they're residing on a bank together without the ferryman present. On the other hand, if everything is okay, IsValid() returns true at then end.