Fox, gopher and bag of beans in Go
Since I've been having quite the love affair these days with Google's Go language I've been spending a lot of time in deep thought reflecting on Go's use cases in terms of concurrency. If you are like me, coming to Go after spending years with your mind tuned to "those other" languages you may find yourself struggling sometimes to adapt your mind to Go's way of doing things.
So let us take a break from the typical coding examples that solve real world problems and let's talk about solving a fun puzzle with Go using channels. This exercise is geared towards those new to Go and offers a framework for playing and experimenting with a channels in Go.
There is an old river crossing puzzle called the Fox, goose and bag of beans puzzle. According to wikipedia this puzzle dates back to 9th century and has since then has entered into folklore amongst different ethnic groups. I believe I first encountered the puzzle somewhere in grade school and the idea is simple: A farmer has purchased a set of three items at the local market. He purchased the following: A fox, a gopher and a bag of beans. In our version of this puzzle, we will be replacing the goose with none other than Go's mascot -- a gopher. As it turns out, there are many variations on the puzzle and you may encounter this exercise in logic in job interviews.
The challenge is this: get the farmer and all three market items from one side of the river to other with the following constraints. The farmer must take a boat along with only one item across the river bank. If he leaves the fox alone with the gopher, the fox will eat the gopher. If he leaves the gopher alone with the bag of beans, the gopher will eat the beans. Therefore, the farmer must get all items across the river from one bank to other in a series of steps that preserves his market items.
Let's dive into one way perhaps we can model this puzzle in Go but please consider to the following disclaimer: In the spirit of keeping things fairly simple, we're going to only use one goroutine (the main goroutine) and additionally, I'm not going to bother with going over board with abstractions and other features of the language. I'd like to keep this article focused. Also, this exercise is in modeling a puzzle and attempting to solve it logically in code. This is not an attempt to have the computer solve the puzzle using some algorithm but I'm sure you could take it there if you want.
To start off let's define the types that we'll need:
//The good 'ol farmer
type Farmer struct {
}
//The gopher (goose) that the farmer purchased at the market
type Gopher struct {
}
func (g *Gopher) Eat(b *BagOfBeans, f *Farmer) {
if b != nil && f == nil {
log.Fatal("OOPS: Gopher just ate all the beans")
}
}
//The bag of beans that the farmer purchased at the market
type BagOfBeans struct {
}
//The fox that the farmer purchased at the market
type Fox struct {
}
func (fox *Fox) Eat(g *Gopher, f *Farmer) {
if g != nil && f == nil {
log.Fatal("OOPS: Fox ate gopher just now.")
}
}
//The boat which at any given time will only hold the farmer and ONE other item
type Boat struct {
farmer *Farmer
gopher *Gopher
fox *Fox
beans *BagOfBeans
}
//Defines a const of East or West
type Side int
const (
East = 0
West = 1
)
//The bank will represent the lands on either side of the river
type Bank struct {
farmer *Farmer
fox *Fox
gopher *Gopher
beans *BagOfBeans
side Side
}
//The river that the farmer must cross with all his belongings
var river = make(chan Boat, 1)As you can see, the types representing each of our objects are pretty straightforward. Most of them are simply empty where we aren't interested in holding any state. A few things to point out: The river is a channel type that can hold a boat with a buffer of one. This is the perfect opportunity to realize that a channel acts very much like a river or a stream, carrying data over it. It offers a means of communication that can be safely used across goroutines. Again, in our example, we only need to use one goroutine to accomplish our goal here today.
Also, notice that both the Gopher and the Fox have Eat receiver functions associated with them. When either of these methods are executed, if the farmer is not present (nil) and the appropriate edible item is still present the application will do a log.Fatal() to signal to the user that either the Fox ate the Gopher or the Gopher ate the beans.
One more thing: I went down the path of having the boat type only hold the farmer and one other item but then it made the code more complicated and I felt it was easier to demonstrate this puzzle if we treat the Boat as being a container that can only ever hold the farmer and a slot for one other item. We can put whatever object into an available slot, but by convention the boat cannot hold more than 2 items with the farmer included.
Moving on let's create our instances in our main function:
func main() {
//The west bank starts off empty
westBank := Bank{side: West}
//The east bank starts off with the farmer and his store bought items
eastBank := Bank{side: East}
//We create an instance of the farmer, fox, bag of beans, and lastly the gopher
eastBank.farmer = &Farmer{}
eastBank.fox = &Fox{}
eastBank.beans = &BagOfBeans{}
eastBank.gopher = &Gopher{}
//...code continues
}We start off with two banks on either sides of our river. In our version of the puzzle, the farmer with his gopher, fox and bag of beans will start off on the East bank. This is basically our setup of the puzzle with the code above representing our initial state. What will happen is, for each stage we will load the boat up with at least the farmer and possibly one other item. In our puzzle, we're going to consider that for any given object (farmer, gopher, fox, or beans) only one reference can be had at a time. In other words, if we have a pointer to the farmer on the west bank, and the farmer gets on the boat and leaves the west bank, the west bank should no longer have a reference to the pointer so the west bank's reference to the farmer will be nil. This will be the case for all the major items for our puzzle to work. This is the idea of passing ownership around in our puzzle with an object's address being the reference in question.
We're going to need a few more methods:
func (b *Bank) checkState() {
counter := 0
if b.fox != nil {
counter++
b.fox.Eat(b.gopher, b.farmer)
}
if b.gopher != nil {
counter++
b.gopher.Eat(b.beans, b.farmer)
}
if b.beans != nil {
counter++
}
if b.farmer != nil {
counter++
}
sd := "West"
if b.side == East {
sd = "East"
}
fmt.Printf("%s bank: %+v\n", sd, b)
//should the counter be 4, this means all 4 made it!
if counter == 4 && b.side == West{
fmt.Println("!!YOU WIN!!")
}
}
func (b *Bank) Send(boat Boat) {
b.farmer = nil
if boat.gopher != nil {
b.gopher = nil
}
if boat.beans != nil {
b.beans = nil
}
if boat.fox != nil {
b.fox = nil
}
b.checkState()
river <- boat
}
func (b *Bank) Receive() {
boat := <-river
b.farmer = boat.farmer
if boat.gopher != nil {
b.gopher = boat.gopher
}
if boat.beans != nil {
b.beans = boat.beans
}
if boat.fox != nil {
b.fox = boat.fox
}
b.checkState()
}In our puzzle what will happen is we're going to have varying stages where the boat will be traveling back and fourth between the West/East bank. Every time, the boat is sent or received we need to check the state of things. Remember with our puzzle, that if we leave the fox alone with the gopher the fox will eat the gopher. If we leave the gopher alone with the beans, that means no more beans for our farmer. Upon either of these events happening we consider this the end of the game and we do a log.Fatal().
In addition to the checkState() function we also have the Send and Receive functions that we call upon a given bank. These functions take care of handling the ownership details about which pointers should be nil and which pointers should have a proper reference to an object whenever ownership does change. Also, these functions make sure to call checkState to validate the state of things.
Running the code
Upon running the code, you will find that it will output the state of the banks upon each Send/Receive command. You will basically see how each bank retains and then later loses its references to those objects which are currently traveling via boat. Here is a segment of some sample output on how this looks:
//Not Go code, just output from the program
//Send
East bank: &{farmer:<nil> fox:0x176a68 gopher:<nil> beans:0x176a68 side:0}
//Receive
West bank: &{farmer:0x176a68 fox:<nil> gopher:0x176a68 beans:<nil> side:1}
//Send
West bank: &{farmer:<nil> fox:<nil> gopher:0x176a68 beans:<nil> side:1}
//Recieve
East bank: &{farmer:0x176a68 fox:0x176a68 gopher:<nil> beans:0x176a68 side:0}
//Send
East bank: &{farmer:<nil> fox:<nil> gopher:<nil> beans:0x176a68 side:0}
//...
//...
//...Interpreting the code above is a little odd at first. On the first Send, we see that the East bank loses it's reference to the farmer and the gopher. Why? Because they are en route to the West. Then, the West bank receives the boat, and as you can see the it now has a reference to the farmer and the gopher. This is repeated until all the farmer and all the items have moved from the East bank to the West entirely.
Solving the puzzle:
With everything now setup solving the puzzle is just a matter of taking a number of steps to run through the puzzle. Here is a few lines of code example:
//Stage 1: send the farmer and the fox
eastBank.Send(Boat{farmer: eastBank.farmer, fox: eastBank.fox})
westBank.Receive()
//Stage 2: send the farmer back by himself
westBank.Send(Boat{farmer: westBank.farmer})
eastBank.Receive()I can already tell you, the above code will fail immediately. If you run the code above it won't even clear the first stage because you are sending along the farmer and the fox. This means the gopher will get to munch on some beans and the game will end.
I will leave solving this puzzle as an exercise to the reader. There are actually a few ways to win, and should you solve the puzzle with the correct sequence the game will automatically detect this in the checkState() method and Println("!!YOU WIN!!") to the screen.
Also, here is a link to the full source code in all its glory with the solution.
