Bridge-crossing with Clojure

Solving puzzles has become popular among colleagues at the end of this year. One of these was the popular Bridge and torch problem. To summarize: four men have to cross a bridge in the dark with a torch, which can only light the way for two persons. These guys can cross the bridge in 1, 2, 5 and 10 minutes, respectively. When two people cross the bridge, it takes the time needed for the slower one to pass.

I'm not going to explain the optimal solution, but I wanted to show how this is a graph-traversal problem, which is amenable to solving using Dijkstra's algorithm. I also noticed that some clever guy has solved the puzzle using Prolog. So an idea was formed: generate the tree of solutions using a language, which I'm not really comfortable with (so I can practice and learn it better). I settled on Clojure, because I wanted to learn it this year (and the year is almost over).

The solution has a lot to do with sets. The state of each of the banks (which I'll call left and right) is a set of people, which are identified by their crossing speed. If we generate the list of possible combinations between the persons for each next move and recurse into them, then we'll have the tree of all solutions. In order to avoid indefinitely long (and stupid) solutions, we assume that going forward always takes two men, and going back takes only one.

The necessary libraries are set, combinatorics and str-utils. That's where I start:

(use '[clojure.contrib.combinatorics])
(use '[clojure.set])
(use '[clojure.contrib.str-utils])
(use '[clojure.contrib.pprint])

Here are the initial data structures: the two river banks are sets, the right one is empty:

(def left #{1, 2, 5, 10})
(def right #{})

And here's a first version of the solution:

(defn forward [left right steps minutes]
        (map #(back
                (difference left %)
                (union right (set %))
                (cons % steps)
                (+ minutes (reduce max %)) )
            (combinations left 2)) )

(defn back [left right steps minutes]
    (if (empty? left)
        (list steps minutes)
        (map #(forward
                (union left (set %))
                (difference right %)
                (cons % steps)
                (+ minutes (reduce max %)) )
            (combinations right 1)) ) )

(pprint (forward left right nil 0))

This prints some semblance of a tree, constructed by nested lists (hey, that's what Lisp is good for, remember?). What I didn't like about this is that there is too much repetition. There are many parts of these functions, which look the same. In order to evolve the solution, I wanted to extract the common parts in a single function:

(defn solve [from to steps minutes group]
    (if (and (empty? to) (not group))
        (list steps minutes)
        (mapcat #(solve
                (union to (set %))
                (difference from %)
                (cons % steps)
                (+ minutes (reduce max %))
                (not group) )
            (combinations from (if group 2 1))) ) )

(pprint (solve left right nil 0 true))

The function behaves differently depending on whether the group of people crossing consists of two or just one person. Also, the tree is now flattened, so the optimal solution can be easily found like this:

(print (reduce #(if (< (second %1) (second %2)) %1 %2) (apply hash-map (solve left right nil 0 true))))

Next step, I want to be able to collect a lot more data about each state, so I need to stop messing around with lists of lists and use something more organized like a hashmap. There's a reason Clojure includes the function second, but not third or, heaven forbid, fourth. Naming each part of your ad-hoc data structure plays a major role in readability.

(defn solve [from to steps minutes group]
    (if (and (empty? to) (not group))
        {:steps steps, :from from, :time minutes}
        {:steps steps, :from from, :time minutes,
            :solutions (map #(solve
                    (union to (set %))
                    (difference from %)
                    (cons % steps)
                    (+ minutes (reduce max %))
                    (not group) )
                (combinations from (if group 2 1)))} ) )

So now the interesting part can begin- rendering the tree in a nice graphical form using GraphViz. Watch this:

(defn printgraph [solution_tree]
    (let [steps (solution_tree :steps)
        nodename (if (nil? steps) "root" steps)
        from (solution_tree :from)
        label (if (= (count from) (count left)) (solution_tree :time) from)]
        (str "\"" nodename "\" [label=\"" label "\"];\n"
            (if (contains? :solutions solution_tree)
                ""
                (str-join ""
                    (map #(str "\"" nodename "\" -> "
                            "\"" (:steps %) "\""
                            " [label=\"" (intersection from (:from %)) "\"];\n"
                            (printgraph %))
                        (solution_tree :solutions)) ) ) ) ) )

And now you can output the recursive stuff wrapped with the header and footer like this:

(println "digraph G {")
(print (printgraph (solve left right nil 0 true)))
(println "}")

This graph shows each node as the state of alternating river banks, and the edges show the people crossing the bridge. The leaves display the number of minutes which it took for this particular combination of crossings.

I also wanted to generate a mind map for FreeMind, but since it doesn't support edge labels, I used the persons crossing for the nodes:

(defn mindmap [solution_tree]
    (str-join "\n"
        (map #(str
                "<node text=\"" (intersection (:from solution_tree) (:from %)) "\">"
                (mindmap %)
                "</node>")
            (solution_tree :solutions)) ) )

Now generating the complete file according to the FreeMind format:

(println "<map><node text=\"root\">\n")
(print (mindmap (solve left right nil 0 true)))
(println "</node></map>\n")

Finally, finding the optimal solution is just a wee bit more involved, because it requires traversing the tree recursively, but that's no problem for us anymore:

(defn optimal [tree]
    (if (contains? tree :solutions)
        (reduce #(if (< (second %1) (second %2)) %1 %2) (map optimal (tree :solutions)))
        (list (tree :steps) (tree :time)) ) )

(print (optimal (solve left right nil 0 true)))

In conclusion, I knew that one can write very compact code in Clojure (and any Lisp, in general), and this was certainly true here. I didn't use the Clojure-specific concurrency primitives or the lazy sequences, so my example would probably look similar in another Lisp. I did try to make it as functional as possible and Clojure does encourage that.

Some of the difficulties I had could be solved by static type checking, but I guess I'm spoiled by Scala. I've ran into small problems like renaming a variable and forgetting to rename (or misspelling) some instance of it in my code. I also tend to mix up which of the arguments to contains? comes first, and which second. This is probably because you can exchange a symbol as a key in a hashmap, and the hashmap without changing the meaning, e.g. (:from solution_tree) and (solution_tree :from). Of course, this is a problem with dynamic typing, not of Clojure in particular (and could probably be interpreted as a problem of using the language inappropriately).

Whatever the small hurdles, the problem was solved. Having fun? Check. Generating nice graphs and mind maps to impress colleagues? Check. Learning a bit of Lispy Clojure in the process? Check. Mission accomplished.