4clojure - Number maze problem

by @ardumont on 28 Jan 2013

Here is the problem statement:

Given a pair of numbers, the start and end point, find a path between the two using only three possible operations:

double

halve (odd numbers cannot be halved)

add 2

Find the shortest path through the "maze". Because there are multiple shortest paths, you must return the length of the shortest path, not the path itself.

For this, I did three functions to separate concerns:

make-children function: deals with the operations (/, +, *) for each value, we can have 3 values for even number or 2 values for odd ones.
lazy breadth-first tree: the construction of each possible values for each step (we use the make-children function)
the lazy searching function: drop the returned values from the breadth-first tree as long as we do not find at least one possible value.

make-children

This function has only for goal to:

compute the result of the operations on a given value (if the value is odd, we do not consider the / operation)
compute the new distance (+ 1)

(defn mkc
  [[s d]]
  (let [[_ & r :as vf] [/ * + ]]
    (map (fn [f] [(f s 2) (+ 1 d)]) (if (even? s) vf r))))

Some unit tests representing the use cases (even and odd value):

(fact
  (mkc [10 1]) => [[5 2] [20 2] [12 2]]
  (mkc [9 1])  => [[18 2]
                   [11 2]])

breadth-first

For each node in the queue, we compute the children via the make-children function and enqueue them. We begin the algorithm by adding the initial input into the queue (the current value and an initial distance of 1)

(defn bfs
  "breadth-first search lazily"
  ([s]
      ((fn nx [q]
         (lazy-seq
          (when (seq q)
            (let [n (peek q)
                  c (mkc n)]
              (cons n (nx (into (pop q) c)))))))
       (conj clojure.lang.PersistentQueue/EMPTY [s 1]))))

(fact
  (take 1 (bfs 1)) => '([1 1])
  (take 4 (bfs 2)) => '([2 1] [1 2] [4 2] [4 2]))

main function

This is the main algorithm.

For the simple case where s(tart) and e(nd) are equals, we return directly 1.

Else, as long as we do not find an entry for which the starting and the ending match, we drop them.

As soon as we find one input that matches the predicate, we retrieve the distance and return it. Indeed, as we search in breadth, we hit the minimal distance.

(defn maze
  [s e]
  (if (= s e) 1 (let [[[_ d]] (drop-while (fn [[s _]] (not= s e)) (bfs s))] d)))

(fact
  (maze 1 1)  =>  1
  (maze 3 12) =>  3
  (maze 12 3) =>  3
  (maze 5 9)  =>  3
  (maze 9 2)  =>  9
  (maze 9 12) =>  5)

source: 106

note As this algorithm is lazy and as we drop the head (using drop-while), we could compute forever without smashing the stack :D.