Solving the River Crossing Puzzle with Go
Solution
All the solver in Listing 6 now needs to do is create the start state in main()
, assign the ferryman and all passengers to the west bank of the river, and call solve()
in line 8. There, a dynamically maintained todo
list in the form of an array of state objects determines states that still need to be examined. If one of them turns out to be the target state, IsFinished()
in line 25 returns a true value. If that's the case, the for
loop starting in line 27 then compiles the path to this end state by tracing back the states' prev
pointers. They guide the loop all the way to the start state, which has an uninitialized prev
pointer (i.e., it has a value of nil
in line with the Go standard). Line 32 builds an array from this inverse sequence using append()
in each step to insert new elements at the beginning of the existing array, resulting in a new array.
Listing 6
solver.go
01 package main 02 03 import ( 04 "errors" 05 "fmt" 06 ) 07 08 func solve(state State) ([]State, error) { 09 10 seen := make(map[string]bool) 11 todo := []State{state} 12 13 for len(todo) > 0 { 14 // pop off last element 15 lastidx := len(todo) - 1 16 s := todo[lastidx] 17 todo = todo[:lastidx] 18 19 // prevent cycles 20 if _, ok := seen[s.String()]; ok { 21 continue 22 } 23 seen[s.String()] = true 24 25 if s.IsFinished() { 26 path := []State{} 27 for cs := &s; cs.prev != nil; 28 cs = cs.prev { 29 c := cs.Copy() 30 path = append([]State{c}, path...) 31 } 32 path = append([]State{state}, path...) 33 return path, nil 34 } 35 36 for _, succ := range s.Successors() { 37 // insert new element at end 38 succ.prev = &s 39 todo = append([]State{succ}, todo...) 40 } 41 } 42 43 return []State{}, 44 errors.New("Can't solve") 45 } 46 47 func main() { 48 var state State 49 50 state.west.Add(Wolf) 51 state.west.Add(Cabbage) 52 state.west.Add(Ferryman) 53 state.west.Add(Goat) 54 55 solution, err := solve(state) 56 if err != nil { 57 panic(err) 58 } 59 60 fmt.Printf("Solution:\n") 61 62 for _, step := range solution { 63 fmt.Printf("[%s]\n", step) 64 } 65 }
Initially, the todo
list only contains the start state with all participants on the west bank. The for
loop from line 13 uses slice arithmetic to remove the last element of the todo
array in line 17 on every round. At the end of the loop, Successors()
searches for possible successors of the current state and inserts them at the beginning of the todo
array slice. This creates a queue where new elements are added from the left and picked from the right (first in, last out).
This procedure causes a breadth-first search [5] in the search tree (Figure 2). It scans the nodes layer by layer until it finds the target state. If we were to use a stack instead of a queue (first in, first out), for example, by appending new states to the right of the array and also fetching them from there, this would cause depth-first behavior in the tree. The algorithm would not proceed layer by layer, but would always advance immediately to the most deeply nested paths. It might find a solution faster – but not necessarily the shortest option, and often a very convoluted one.
To prevent the solver from getting stuck and, for example, sending the ferryman back and forth without any cargo (therefore generating an infinite number of subsequent states in the process), line 20 checks whether a proposed subsequent state has previously been processed. To do this, it checks the seen
map (a hash table) to discover whether the state's string representation already exists as a key. If so, the continue
statement in line 21 ignores this entry and triggers the next round in the for
loop.
Figure 3 shows the solver's output, which found a solution in seven moves. First, the ferryman takes the goat to the east bank, before coming back empty. The ferryman then takes the wolf to the east bank, but takes the goat back. When he reaches the west bank, he grabs the cabbage and leaves the goat there. He takes the cabbage to the east bank, where the wolf is waiting but is no threat to the cabbage. Now the ferryman only has to cross back without cargo and then take the goat to the east bank. The whole crew has then arrived safely without any incidents.
Even More
Once programmed, the solver can also be expanded if required. How about an additional passenger who is rather mellow and won't threaten anyone, for example, a salmon? Quickly added to Listing 2's const
construct as Salmon
and wired into the main()
function in Listing 6 with state.west.Add(Salmon)
, the solver will find a solution for this modified problem as well, although it will be a bit more complicated. Figure 4 shows the nine steps necessary for the entire crew to safely arrive on the eastern shore.
In this case, the ferryman first takes the goat, then the salmon, and then the cabbage. But now he cannot return without a cargo to the wolf waiting on the west bank, because the goat would eat the cabbage. Instead, he takes the goat back, crosses with the wolf, and then returns without cargo to pick up the goat on the west bank for the final crossing. A human puzzle fan would have tinkered with this for a while, but for the algorithm it's just another routine task, solved in a fraction of a second.
Infos
- River crossing puzzle: https://en.wikipedia.org/wiki/River_crossing_puzzle
- "Classic Computer Science Problems in Python": https://www.manning.com/books/classic-computer-science-problems-in-python
- All listings for this article: ftp://ftp.linux-magazine.com/pub/listings/linux-magazine.com/232/
- In-place algorithms https://en.wikipedia.org/wiki/In-place_algorithm
- Breadth-first search: https://en.wikipedia.org/wiki/Breadth-first_search
« Previous 1 2 3
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
-
Gnome 47.1 Released with a Few Fixes
The latest release of the Gnome desktop is all about fixing a few nagging issues and not about bringing new features into the mix.
-
System76 Unveils an Ampere-Powered Thelio Desktop
If you're looking for a new desktop system for developing autonomous driving and software-defined vehicle solutions. System76 has you covered.
-
VirtualBox 7.1.4 Includes Initial Support for Linux kernel 6.12
The latest version of VirtualBox has arrived and it not only adds initial support for kernel 6.12 but another feature that will make using the virtual machine tool much easier.
-
New Slimbook EVO with Raw AMD Ryzen Power
If you're looking for serious power in a 14" ultrabook that is powered by Linux, Slimbook has just the thing for you.
-
The Gnome Foundation Struggling to Stay Afloat
The foundation behind the Gnome desktop environment is having to go through some serious belt-tightening due to continued financial problems.
-
Thousands of Linux Servers Infected with Stealth Malware Since 2021
Perfctl is capable of remaining undetected, which makes it dangerous and hard to mitigate.
-
Halcyon Creates Anti-Ransomware Protection for Linux
As more Linux systems are targeted by ransomware, Halcyon is stepping up its protection.
-
Valve and Arch Linux Announce Collaboration
Valve and Arch have come together for two projects that will have a serious impact on the Linux distribution.
-
Hacker Successfully Runs Linux on a CPU from the Early ‘70s
From the office of "Look what I can do," Dmitry Grinberg was able to get Linux running on a processor that was created in 1971.
-
OSI and LPI Form Strategic Alliance
With a goal of strengthening Linux and open source communities, this new alliance aims to nurture the growth of more highly skilled professionals.