397 - PurelyFunctional.tv Newsletter

00 Wolf Sheep Cabbage.md

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.

Since part one doesn't specify correct solutions, here's a way of generating random 'solutions' with clojure.spec:

(ns challenges.wolf
  (:require [clojure.spec.alpha :as s]
            [clojure.spec.gen.alpha :as gen]))

(s/def ::passenger #{:wolf :sheep :cabbage})
(s/def ::direction #{:across :return})
(s/def ::round (s/keys :req-un [::direction ::passenger]))
(s/def ::solut (s/* ::round))

(defn wolf-sheep-cabbage []
  (into [] (gen/generate (s/gen ::solut))))

;; example run
(wolf-sheep-cabbage)
;; [{:direction :across, :passenger :wolf}
;;  {:direction :return, :passenger :wolf}
;;  {:direction :across, :passenger :sheep}
;;  {:direction :return, :passenger :cabbage}
;;  {:direction :across, :passenger :wolf}
;;  {:direction :return, :passenger :sheep}
;;  {:direction :across, :passenger :sheep}
;;  {:direction :across, :passenger :cabbage}
;;  {:direction :across, :passentger :wolf}
;;  {:direction :across, :passenger :sheep}]

Given enough time, this would stumble on a correct solution. :)
Yes, I know, this is not what was intended, but it was a good excuse to practice with clojure.spec and test.check. It would also be useful for generating test cases for a solution validator!