CODEWITHSUNDEEP
pythonclojure
Solaxun
Solaxun

Reputation: 2792

Clojure - idiomatic way to do dynamically nested loops

This code is intended to basically loop through each letter in the supplied string and continue until z, then increment the prior letter and restart at a (e.g. starts at "bde", next would be "bdf", ends at "zzz" - the same way a typical loop would work.)

I could of course do a nested for comprehension since this is only three levels, but if the levels are arbitrarily deep, the way I would traditionally approach that is by using recursion (as demonstrated below), in what basically amounts to a depth first search.

The problem with this approach is that any non-trivial sized input blows the stack (for example, "abcd"), and I can't think of a good way to do it without recursion. A similar approach in Python (with some small differences like accumulating results in a mutable list), implemented below the clojure code doesn't hit the stack limit for input "abcd".

I tried using loop/recur but this construct doesn't seem to work from within a for macro as the call must suspend on the next loop iteration and is therefore not in tail position (at least I believe that is the reason).

What is the most idiomatic way to approach this type of problem?

;;; example using for macro
(defn gen-pw [pw r]
  (cond (empty? pw) r
        :else (flatten (for [x (range (int(first pw)) 123)]
                            (gen-pw (rest pw) (str r (char x)))))))


;;; example using map instead of for macro
(defn gen-pw [pw r]
  (cond (empty? pw) r
        :else (flatten (map #(gen-pw (rest pw) (str r (char %)))
                            (range (int(first pw)) 123))))) 

(gen-pw "bde" "") 

def gen_pw(pw,r='',final=[]):
    if not pw:
        final.append(r)
        return 
    for letter in range(ord(pw[0]),123):
        gen_pw(pw[1:],r + chr(letter))
    return final

print(gen_pw('abcd'))

Upvotes: 2

Views: 792

Answers (4)

amalloy
amalloy

Reputation: 91857

You are generating a list that is tremendously over-nested by evaluating something like this:

(for [...]
  (for [...]
    (for [...]
      ...)))

And then trying to fix the accidental nesting with flatten, which of course has to walk recursively into your gigantic structure, and then explodes. Instead, generate a flat list to begin with. The easiest way to do this is simply to take your map version, replace map with mapcat, and remove the now-unnecessary flatten:

(defn gen-pw [pw r]
  (cond (empty? pw) [r]
        :else (mapcat #(gen-pw (rest pw) (str r (char %)))
                      (range (int(first pw)) 123))))

You'll also have to adjust the base case from r to [r], as I did here: you're generating a list of valid passwords, not just one password, and so the return type should always be a list.

Upvotes: 3

Chris Murphy
Chris Murphy

Reputation: 6509

One way to do this is using iterate:

(defn transition [[text n]]
  (let [c (nth text n)
        nxt (if (= c \z) \z (-> c int inc char))
        nxt-str (str (subs text 0 n) nxt (subs text (inc n) (dec (count text))))]
    (if (= \z nxt)
      [nxt-str (inc n)]
      [nxt-str n])))

(defn ongoing? [[text n]]
  (not (every? #(= \z %) text)))

(->> (iterate transition ["zza" 2])
     (take-while ongoing?)
     (map first))

Note that for ["zza" 2] the \a is in third position (hence 2) and for ["dzs" 0] the \d is in first position (hence 0).

Upvotes: 1

Magos
Magos

Reputation: 3014

I see this problem statement as about computing a cartesian product, so I'm inclined to just recommend the lazy mutual-recursion implementation of that found in clojure.math.combinatorics. Using it becomes something like:

(ns loops
  (:require [clojure.math.combinatorics :refer [cartesian-product]]
            [clojure.string :refer [join]]))

(defn chars-from [start]
  (map char (range (int start) 123)))

(defn gen-pw [pw]
  (map join (apply cartesian-product (map chars-from pw))))

(gen-pw "bde")
;;=> ("bde" "bdf" "bdg" ... "bee" "bef" "beg" ...

Upvotes: 1

Alex
Alex

Reputation: 790

If you're reaching the recursion limit, make your process iterative rather than recursive.

You're right that when the recursive procedure call is part of a larger expression (that is, not in tail position), it will produce a recursive process. Therefore, make sure that the recursive call represents the entire value of the procedure.

(defn gen-pw [pw r]
  (let (s (successor pw))
    (if (nil? s)                ; (successor "zzz") is equal to nil
      r
      (gen-pw s (cons s r)))))  ; (successor "bfe") is equal to "bff"

Upvotes: -1

Related Questions