360 - PurelyFunctional.tv Newsletter https://purelyfunctional.tv/issues/purelyfunctional-tv-newsletter-360-tip-fold-left-vs-fold-right/

00 wheres waldo.md

Where's Waldo?

You are given a vector of vectors, representing a grid. The grid is filled with values. Your job is to find a given value and return the path into the grid that will get to it.

Here's an example:

(wheres-waldo :W ;; look for :W
 [[:A :B :C]
  [:D :E :F]
  [:G :H :I]
  [:J :K :L]
  [:M :N :O]
  [:P :Q :R]
  [:S :T :U]
  [:V :W :X]
  [:Y :and :Z]]);=> [7 1]

Notice that I can pass [7 1] to get-in to find the value.

Notes

• The nested vectors will all be the same length. This is a rectangular grid.
• If the value occurs more than once, you can return coordinates to any of them.
• Return nil if you can't find the value.

Bonus

Can you make it work with arbitrarily nested vectors of different sizes?

Have fun with this one! Try out different ways to implement it.

Thanks to to this site for the challenge idea!

Chase Lambert.clj

(defn wheres-waldo [grid value]
  (loop [xs grid
         value value]
    (if (empty? xs)
      nil
      (if ((set (first xs)) value)
        [(.indexOf grid (first xs)) (.indexOf (first xs) value)]
        (recur (rest xs) value)))))

Eric Normand.clj

(defn wheres-waldo
  ([w world]
   (wheres-waldo w world 0))
  ([w world i]
   (cond
    (empty? world)
    nil

    (vector? (first world))
    (let [path (wheres-waldo w (first world))]
      (if (nil? path)
        (recur w (rest world) (inc i))
        (vec (cons i path))))

    (= w (first world))
    [i]

    :else
    (recur w (rest world) (inc i)))))

Peter Strömberg.clj

(defn wheres-waldo
  "Find the path to waldo"
  {:test (fn []
           (is (= [7 1]
                  (wheres-waldo :W ;; look for :W
                                [[:A :B :C]
                                 [:D :E :F]
                                 [:G :H :I]
                                 [:J :K :L]
                                 [:M :N :O]
                                 [:P :Q :R]
                                 [:S :T :U]
                                 [:V :W :X]
                                 [:Y :and :Z]])))
           (is (= nil (wheres-waldo :W [[:A :B :C]])))
           (is (= [1 2]
                  (wheres-waldo [:i :am :waldo]
                                [[:a :b "ceee"]
                                 [[:i :am :not :waldo] [:i :am :spartacus] [:i :am :waldo]]
                                 ["d" "e" 6]]))))}
  [waldo grid]
  (->> (map-indexed (fn [i v] [i (.indexOf v waldo)]) grid)
       (filter #(not= -1 (second %)))
       first)
  )

(defn wheres-waldo-bonus
  "Find the path to waldo"
  {:test (fn []
           (is (= [7 1 0]
                  (wheres-waldo-bonus :W
                                      [[:A :B :C]
                                       [:D :E :F]
                                       [:G :H :I]
                                       [:J :K :L]
                                       [:M :N :O]
                                       [:P :Q :R]
                                       [:S :T :U]
                                       [:V [:W] :X]
                                       [:Y :and :Z]])))
           (is (= nil (wheres-waldo-bonus :W
                                          [[:A :B :C]])))
           (is (= [1]
                  (wheres-waldo-bonus :W
                                      [:V :W :X])))
           (is (= [1 2 1]
                  (wheres-waldo-bonus [:i :am :waldo]
                                      [[:a :b "ceee"]
                                       [[:i :am :not :waldo] [:i :am :spartacus] [:hello [:i :am :waldo] [:who :are :you?]]]
                                       ["d" "e" 6]]))))}
  ([waldo vektor]
   (wheres-waldo-bonus waldo vektor []))
  ([waldo vektor path]
   (when (vector? vektor)
     (let [i (.indexOf vektor waldo)]
       (if (> i -1)
         (conj path i)
         (->> (map #(wheres-waldo-bonus waldo %1 (conj path %2)) vektor (range))
              (remove nil?)
              first))))))

Steve Miner.clj

(defn wheres-waldo [w grid2]
  (first (for [i (range (count grid2)) :let [v (nth grid2 i)]
               j (range (count v)) :when (= (nth v j) w)]
           [i j])))

;; faster
(defn wheres-waldo2 [w grid2]
  (reduce-kv (fn [_ i v]
               (reduce-kv (fn [_ j x] (when (= w x) (reduced (reduced [i j])))) nil v))
             nil
             grid2))

My solution will blow the stack for large input structures, right?

The Java interop call to .indexOf is going to be slow without a type hint. I suggest you try to use plain Clojure as much as possible. Here's a Clojure implementation (assuming v is vector):

(defn index-of [v w]
  (reduce-kv (fn [_ i x] (when (= x w) (reduced i))) nil v))

If you find yourself needing to (remove nil? ...), you might want to use something like keep instead. In this case, you need the index so use keep-indexed. Here's a slight variation of your code:

(defn wheres-waldo-bonus1
  "Find the path to waldo"
  ([waldo vektor]
   (wheres-waldo-bonus1 waldo vektor []))
  ([waldo vektor path]
   (when (vector? vektor)
     (if-let [i (index-of vektor waldo)]
       (conj path i)
       (first (keep-indexed #(wheres-waldo-bonus1 waldo %2 (conj path %)) vektor))))))

I like to use reduce-kv with vectors so here's another solution that also happens to be pretty fast.

(defn wheres-waldo4
  ([w nested-vec] (wheres-waldo4 w nested-vec []))
  ([w nested-vec stack]
   (reduce-kv (fn [_ i v]
                (cond (= w v) (reduced (conj stack i))
                      (vector? v) (when-let [r (wheres-waldo4 w v (conj stack i))]
                                    (reduced r))
                      :else nil))
              nil
              nested-vec)))

Oh, wow, thanks!. This is super. I keep forgetting about type hinting. Most of my Clojure and ClojureScript work has been with CLJC and then most things are written in plain Clojure...

Thanks for reminding me about keep. Makes total sense here!

I have to admit that I am still having troubles figuring reduce out. It is obviously a very good tool, but my brain hasn't grokked it yet. Eric's intro to Clojure where he says map, filter and reduce are the keys to functional programming still play in my head, but while the two former are super easy for me to understand, the latter... Not so much. Maybe playing around with your input here can help me.

I should note that my example of using reduce-kv is a bit unusual in that the reduced result short-circuits the process. In this case, reduce-kv is being used to efficiently step through the vector. Normally, a reduce process boils the entire collection down to a single value. The usage of reduced is a slightly more advanced technique. I would say you rarely need it. It just turns out to be a way of using the efficient machinery to get a desired result in this special case.

This is a great discussion! It does make me fear that my solution is hopelessly missing something because it doesn't seem to be anything like what you folks are doing. Is the performance going to be horrible? Is it not doing something that I thought it was?

Performance isn't everything but I like to use Criterium for benchmarking. Criterium
My original suggestion was to avoid Java interop if there is a good Clojure solution. But if you use interop, take a look at the *warn-on-reflection* documentation. The two-dimensional solution by Chase performs better than I would have expected if you type hint the calls to .indexOf -- first arg needs ^clojure.lang.PersistentVector. However, using reduce-kv is still much faster.

;; faster two-dimension grid
(defn wheres-waldo2 [w grid2]
  (reduce-kv (fn [_ i v]
               (reduce-kv (fn [_ j x] (when (= w x) (reduced (reduced [i j])))) nil v))
             nil
             grid2))