Skip to content

Instantly share code, notes, and snippets.

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

Phone to letter translation

Phone keypads and rotary dials have little letters on them. Most numbers translate into letters. Of course, with only 10 digits, but 26 letters, there is a problem: the translation from letters to numbers is lossy. When translating from numbers to letters, there is always more than one possible interpretation.

Write a function that takes a string of digits and returns a collection of the possible strings of letters it corresponds to.

Examples

(digits->letters "22") ;=> ["aa" "ab" "ac" "ba" "bb" "bc" "ca" "cb" "cc"]

Here are the mappings you should use:

1: no letters
2: abc
3: def
4: ghi
5: jkl
6: mno
7: pqrs
8: tuv
9: wxyz
0: space

If a character appears in the input that does not have a mapping, it will appear in the output untranslated.

Thanks to this site for the problem idea, where it is rated Expert in JavaScript. The problem has been modified.

Please submit your solutions as comments on this gist.

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

@felipereigosa

This comment has been minimized.

Copy link

@felipereigosa felipereigosa commented Aug 3, 2021

(defn create-combinations [& lists]
  (if (= (count lists) 1)
    (map list (first lists))
    (for [a (first lists)
          b (apply create-combinations (rest lists))]
      (cons a b))))

(defn digits->letters [msg]
  (let [m {\1 "1" \2 "abc" \3 "def"
           \4 "ghi" \5 "jkl" \6 "mno"
           \7 "pqrs" \8 "tuv" \9 "wxyz" \0 " "}]
    (->> msg
         (map (partial get m))
         (apply create-combinations)
         (map (partial apply str))
         (vec))))
@jonasseglare

This comment has been minimized.

Copy link

@jonasseglare jonasseglare commented Aug 3, 2021

