Solving the River Crossing Puzzle with Go
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.
Listing 4
sort.go
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.
Listing 5
state.go
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.
« Previous 1 2 3 Next »
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Support Our Work
Linux Magazine content is made possible with support from readers like you. Please consider contributing when you’ve found an article to be beneficial.
News
-
So Long Neofetch and Thanks for the Info
Today is a day that every Linux user who enjoys bragging about their system(s) will mourn, as Neofetch has come to an end.
-
Ubuntu 24.04 Comes with a “Flaw"
If you're thinking you might want to upgrade from your current Ubuntu release to the latest, there's something you might want to consider before doing so.
-
Canonical Releases Ubuntu 24.04
After a brief pause because of the XZ vulnerability, Ubuntu 24.04 is now available for install.
-
Linux Servers Targeted by Akira Ransomware
A group of bad actors who have already extorted $42 million have their sights set on the Linux platform.
-
TUXEDO Computers Unveils Linux Laptop Featuring AMD Ryzen CPU
This latest release is the first laptop to include the new CPU from Ryzen and Linux preinstalled.
-
XZ Gets the All-Clear
The back door xz vulnerability has been officially reverted for Fedora 40 and versions 38 and 39 were never affected.
-
Canonical Collaborates with Qualcomm on New Venture
This new joint effort is geared toward bringing Ubuntu and Ubuntu Core to Qualcomm-powered devices.
-
Kodi 21.0 Open-Source Entertainment Hub Released
After a year of development, the award-winning Kodi cross-platform, media center software is now available with many new additions and improvements.
-
Linux Usage Increases in Two Key Areas
If market share is your thing, you'll be happy to know that Linux is on the rise in two areas that, if they keep climbing, could have serious meaning for Linux's future.
-
Vulnerability Discovered in xz Libraries
An urgent alert for Fedora 40 has been posted and users should pay attention.