Puzzle solving in Clojure

[Olivier Scalbert]

Hello everybody !

I just start learning Clojure and I am a complete newbie !

I have tried to solve this classical small puzzle with Clojure.
Assign one digit from {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} to each letter {o n e t h r l v w y} so that
one + one + one + three + three + eleven = twenty

Here is the code:

(defn permutations [s]
  (lazy-seq
   (if (seq (rest s))
     (apply concat (for [x s]
                     (map #(cons x %) (permutations (remove #{x} s)))))
     [s])))

(defn tomap [proposal]
    (zipmap [:o :n :e :t :h :r :l :v :w :y] proposal))

(defn one-value [m]
    (+ (* 100 (:o m))
       (*  10 (:n m))
              (:e m)))

(defn three-value [m]
    (+ (* 10000 (:t m))
       (*  1000 (:h m))
       (*   100 (:r m))
       (*    10 (:e m))
                (:e m)))

(defn eleven-value [m]
    (+ (* 100000 (:e m))
       (*  10000 (:l m))
       (*   1000 (:e m))
       (*    100 (:v m))
       (*     10 (:e m))
                 (:n m)))

(defn twenty-value [m]
    (+ (* 100000 (:t m))
       (*  10000 (:w m))
       (*   1000 (:e m))
       (*    100 (:n m))
       (*     10 (:t m))
                 (:y m)))

(defn check? [proposal]
    (let [m (tomap proposal)
          one (one-value m)
          three (three-value m)
          eleven (eleven-value m)
          twenty (twenty-value m)]

        (= (+ one one one three three eleven)
           twenty)))

(defn print-solution [solution]
    (println (tomap solution)))

(doall (map print-solution (filter check? (permutations (range 10)))))

This program prints the correct solution, but I have some questions !
It seems to consume lot of memory (around 6GB). Do I miss something with the lazy evaluation ?
How can I change the code into a more idiomatic one ?

Thanks for your help and time !

Olivier

[Cornelius Goh]

Just my 2-cent suggestion : at your Permutation recursion function, may be try "recur" instead.

[Ashish Negi]

Your permutations is being called again for similar inputs..
Try using this and see that similar inputs like (2 3) are coming again for  (permutations [1 2 3 4])

(defn permutations [s]
  (prn s)          ;; This will print input

  (lazy-seq
   (if (seq (rest s))
     (apply concat (for [x s]
                     (map #(cons x %) (permutations (remove #{x} s)))))
     [s])))

Using the following solves that problem : It seems to be also not taking much memory :

(defn insert-at-every-pos [x v]
  (loop [s x
         e []
         r []]
    (if (empty? s)
      (conj r (into [v] x))
      (recur (pop s) (conj e (peek s)) (conj r (into (conj s v) e))))))

(defn permutations [s]
  (prn s)

  (lazy-seq
   (if (seq (rest s))

     (mapcat (fn [p] (insert-at-every-pos p (peek s))) (permutations (pop s)))
     [s])))

(filter nil? (permutations (vec (range 11))))

[Ashish Negi]

Though i am not totally sure why it is working..
How removing repeated calls solved the problem of memory ?
Other difference is not using `for` loop..

Do post your findings.. if you get it.

[Olivier Scalbert]

Thanks for your help.

I have replaced "my" permutations by "your" permutations code.
It works faster (16s against 20 or 24s). And it seems to consume much less memory.

Now, I will try to understand how it works, which is another story (for me of course!).

[Cornelius Goh]

https://en.m.wikipedia.org/wiki/Tail_call

Tail call optimization...

[Cornelius Goh]

continued my above reply... read the "factorial" example in the Wikipedia on tail recursion to save space and time. Hope it helps!

[Ashish Negi]

@Cornelius Goh
According to my current understanding..
Tail Call Optimization comes in picture when the `recursive-call`'s return value is not used after its return.
Then we do not need the stack..

But my permutation is not like that.. and hence can not be Tall-Call-Optimized..

[Cornelius Goh]

True. Clojure doesn't provide tail call optimization. According to Daniel Higginbotham book "Clojure for the Brave and True" (Page 102) he suggests using "recur" for performance reasons.

That is, in Olivier's original code, (sorry, without understanding his puzzle):

(defn permutations [s]
(lazy-seq
...
...
(map # (...) (recur (remove #...)))))
...

See if it improves performance by just using "recur" ?

[Gary Verhaegen]

But you can't do that, because you're using the return value there (specifically, as the argument to map). If you try it, you'll see that the compiler throws an error.

The idea behind tail call elimination is that, if the very last thing that your function, say fnA, does is returning the result of a call to another function, say fnB, then you do not need the stack frame of fnA during the call to fnB, and you can preemptively pop it before calling fnB. But this only works if calling fnB is the very last thing that fnA does: if fnA still has some work to do with the result of fnB, its stack cannot be destroyed. (You could argue that a sufficiently smart compiler could "trim" the stack to just what will be needed after the call to fnB, but it's not the same.)

A simple, well-known example is the case of the recursive factorial function:

(defn non-tce-fact
  [n]
  (if (zero? n)
    1
    (* n (non-tce-fact (dec n)))))

(defn tce-fact
  ([n] (tce-fact n 1))
  ([n p]
    (if (zero? n)
      p
      (recur (dec n) (* n p)))))

Note that in the first function, the result of the recursive call is used in the multiplication, whereas in the second function the result is directly the result of the recursive call.

Most common examples are of recursive functions, but TCE is (in principle) a general technique that can be applied to any function whose last instruction is a call to another function.

In Clojure, only recursive tail call elimination is supported, and only when the programmer explicitly requires it by using recur instead of an explicit recursive call. This has the advantage (and disadvantage) of being explicit and checked by the compiler (i.e. if you use recur in a non-tail position, you get an error).

[Cornelius Goh]

Thanks Gary for the explanation on "recur" in "TCE only" situation.

[Bobby Eickhoff]

doall holds on to the head of the seq, "causing the entire seq to reside in memory at one time." (https://clojuredocs.org/clojure.core/doall)

Instead, just find the first solution:

    (->> (permutations (range 10)) (filter check?) (first) (print-solution))

[Mark Engelberg]

The points the others have made are true, but not likely the true cause of your memory blow-up.

I believe the real source of your problem has to do with Clojure's use of chunked sequences rather than truly lazy sequences, which can bite you in scenarios like this one.  (range 10) produces a single chunk, so because of the way that for, map, filter, and remove work on chunked sequences, the entire permutations sequence is generated all at once and not lazily.

So your original solution was reasonable, but you need to "unchunk" (range 10) before you pass it to the permutations function.  One way to do that is with this function:

(defn- unchunk
  "Given a sequence that may have chunks, return a sequence that is 1-at-a-time
lazy with no chunks. Chunks are good for efficiency when the data items are
small, but when being processed via map, for example, a reference is kept to
every function result in the chunk until the entire chunk has been processed,
which increases the amount of memory in use that cannot be garbage
collected."
  [s]
  (lazy-seq
    (when (seq s)
      (cons (first s) (unchunk (rest s))))))

BTW, it's a perfectly good, valuable learning experience to write permutations on your own, but you'll get better performance if you use the implementation in clojure.math.combinatorics: https://github.com/clojure/math.combinatorics

[Ashish Negi]

Thanks puzzler for the explanation.
I tried out your `unchunk` and its works nicely..

I then googled around about chunk and memory issues..

I found most issues about chunking and stack overflow..
here.. https://stuartsierra.com/2015/04/26/clojure-donts-concat       [which is very good read for this question as well.. the diagram of lazy-seq's is great.]
with https://groups.google.com/forum/#!topic/clojure-dev/ewBuyloeiFs/discussion [Left recursion with concat as said in above article as well would stack overflow].

However, none talked about memory consumption.. Do anyone know about good practices with `chunking` and `memory consumption` ?
Can i say that : as long tail of recursive calls are happening due to chunking.. all the memory of intermediate steps is present at the same time.. leading to heavy memory usage.. ?  or is it something more subtle..

Some graphs that i found while profiling :

[Olivier Scalbert]

Thanks to all of you !
There are so much material in your answers that I need to wait this week-end to do some tests !

Clojure is cool !

[bernardH]

Hi !

On Friday, April 8, 2016 at 3:28:55 PM UTC+2, Olivier Scalbert wrote:

Hello everybody !

I just start learning Clojure and I am a complete newbie !

I have tried to solve this classical small puzzle with Clojure.
Assign one digit from {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} to each letter {o n e t h r l v w y} so that
one + one + one + three + three + eleven = twenty

[…]

How can I change the code into a more idiomatic one ?

For what it's worth, this can be done easily with the great loco library [loco] :
;; straight port of cf https://github.com/aengelberg/loco/blob/master/test/loco/integer/sendmoremoney1.clj
;; (:use loco.constraints
;;      loco.core))

(defn initialize-digits [vars]
  (for [v vars]
    ($in v 0 9)))

(def letters
  [:o :n :e :t :h :r :l :v :w :y])

(def puzzle-model
  (concat (initialize-digits letters)
          [($distinct letters)
           ($> :o 0)
           ($> :t 0)
           ($> :e 0)
           ($= ($+ ($* 3 ($scalar [:o :n :e] [100 10 1]))
                   ($* 2 ($scalar [:t :h :r :e :e] [10000 1000 100 10 1]))
                   ($scalar [:e :l :e :v :e :n] [100000 10000 1000 100 10 1]))
               ($scalar [:t :w :e :n :t :y] [100000 10000 1000 100 10 1]))]))
(time (solutions puzzle-model))

"Elapsed time: 61.496745 msecs"
({:y 8, :r 7, :v 1, :o 2, :n 3, :w 4, :e 5, :l 0, :h 9, :t 6})


Cheers,

bernard

[loco] https://github.com/aengelberg/loco
 

[Olivier Scalbert]

Whooww that is impressive !
Respect !!!

Olivier