(defn digits->letters [src]
  (transduce
   (map #(nth [" " "1" "abc" "def" "ghi" "jkl" "mno" "pqrs" "tuv" "wxyz"] (- (int %) 48) [%]))
   (completing #(for [l %1 r %2] (str l r)))
   [""]
   src))
@jaihindhreddy

This comment has been minimized.

Copy link

@jaihindhreddy jaihindhreddy commented Aug 3, 2021

;; deps.edn coord {org.clojure/math.combinatorics {:mvn/version "0.1.6"}}
(require '[clojure.math.combinatorics :as comb])

(let [mapping {\1 "1"    \2 "abc" \3 "def"
               \4 "ghi"  \5 "jkl" \6 "mno"
               \7 "pqrs" \8 "tuv" \9 "wxyz"
                         \0 " "}]
  (defn digits->letters [msg]
    (->> (map #(or (mapping %) [%]) msg)
         (apply comb/cartesian-product)
         (mapv #(apply str %)))))
@kolstae

This comment has been minimized.

Copy link

@kolstae kolstae commented Aug 3, 2021

(def digit->letters {\2 "abc"
                     \3 "def"
                     \4 "ghi"
                     \5 "jkl"
                     \6 "mno"
                     \7 "pqrs"
                     \8 "tuv"
                     \9 "wxyz"
                     \0 " "})

(defn digits->letters [s]
  (->> s
       (map #(digit->letters % (str %)))
       (reduce #(for [a %1 b %2] (str a b)) [""])))
@SignSpice

This comment has been minimized.

Copy link

@SignSpice SignSpice commented Aug 4, 2021

I'm relatively new to Clojure, so it's quite likely I'm missing something obvious.

I thought I had a solution, until I realized clojure.core/for was a macro. So then I thought I had I bad solution, to make a macro that allows me to have a "variadic for" (not really the best name, just couldn't think of a better one for now). I think I might be close, but maybe it's not actually possible like this. I know you wouldn't actually want to use a macro for this problem as there are other ways of achieving the same result, but I am curious how and if it can be done for the sake of learning.

(def keypad-letters
  {:1 nil    :2 "abc" :3 "def"
   :4 "ghi"  :5 "jkl" :6 "mno"
   :7 "pqrs" :8 "tuv" :9 "wxyz"
             :0 " "})

(defn vector-for-the-for-macro [message]
  (into []
        (mapcat
         #(keypad-letters % [(symbol (str "i" %2)) ((keyword (str %)) keypad-letters)])
         message
         (range))))

(comment

  (for [x (:2 keypad-letters)
        y (:3 keypad-letters)] (str x y))

  (for [x (:2 keypad-letters)
        y (:3 keypad-letters)
        z (:4 keypad-letters)] (str x y z))

  (for [x (:2 keypad-letters)
        y (:2 keypad-letters)
        z (:4 keypad-letters)
        a (:2 keypad-letters)] (str x y z a))

  (for [x (:2 keypad-letters)
        y (:2 keypad-letters)
        z (:4 keypad-letters)
        a (:2 keypad-letters)] (apply str [x y z a]))

  (for [digit "223"]
    (for [x ((keyword (str digit)) keypad-letters)]
      x))

  (map #(keypad-letters % (keyword (str %))) "23")
  (map #(keypad-letters % [(str "i" %2)]) "23" (range))
  (mapcat #(keypad-letters % [(str "i" %2) ((keyword (str %)) keypad-letters)]) "23" (range))
  (mapcat #(keypad-letters % [(symbol (str "i" %2)) ((keyword (str %)) keypad-letters)]) "23" (range))
  (into []
        (mapcat
         #(keypad-letters % [(symbol (str "i" %2)) ((keyword (str %)) keypad-letters)])
         "23"
         (range)))

  (vector-for-the-for-macro "262")
  (filter symbol? (vector-for-the-for-macro "262"))

  (defmacro variadic-for
    []
    '(for ~(vector-for-the-for-macro "262")
       (apply str (~(filter symbol? (vector-for-the-for-macro "262"))))))

  (defmacro variadic-for
    [binding-vector]
    '(for ~binding-vector
       (apply str ((filter symbol? ~binding-vector)))))

  (variadic-for (vector-for-the-for-macro "2"))
  (macroexpand-1 '(variadic-for (vector-for-the-for-macro "2")))

  ,)



#_(digits->letters "222")
@mchampine

This comment has been minimized.

Copy link

@mchampine mchampine commented Aug 4, 2021

(defn combo [n items]
  (cond
    (= n 0) '(())
    (empty? items) '()
    :else (concat (map #(cons (first items) %)
                       (combo (dec n) (rest items)))
                  (combo n (rest items)))))

(defn digits->letters [ds]
  (let [ds' (s/replace ds "1" "")
        dial {\1 nil \2 "abc" \3 "def" \4 "ghi" \5 "jkl"
              \6 "mno" \7 "pqrs" \8 "tuv" \9 "wxyz" \0 " "}
        pstr (apply str (map (fn [v] (get dial v v)) ds'))]
    (vec (distinct (map #(apply str %) (combo (count ds') pstr))))))
@ZaymonFC

This comment has been minimized.

Copy link

@ZaymonFC ZaymonFC commented Aug 5, 2021

;; combo is clojure.math.combinatorics
(def phone-letter-mapping
  {\2 [\a \b \c] \3 [\d \e \f]
   \4 [\g \h \i] \5 [\j \k \l]
   \6 [\m \n \o] \7 [\p \q \r \s]
   \8 [\t \u \v] \9 [\w \x \y \z]
   \0 [\ ]})

(defn number-to-list [xs]
  (->> xs
       (map (fn [x] (get phone-letter-mapping x [x])))
       (apply combo/cartesian-product)
       (map (partial apply str))))
@mcuervoe

This comment has been minimized.

Copy link

@mcuervoe mcuervoe commented Aug 5, 2021

(defn digits->letters [digits-str]
  (let [mapping {\1 [\1], \2 [\a \b \c], \3 [\d \e \f], \4 [\g \h \i], \5 [\j \k \l], \6 [\m \n \o], \7 [\p \q \r \s],
                 \8 [\t \u \v], \9 [\w \x \y \z], \0 [\space]}]
    (->>
      (loop [digits digits-str
             results [nil]]
        (if (= 0 (count digits))
          results
          (let [chars (get mapping (first digits))]
            (recur
              (next digits)
              (for [c chars, result results]
                ((fnil conj []) result c))))))
      (map (fn [chars] (apply str chars))))))
@KubqoA

This comment has been minimized.

Copy link

@KubqoA KubqoA commented Aug 5, 2021

(require '[clojure.math.combinatorics :as combo])

(def digit->letters {\2 "abc"
                     \3 "def"
                     \4 "ghi"
                     \5 "jkl"
                     \6 "mno"
                     \7 "pqrs"
                     \8 "tuv"
                     \9 "wxyz"
                     \0 " "})

(defn digits->letters [digits] (->> digits
                                    (map digit->letters)
                                    (filter seq)
                                    (apply combo/cartesian-product)
                                    (mapv #(apply str %))))
@igajsin

This comment has been minimized.

Copy link

@igajsin igajsin commented Aug 7, 2021

There are 3 steps here:

  1. deconstruct a digit string into a list of letters.
  2. do a permutation on lists.
  3. construct strings from lists.
(def dict {
           :1 [""]
           :2 ["a" "b" "c"]
           :3 ["d" "e" "f"]
           :4 ["g" "h" "i"]
           :5 ["j" "k" "l"]
           :6 ["m" "n" "o"]
           :7 ["p" "q" "r" "s"]
           :8 ["t" "u" "v"]
           :9 ["w" "x" "y" "z"]
           :0 [" "]
           })

(defn letter->list [letter]
  ((keyword letter) dict))

(defn string->list [s]
  (str/split s #""))

(defn get-letters [digits]
  (map letter->list (string->list digits)))

(defn add1 [letter letters]
  (map #(list letter %)  letters))

(defn permutate2 [l1 l2]
  (mapcat #(add1 % l2) l1))

(defn msg [s l]
  (print (str s ": ")) (clojure.pprint/pprint l))

(defn permutate [letters]
  (cond
    (< (count letters) 2) letters
    (= (count letters) 2) (permutate2 (first letters) (second letters))
    :else (permutate2 (first letters) (permutate (rest letters)))))

(defn list->string [permutted]
  (map clojure.string/join
       (map flatten permutted)))

(defn digits->letters [digits]
  (list->string (permutate (get-letters digits))))
@KingCode

This comment has been minimized.

Copy link

@KingCode KingCode commented Oct 6, 2021

(def dial {\1 "1", \2 "abc", \3 "def", \4 "ghi", \5 "jkl", \6 "mno", 
           \7 "pqrs", \8 "tuv", \9 "wxyz", \0 " "})

(defn digits->letters [digits]
  (map 
   (partial apply str)
   (loop [digs (-> digits reverse rest),
          acc  (->> digits last dial
                    (map list))]
     (if (empty? digs)
       acc
       (recur (rest digs) 
              (->> (dial (first digs))
                   (mapcat (fn [ltr]
                             (->> acc
                                  (map #(conj % ltr)))))))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment