465 Eric Normand Newsletter

00 Single letter swaps.md

Single letter swaps

Write a function that takes a sequence of strings and a target string. For each string in the sequence, determine if it is equal to the target string after exactly one letter swap. Return the sequence of letter pairs that are swapped, or nil if it doesn't exist.

Example

(letter-swaps ["bacd" "abdc" "abcde" "abcc" "abcd"] "abcd")
  ;=> [#{\a \b} #{\c \d} nil nil nil]

Swapping a and b in "bacd" gives you the target string. Swapping c and d in "abdc" gives you the target string. But there is no way to swap to get an extra e. And trading a d for a c is not possible. Finally, the last string has no swaps, and exactly one is required.

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

Please submit your solutions as comments on this gist.

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

(defn swap-chars [s i j]
  (let [sv (vec s)]
    [(hash-set (sv i) (sv j))
     (apply str (assoc (assoc sv i (sv j)) j (sv i)))]))

(defn swapss [s]
  (let [cs (count s)
        x (range (dec cs))
        y (range 1 cs)
        z (reverse y)]
    (map (partial swap-chars s) (apply concat (map #(repeat %1 %2) z x))
         (apply concat (map #(range %1 %2) y (repeat cs))))))

(defn checkswap [swstr ostr]
  (ffirst (filter #(= swstr (second %)) (swapss ostr))))

(defn letter-swaps [sc s]
  (map (partial checkswap s) sc))

(defn letter-swaps [strs target]
  (let [swapped (fn swapped [fstr sstr]
                  (let [[f s] (clojure.data/diff (seq fstr) (seq sstr))
                        fv (sort (remove nil? f))
                        sv (sort (remove nil? s))]
                    (when
                      (and
                        (= (count fv) (count sv) 2)
                        (= fv sv))
                      (set sv))))]
    (map (partial swapped target) strs)))

Here are a couple of additional examples that I think should be true, but not all the implementations agree.

(= (letter-swaps ["abba" "bcba" "abab" "baba"] "abba") [nil nil #{\a \b} #{\a \b}])
(= (letter-swaps ["aa" "bb" "ba" "ab"] "aa") [nil nil nil nil])

Hmmmm, mine does this with the second one, @miner:

(letter-swaps ["aa" "bb" "ba" "ab"] "aa") ; => [nil #{\a \b} nil nil]

I'll have to fix it, I agree.

EDIT: Now fixed. ✅ Thanks! 🙏

(defn letter-swaps [inputs target]
  (for [i inputs]
    (->> i
         (when (= (count target) (count i)))
         (map vector target)
         (group-by set)
         (remove #(= 1 (count (first %))))
         ((fn [[[x [a b]] & c]] (and a b (not c) x))))))

(defn letter-swap [xs ys]
  (when (= (count xs) (count ys))
    (let [[[a b] & other-swaps] (remove #(apply = %) (map vector xs ys))]
      (when (= [[b a]] other-swaps)
        #{a b}))))

(defn letter-swaps [coll s]
  (mapv letter-swap coll (repeat s)))

This is so elegant, nice one @steffan-westcott !

Using sets and =/not= to weed out most candidates.

(defn single-swap? [kand xs]
  (let [swaps (and (= (set kand) (set xs))
                   (not= kand xs)
                   (->> xs (map vector kand)
                        (sequence (comp
                                   (map (fn [[k x]]
                                          (when (not= k x) k)))
                                   (filter identity)))))]
    (when (and swaps (= 2 (count swaps)))
      (set swaps))))

(defn letter-swaps [kands str]
  (->> kands
       (map #(single-swap? % str))))