Solving the River Crossing Puzzle with Go
Programming Snapshot – Go Game States
How does a ferryman transport a wolf, a goat, and a cabbage across a river in a boat that can only carry the ferryman plus one item at a time, without the wolf eating the goat or the goat eating the cabbage while left together back on shore? Mike programs the solution in Go.
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.
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).
Listing 1
Program Start
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"
.
Listing 2
passenger.go
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.
Listing 3
shore.go
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.
Buy this article as PDF
(incl. VAT)