Sorting with Go

To enable the algorithm to easily determine later whether two bank objects have identical passengers (to detect already-seen states), it compares their string representations generated by String() in line 12, character by character. Since the original order of the arrays is lost after manipulating game states, line 13 sorts them according to passenger numbers. The Passenger elements are in fact plain vanilla integers, but the strict type-enforcing Go compiler refuses to sort them with the standard integer sorting function, sort.Ints(). This is why Listing 4 steps in to teach Go how to sort an array of Passenger values. It defines a Passengers (note the plural) type plus three functions that Go requires the programmer to define in order to sort arbitrary data types.

01 package main
02
03 type Passengers []Passenger
04
05 func (p Passengers) Len() int {
06   return len(p)
07 }
08 func (p Passengers) Swap(i, j int) {
09   p[i], p[j] = p[j], p[i]
10 }
11 func (p Passengers) Less(i, j int) bool {
12   return p[i] < p[j]
13 }

The first function is named Len() and specifies the length of the array to be sorted. Listing 4 simply determines this using Go's built-in len() function. The second function is Swap() and shows the compiler how to swap two elements at the index positions i and j during sorting. This is easily done in Go, because it understands the syntax a,b = b,a. Thirdly, the sort needs a Less() function, which returns a true value if its first parameter is smaller than the second. With the present array of integers, a numerical comparison of the two elements using p[i] < p[j] gives the correct results.

With this tool in Listing 4, Listing 3 can now call sort.Sort(Passengers(...)) on an array of Passenger types, which the function then sorts in-place [4].

From State to State

Listing 5 defines the game states (i.e., the situation on both banks), with the State data type. Go does not support classes, but it offers object orientation with structures and methods operating on the data defined in the structure.

01 package main
02
03 import (
04   "fmt"
05 )
06
07 type State struct {
08   west Shore
09   east Shore
10   prev *State
11 }
12
13 func (s State) IsValid() bool {
14   return s.west.IsValid() &&
15     s.east.IsValid()
16 }
17
18 func (s State) String() string {
19   return fmt.Sprintf("%s | %s",
20     s.west.String(),
21     s.east.String(),
22   )
23 }
24
25 func (s *State) Move(p Passenger) {
26   from := &s.west
27   to := &s.east
28   if to.Has(Ferryman) {
29     from, to = to, from
30   }
31   from.Move(p, to)
32 }
33
34 func (s State) IsFinished() bool {
35   return len(s.west.passengers) == 0
36 }
37
38 func (s State) Copy() State {
39   d := State{}
40   d.west = s.west.Copy()
41   d.east = s.east.Copy()
42   return d
43 }
44
45 func (s State) Successors() []State {
46   startShore := s.east
47   if s.west.Has(Ferryman) {
48       startShore = s.west
49   }
50   results := []State{}
51
52   for _, passenger :=
53          range startShore.passengers {
54     candidate := s.Copy()
55     candidate.Move(passenger)
56     if passenger != Ferryman {
57       candidate.Move(Ferryman)
58     }
59
60     if candidate.IsValid() {
61       results = append(results, candidate)
62     }
63   }
64
65   return results
66 }

It is important to note the difference between writing and reading methods. A normal "receiver" (the object preceding the function name after the func keyword, as in the IsValid() function in line 13) gives the function read-only access to the data. The function can write, but only into a copy of the object, which disappears after the function has terminated.

For persistent writes, you need to use a pointer receiver, as shown, for example, in Move() from line 25. No matter whether Move() is a normal receiver or a pointer (as indicated by a * preceding the receiver in the function definition), the invocation of state.Move() by the caller looks completely identical. This means that programmers have to be very careful. If the pointer definition is missing by mistake, no errors occur – but nothing is written correctly, which (and this has been scientifically proven) leads to much wailing and gnashing of teeth on the part of the programmer.

Every state object holds two shore objects west and east, as well as a pointer prev to the state from which it was derived. If the algorithm later stumbles upon a solved state, the path to the target can be traced backwards using this pointer chain. The ferryman's location determines on which shore the next change can happen. Line 26 defines the direction as "from west to east," but reverses from and to in line 29, if it finds that the ferryman isn't on the west bank, but on the east bank instead.

Bosses and Workers

A state is considered permissible if confirmed by IsValid() from line 13 in Listing 5. It examines both of its shore objects, west and east, and returns an okay if both their IsValid() functions say so. The string representation of the State object is calculated by the object's String() method from line 18 onwards. In turn, it delegates the hard work to the two bank objects, and then, acting as a higher-level authority, combines the two partial results into a string with a pipe sign as the separator. A copy of a state is created by Copy() in line 38. The function makes copies of the two shores and again delegates the hard work to the individual shore objects.

The final game state is reached when IsFinished() returns a true value starting in line 34. To determine this state, the method simply checks whether there is any candidate left on the west bank. If that's true and there was no cheating, then the ferryman and all passengers should all be safe and sound on the east side.

A state object's most important task is to find subsequent states so that the solver can later build the search tree. The Successors() method in line 45 tries to send the ferryman to the other bank either alone or with a passenger waiting on the same bank. It blindly tries all possibilities and then checks with IsValid() in line 60 to see whether a valid state has been created this way. If so, it appends it to the result list that the method returns to the calling solver.