Wolf, sheep, cabbage
There's a really common problem called "Wolf, sheep, cabbage". (There are other names for it as well). The problem goes like this:
You own a wolf, a sheep, and a cabbage. You need to cross a river and you only have a boat big enough for you plus one other passenger (your wolf, sheep, or cabbage). The trouble is, the animals are hungry. If you leave the wolf with the sheep, the wolf will eat it. If you leave the sheep with the cabbage, it will eat it. The wolf, being a carnivore, will not eat the cabbage. How do you move them safely to the other side with nothing being eaten?
It's a fun problem and I suggest you give it a try on paper if you don't know the solution. If you can't figure it out, search for it online and you'll find solutions.
Your task is to write a function that generates solutions to this puzzle, in the form of boat crossings. Each crossing should state:
- the direction you are going
- the passenger in your boat
(defn wolf-sheep-cabbage []) => ([...
{:direction :across
:passenger :cabbage}
{:direction :return
:passenger :sheep}]
...)
Bonus
Write a function that validates a solution.
Please submit your solutions as comments to this gist. Discussion is welcome.
The solver functions retain a route of visited states to avoid cycles. I found it more convenient to build up the solution as a route and convert to the required move format.