5
\$\begingroup\$

I'm fairly new to Clojure and I struggled a bit coming up with a nice Clojure-y solution for implementing an algorithm for one of my applications. The real issue I'm trying to solve would require a large writeup in order to understand what it's about, so I've come up with a contrived problem statement that's much easier to understand which is quite similar to my original problem.

Assume you have mapped numbers to letters like so: 1->a, 2->b, 3->c, ... , 26->z

If you receive input like "4 1 25", you can easily convert this to the string "day" (because 'd' is the 4th letter in the alphabet, 'a' is the 1st, and 'y' is the 25th).

Now assume you don't have spaces as delimiters. So the input is "4125". This introduces ambiguity. "4125" can be interpreted as "4 1 25", "4 12 5", and "4 1 2 5".

Write a function that takes a number, and returns all possible strings from these letter codes.

So if you receive "4125" (the example above), the function would return: dle, day, dabe

Here is what I came up with:

; Generates map {1->a, 2->b, ... , 26->z}
(def code->letter
  (into {}
        (for [x (range 26)]
          [(str (inc x))
           (str (char (+ x (int \a))))])))

(defn possible-strings
  ([number]
   (possible-strings (str number) 0 ""))
  ([number index acc]
   (if (>= index (count number))
     acc
     (flatten (for [[k v] code->letter
                    :when (.startsWith number k index)]
                (possible-strings number (+ index (count k)) (str acc v)))))))

; Print all the possible strings from the input "4125"
(doseq [s (possible-strings 4125)]
  (println s))

So I believe this is basically a backtracking algorithm. And because it's a backtracking algorithm, it's impossible to make this tail-recursive, correct? Or maybe I'm wrong that this is a backtracking algorithm. If so, what would this kind of solution be classified as?

Anyway, the algorithm seems to work, but I'm not sure this solution is very idiomatic. The part in particular that I really don't like is having to call flatten for each call. I can't imagine that being very efficient either for large inputs. It seems like there must be a better way to do handle that.

Like I said, I'm new to Clojure and functional programming in general, so if there are improvements elsewhere, I'd be happy to hear about them as well. A completely different approach to solving the problem is welcome as well.

\$\endgroup\$
2
\$\begingroup\$

I figured out a faster, more functional programming-oriented algorithm for this problem -- see below. Besides that, your code overall looks idiomatic and was easy for me to understand, so I have no real criticisms in that area.

zipmap

zipmap is ideal for concisely constructing maps like your code->letter map:

(def code->letter
  (zipmap (map str (iterate inc 1)) (map char (range 97 123))))

;=> {"1" \a, "2" \b, "3" \c, ... "26" \z}

One way to avoid using flatten

Personally, I think using flatten is fine, but some view it as being somewhat hacky, and I've heard it said that if you find yourself using flatten, there is usually a better way to do what you're trying to do. In this case, I would use mapcat -- it's like map, but it handily concatenates the results together into a single collection.

EDIT: This doesn't work! Please disregard :)

...
(mapcat (fn [[k v]]
          (when (.startsWith number k index)
            (possible-strings number (+ index (count k)) (str acc v))))
        code->letter))))

or,

...
(mapcat (fn [[k v]] (possible-strings number (+ index (count k)) (str acc v)))
        (filter #(.startsWith number (key %) index) code->letter)))))

Functional programming

You're correct in that your algorithm is not (and cannot be) tail-recursive. This is because you're wrapping the recursive call to possible-strings within a filtering and mapping operation. I'm not familiar with the term "backtracking algorithm," but it does seem appropriate in this case. This initially struck me as the kind of thing you would do with a reduce, building up a string from scratch, however, you do have to keep "backtracking" to build up new strings using different groupings of digits. I might be wrong about this, but I don't think this is something you can do with tail-recursion, which means you can't use recur and there would be performance implications, especially for large inputs.

Here's another approach: write a function that takes a number and returns a list of possible arrangements of numbers from 1-26. Then just map the numbers to letters and you'll have your possible strings.

This function, which I'll call possible-arrangements, is a little complicated to write. My approach is to walk through the number string from the beginning and form a tree, looking at numbers 2 at a time and branching off for each possibility, each branch terminating once it reaches a list of numbers that can't be broken down any further. For example:

; *starred numbers are ones that are evaluated to see if they can be broken
; down further

                  *4125    ; 41 is not in range, so only one possibility...
                    |
                  4 *125   ; 12 can be 1 2 or 12, so we branch, etc.
                    /  \
                 1 *25  12 5 
                   /\     |
                  /  \    |
      (4 1 ...) 2 5  25  12 5   = 4 1 2 5, 4 1 25, 4 1 12 5

; the result would be [["4" "1" "2" "5"] ["4" "1" "25"] ["4" "12" "5"]]

.

(defn possible-arrangements [^String n]
  (case (count n)
    1 [[n]]
    2 (let [each-digit (mapv str n)]
        (if (contains? code->letter n)
          [[n] each-digit]
          [each-digit]))
    (let [a       (str (first n))
          ab      (subs n 0 2)
          prepend (fn [x offset] 
                    (map (partial cons x) (possible-arrangements (subs n offset))))]
      (if-not (contains? code->letter ab)
        (prepend a 1)
        (concat (prepend a 1) (prepend ab 2))))))

(defn possible-strings [^String n]
  (for [nums (possible-arrangements n)
        :let [chars (map code->letter nums)]]
    (apply str chars)))

This is still not a tail-recursive solution, but it's about 4 times faster, I think because it isn't having to perform 26 string operations for each digit of the input number.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I might be misunderstanding mapcat, but I'm unable to drop your mapcat examples into my original function and make it work. What ends up happening is that I'm getting a sequence of characters (like d l e d a y d a b e) instead of a sequence of strings (like dle day dabe). I tried various things like (apply str), but to no success. \$\endgroup\$ – reibitto Jul 27 '14 at 11:34
  • \$\begingroup\$ Also, I didn't know about zipmap. Thanks for that. Should be helpful as I tend to use (abuse?) list comprehensions everywhere in my code. Your alternate approach is interesting. It's also a nice optimization for the problem at hand. I might not be able to apply it to the real problem I'm trying to solve because the map will have keys of arbitrary length (not just 1 and 2), but for the problem I presented in this post, this is working well. \$\endgroup\$ – reibitto Jul 27 '14 at 11:35
  • \$\begingroup\$ Whoops! I should have tested that mapcat example. Turns out it doesn't work for this particular example because you're dealing with strings, and (concat "dle" "day" "dabe") gives you (\d \l \e \d \a \y \d \a \b \e) because Clojure treats strings as sequences of characters. I'm sure there is some way around this, but I'm blanking at the moment. I don't think there's anything particularly wrong with your use of flatten, for what it's worth. \$\endgroup\$ – Dave Yarwood Jul 28 '14 at 13:57
  • \$\begingroup\$ Now I'm curious about your actual problem, and whether my approach could solve it with some modifications... it would be good practice for me. Would you mind emailing me? My email address is my name @gmail.com \$\endgroup\$ – Dave Yarwood Jul 28 '14 at 14:00
  • \$\begingroup\$ Alright. Sent :) \$\endgroup\$ – reibitto Jul 28 '14 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.