455 PurelyFunctional.tv Newsletter

00 Autocomplete.md

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/

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

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 

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