Algorithm to Iterate All Possible Strings in Clojure

Question

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.

Answer 1

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.