Skip to content

Instantly share code, notes, and snippets.

@ericnormand
Created March 2, 2022 22:22
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ericnormand/6eda605a72b169d62bde12a740eb5bb9 to your computer and use it in GitHub Desktop.
Save ericnormand/6eda605a72b169d62bde12a740eb5bb9 to your computer and use it in GitHub Desktop.
463 PurelyFunctional.tv Newsletter

Word search

I'm fond of search that is forgiving of small mistakes. If you type a few letters from the word, even if you miss a letter, you should get the word.

Here's a simple, forgiving search function.

Write a function that takes two strings, a needle and a haystack. The function should return true if the needle is found in the haystack, with a few forgiving features:

  • If the needle is fully contained in the haystack, it should return true.
  • If the needle would be fully contained in the haystack, but for one or more missing letters, it should return true.
  • Don't match the needle across whitespace or other non alphanumeric characters.
  • Otherwise, return false.

Examples

;;      needle   haystack
(found? "abc" "dddabcfff") ;=> true (direct match)
(found? "abc" "xyzannbffooc") ;=> true (add missing "nn" and "ffoo")
(found? "abc" "a bc") ;=> false (don't match across whitespace)
(found? "xxx" "cxccx") ;=> false (not enough x's)
(found? "" "") ;=> true (trivially so)
(found? "" "aaa") ;=> true (also trivial)

Thanks to this site for the problem idea, where it is rated Very Hard in Java. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

@steffan-westcott
Copy link

(defn found? [needle haystack]
  (-> (clojure.string/join "\\p{Alnum}*" needle)
      re-pattern
      (re-find haystack)
      boolean))

@mchampine
Copy link

mchampine commented Mar 2, 2022

(defn found? [needle haystack]
  (let [pat (re-pattern (apply str (interpose ".*" needle)))
        mtch (re-find pat haystack)]
    (not (or (nil? mtch) (nil? (re-find #"^[a-zA-Z0-9]*$" mtch))))))

@filippocostalli
Copy link

filippocostalli commented Mar 3, 2022

(defn found? [needle haystack]
    (as-> needle v
         (interpose "[a-zA-Z0-9]*" v)   
         (apply str v)
         (re-pattern v)
         (re-find v haystack)
         (not (nil? v))))

@fredokun
Copy link

fredokun commented Mar 4, 2022

;; A (kind of boring) loop-over-seq solution
(defn found? [needle haystack]
  (loop [s (seq haystack), p (seq needle)]
    (if (seq p)
      (if (seq s)
        (cond
          (= (first p) (first s))
          (recur (rest s) (rest p))
          (clojure.string/blank? (str (first s)))
          (recur (rest s) (seq needle))
          :else
          (recur (rest s) p))
        ;; no more input
        false)
      ;; empty pattern
      true)))

;; some more examples
(found? "abc" "a bc abxc") ;; => true  (restart pattern)
(found? "a bc" "xxa byc") ;; => true (somewhat beyond the spec)
(found? [:a :b :c] [:d :d :d :a :b :c :f :f :f]) ;; => true (works on sequences...)

@dfuenzalida
Copy link

(defn found? [needle haystack]
  (let [pat (->> (interpose "\\w*" needle)
                 (reduce str)
                 (format "\\w*%s\\w*")
                 re-pattern)]
    (boolean (re-matches pat haystack))))

(comment
  (found? "abc" "dddabcfff") ;; => true
  (found? "abc" "xyzannbffooc") ;; => true
  (found? "abc" "a bc") ;; => false
  (found? "xxx" "cxccx") ;; => false
  (found? "" "") ;; => true
  (found? "" "aaa") ;; => true
  )

@JonathanHarford
Copy link

JonathanHarford commented Mar 18, 2022

(require '[clojure.test :refer [is]])

(defn found? [needle haystack]
  (->> haystack (re-find (re-pattern (apply str (interpose "\\w*" needle)))) boolean))

(is (= true (found? "abc" "dddabcfff"))) ;  (direct match)
(is (= true (found? "abc" "xyzannbffooc"))) ;  (add missing "nn" and "ffoo")
(is (= false (found? "abc" "a bc"))) ;  (don't match across whitespace)
(is (= false (found? "xxx" "cxccx"))) ;  (not enough x's)
(is (= true (found? "" ""))) ; (trivially so)
(is (= true (found? "" "aaa"))) ; (also trivial)
(is (= true (found? "abc" "aaa bbb ccc ab c xaxxbxxxcx")))

@KingCode
Copy link

(defn found? [needle haystack]
  (let [nvec (vec needle)
        nset (set needle)]
    (->> haystack
         (reduce (fn [acc x]
                   (cond 
                     (= nvec acc)
                     (reduced acc)
                     (#{\space \tab \newline} x)
                     []
                     (nset x)
                     (conj acc x)
                     :else
                     acc))
                 [])
         (= nvec))))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment