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))

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))