Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
455 PurelyFunctional.tv Newsletter

Autocomplete

I always liked flexible autocomplete where you can type a few letters, even skipping some letters, and it can find the file or word for you.

Your task is to write a function that determines if you can complete a sequence of characters to a given string.

Examples

(completes? "a" "autocomplete") ;=> true
(completes? "atc" "autocomplete") ;=> true
(completes? "hello" "hello") ;=> true
(completes? "ll" "hello") ;=> true
(completes? "llh" "hello") ;=> false

The rules. The function returns true if all of the following are true (otherwise false):

  1. The first string contains only letters in the second string.
  2. The first string's letters are in the same order as in the second string.

Note that this means that you can match any number of letters between typed letters.

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/

@jonasseglare
Copy link

jonasseglare commented Dec 21, 2021

(defn completes? [x full-word]
  (->> full-word
       (reduce #(if (= (first %1) %2) (subs %1 1) %1) x)
       empty?))

@jkrasnay
Copy link

jkrasnay commented Dec 21, 2021

(defn completes?
  [a b]
  (cond
    
    (empty? a)
    true
    
    (empty? b)
    false
    
    (= (first a) (first b))
    (recur (rest a) (rest b))
    
    :else
    (recur a (rest b))))

@gveres
Copy link

gveres commented Dec 21, 2021

(defn completes?
  [a b]
  (let [b* (apply str (filter (set a) b))]
    (.contains b* a)))

@mchampine
Copy link

mchampine commented Dec 21, 2021

(defn completes? [a b]
  (-> #(if-let [r (clojure.string/index-of %1 %2)]
         (subs %1 r) (reduced false))
      (reduce b a)
      boolean))

@steffan-westcott
Copy link

steffan-westcott commented Dec 22, 2021

(defn completes? [pat s]
  (-> (apply str (mapcat #(list ".*?\\Q" % "\\E") pat))
      re-pattern
      (re-find s)
      some?))

@harto
Copy link

harto commented Dec 22, 2021

(defn completes? [abbrev s]
  (re-find (re-pattern (clojure.string/join ".*" abbrev)) s))

(probably needs some escaping of characters in abbrev to work robustly...)

edit: ah, just realised that's what steffan-westcott's solution does :)

@Toni-zgz
Copy link

Toni-zgz commented Dec 30, 2021

(ns autocomplete)

(require '[clojure.test :as test])

(defn completes? [str1 str2]
    (loop [str1 str1
           str2 str2]
        (cond
            (empty? str1) true
            (empty? str2) false
            (= (first str1) (first str2)) (recur (rest str1) (rest str2))
            :else (recur str1 (rest str2)))))

(test/testing "Pruebas autocomplete"
    (test/is (= (completes? "a" "autocomplete") true))
    (test/is (= (completes? "atc" "autocomplete") true))
    (test/is (= (completes? "hello" "hello") true))
    (test/is (= (completes? "ll" "hello") true))
    (test/is (= (completes? "llh" "hello") false)))

@KingCode
Copy link

KingCode commented Jun 4, 2022

This is long winded, to accept any input where all consecutive pairs comply, including duplicates. @mchampine's solution does the same, but much more compactly - nice work!:)
See the last few examples below.

(defn order [xs]
  (-> (comp 
       (map-indexed vector)
       (map reverse))
      (transduce  (completing (fn [acc [v i]] 
                                (update acc v (fnil conj #{}) i)))
                  {} xs)))

(defn mutual-order [xs]
  (let [o (order xs)]
    (->> (for [a xs b xs
               :when (not= a b)
               :let [ao (o a) bo (o b)
                     <? (< (apply min ao) (apply max bo))]]
           [[a b] <?])
         (reduce (fn [acc [pair <?]]
                   (update acc pair (fnil conj #{}) <?))
                 {}))))

(defn <=? [[a b :as pair] amo bmo]
  (or (= a b)
      (some (get amo pair) (get bmo pair))
      false))

(defn completes? [txt tgt]
  (let [txt-mo (mutual-order txt) 
        tgt-mo (mutual-order tgt)]
    (->> txt (partition 2 1)
         (reduce (fn [ok? pair]
                   (if (not ok?)
                     (reduced false)
                     (<=? pair txt-mo tgt-mo)))
                 true))))

(completes? "a" "autocomplete") ;=> true
(completes? "atc" "autocomplete") ;=> true
(completes? "hello" "hello") ;=> true
(completes? "ll" "hello") ;=> true
(completes? "llh" "hello") ;=> false
(completes? "heeeeeewllld" "hello world!") ;=> true, as duplicates are allowed
(completes? "hollld" "hello world!") ;=> true, using o->l->d of second word 
(completes? "hwllld" "hello world!") ;=> true, since h->w->l->d
(completes? "hwlllds" "hello world!") ;=> false, different chars 
(completes? "hwellld" "hello world!") ;=> false, due to w->e 

@KingCode
Copy link

KingCode commented Jun 4, 2022

Here is another version which generates a regexp from the input:

(defn ->re [s]
  (let [wc ".*"]
    (->> s distinct (interpose wc)  (cons wc) vec (#(conj % wc))
         (apply str) re-pattern)))

(defn completes? [txt tgt]
  (if (re-matches (->re txt) tgt)
    true
    false))



(completes? "a" "autocomplete") ;=> true
(completes? "atc" "autocomplete") ;=> true
(completes? "hello" "hello") ;=> true
(completes? "ll" "hello") ;=> true
(completes? "llh" "hello") ;=> false
(completes? "heeeeeewllld" "hello world!") ;=> true, as duplicates are allowed
(completes? "hollld" "hello world!") ;=> true, using o->l->d of second word 
(completes? "hwllld" "hello world!") ;=> true, since h->w->l->d
(completes? "hwlllds" "hello world!") ;=> false, different chars 
(completes? "hwellld" "hello world!") ;=> false, due to w->e 

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