Solving the River Crossing Puzzle with Go
Programming Snapshot – Go Game States
© Lead Image by am not, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=18656684
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.
[...]
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
-
Hannah Montana Linux Is Back!
Developer Noah Cagle decided the world needed the once obscure but beloved Linux distribution and gave it a decidedly pink refresh.
-
System76 Refreshes the Lemur Laptop
If you're looking for a laptop with tons of power and battery, look no further than the latest iteration of the System76 Lemur Pro.
-
More than 43 Million Lines of Code in Linux Kernel 7.2
Using the cloc utility, Michael Larabel of Phoronix discovered that Linux kernel 7.2 has over 43 million lines of code.
-
Kubuntu Focus Goes Ultra
The Kubuntu Focus team has upped the performance ante of its M2 and Zr laptops with the latest, greatest CPUs from Intel.
-
Linux Gamers May Soon See Less Mouse Lag in KDE Plasma
Gamers using KDE’s Plasma desktop have been suffering from a slight input delay in mouse movement that could lead to getting fragged.
-
Three Lines of Code Improve Linux Storage Performance
A developer changed three lines of code, giving Linux storage performance a 5% bump.
-
AUR Hit Again with Malicious Packages
Once again the Arch User Repository is plagued by a high volume of malicious packages.
-
Alpine Linux 3.24 Features Fresh Desktops and a Newer Kernel
If you're a fan of Alpine Linux, it's time to upgrade because the latest version has been released with KDE Plasma 6.6, Gnome 50, and Linux kernel 6.18 LTS.
-
EU Open Source Strategy Plays Key Role in Tech Sovereignty Package
Comprehensive measures adopted by the European Commission aim to reduce dependency on non-EU countries.
-
Linux Foundation Report Indicates AI Driving Tech Hiring
Within growing security and skills gaps, AI has been found to be a positive driving force behind tech hiring trends in Europe.