Ring of numbers where adjacent entries sum up to a prime

Question

Given a number n, find a permutation of the numbers 1...n such that all adjacent entries sum up to primes. If such a permutation does not exist, throw an error.

Is there a purely-functional way to do this problem? The solution, which apparently uses backtracking, given uses C++, a language which I am not very familiar with, and loops in loops in loops with very badly-named variable names and a whole lot of mutation. Even if the solution requires mutation, nested loops are really difficult to translate into Racket, the language I currently use.

A more general question would be, how to do backtracking algorithms purely functionally when the concept of backtracking seems to always involve maintaining a state of where you are currently and a big history breadcrumb global state variable that keeps getting mutated?

Of course the dumb way would be to generate all permutations and test them one by one, but are there more efficient ways, preferably implementing a backtracking method, to do so functionally?

Since I use Racket, the solution might not be purely functional but preferably mostly functional, i.e. no repeatedly mutating counter vars in loops or such.

Answer 1

I just wrote an implementation in Clojure, a functional Lisp-I, which you may find below. Because of the controversy in the commments to this answer, I will try to explain the code and the techniques used to achieve the result as good as possible, especially for those who are not Clojurists. Forgive me if I don't touch on everything in great detail and length.

This version does not mutate state. All of Clojures values are immutable, e. g. a vector [1 2] can not be altered once it has been constructed. When you want to concat that vector with another vector [3 4] you may invoke a function like concat like this (concat [1 2] [3 4]). Concat will return a new vector [1 2 3 4] and the two input vectors will be forgotten. The great thing is that behind the scenes, structural sharing is happening: The new vector [1 2 3 4] consists of the same data [1 2] and [3 4] consisted of. Also, if we had bound the vector [1 2] to a symbol a instead, after (concat a [3 4]) a would still be [1 2]. So while you are always generating new immutable values, in memory only the delta will be allocated.

One other feature of Clojure I am taking advantage of is laziness. E. g. you can build a sequence of all number 0 ... n with (range). The call to range returns an infinite sequence like (0 1 2 3 4 5...), but it is not realized until elements of it are consumed. Finally, many transformation functions return new lazy-sequences from lazy input sequences, so (filter even? (range)) would give me a lazy sequence of all numbers >= 0 for which the predicate even? (a boolean function) returns true - however, the filtering only happens when I actually consume elements from that sequence, e. g. (take 3 (filter even? (range))) will return (0 2 4): Until here, filter has been invoked five times (as many times as necessary to produce three elements or have the input sequence consumed).

The prime ring generator below utilizes this laziness. If you invoke (rings-of-primes 100) it immediately returns a lazy sequence of all possible prime rings with 100 elements from 1 to 100. Nothing is calculated, so if I wanted to have only three rings, I could do (take 3 (rings-of-primes 100)) and calculation would only happen for the production of three rings.

The core to the solution below is the function helper-fn which is defined within rings-of-primes. It takes two immutable values as arguments and refers to two other immutable values, length (the argument to rings-of-primes) and n-range (defined in rings-of-primes as seq [1 .. length]) in its body.

The two arguments to helper-fn are used, an immutable set of numbers that have been used in the possible ring passed as the second arg, acc (short for accumulator).

One of the great advantages of Clojure is that when you are dealing with immutable values, it's quite easy to write pure functions. helper-fn is one of those pure functions. It is defined as follows: It takes the input of a set of used numbers, and a vector of numbers which is supposed to be a partial ring of primes, and always returns a sequence of possible rings of primes that begin with the numbers in acc and have a size of length. If no rings are possible, helper-fn returns (), an empty list (not the same as nil in Clojure).

          (let [last-elem (peek acc)]
            (if (and (= length (count acc))
                     (is-prime?
                      (+ last-elem
                         (first acc))))
              [acc]

In the above code-snippet (the first lines of helper-fn), the symbol last-elem is bound to the last value of acc. Then within the conditional statement if two conditions are tested: 1. Has accumulator the user-desired length ((= length (count acc)))?, 2. Do the last and the first element add up to a prime number. If both conditions are matched, helper-fn returns [acc], a vector with exactly one element: The accumulator, a valid prime-ring. The nesting in an additional vector is needed because our function is supposed to return a sequence of valid prime-rings, not just a sequence of numbers.

Now what happens if the passed value is not a prime-ring, like when the function is invoked the first time within rings-of-primes: (helper-fn #{1} [1]). As you might have noticed, #{1} is the notation for a set, and within helper-fn, used will now be bound to #{1} and acc will be bound to [1].

Given that we have asked for a length of 4, the test-clause in the code snippet above will fail. What happens then?

              (let [parity-filter (if (even? last-elem)
                                    odd?
                                    even?)]
                (->> n-range
                     (filter #(and (parity-filter %)
                                   (not (used %))
                                   (is-prime? (+ %
                                                 last-elem))))
                     (lazy-mapcat #(helper-fn 
                                    (conj used %)
                                    (conj acc %))))))))]

The parity-filter symbol will be bound to either the predicate function odd? or to the predicate function even?, depending on whether the last-element of acc is even or odd. The reason is that you can divide even numbers by two, and adding two even numbers or two odd numbers always results in an even number which can't be a prime number then. So we only want the numbers with the opposite parity of the last element of acc, last-elem.

->> is an awesome macro. It does not do anything except for reordering the code you put into it. That is one of the advantages of Clojure being a lisp, that all your code is data that can be manipulated before evaluation. ->> reorders your code so (->> x (doY) (doZ baz)) => (doZ baz (doY x)). In other words, the first argument is appended to the end of the second form, which is appended to the end of the third form and so on.

So in this case, n-range, which was generated at the beginning of rings-of-primes, another immutable value, will be threaded with ->>. n-range will always be a sequence [1 .. length]. Now this sequence must be filtered. We define a small function, a lambda, on the fly as the first argument to filter:

                             #(and (parity-filter %)
                                   (not (used %))
                                   (is-prime? (+ %
                                                 last-elem)))

In this case #(...) creates a function with one argument to which we refer as %. E. g. #(+ % %) would create a function that takes one argument and doubles it. Our lambda is a predicate function that tests the argument for three conditions: 1. It must pass the parity-filter, 2. It may not be in the set used (you can invoke sets like functions and they return whether they contain the argument), 3. Added to the last-elem of acc, it must be a prime-number. If this three conditions match, it is a possible candidate for the next iteration of the prime ring we are building, and it will be part of the lazy sequence returned by the filter expression.

After that, a function lazy-mapcat that comes with this source, is invoked. It takes a transformation function and a sequence of elements (our filtered candidates), transforms each input element with the transform function and concats the returned value (a sequence) to the other returned values. The transformation function may return any kind of sequence, also the empty sequence. Let's have a closer look at the transformation function:

                                 #(helper-fn 
                                    (conj used %)
                                    (conj acc %))

Yes! It's a call to helper-fn itself. conj takes a collection and an argument and returns a new collection with that argument in it. Here we put the value taken from our filtered sequence into a new version of used, also create a new version of acc with that number in it, and pass them to helper-fn. Now go back to line 1. helper-fn will then (after many more recursive steps) return a sequence of possible prime-rings and because of mapcat we do that for each candidate that may be the next valid number in the current prime-ring. All the resulting sequences of rings will be concatenated to one sequence of rings. Of course, in some cases helper-fn will return an empty list, and on a higher level, that empty list will be concataned with other lists - also within a mapcat expression.

As you can see, no state is mutated. The resulting function is pure and can also be invoked with odd lengths or negative input values, in which case it will (mathematically correctly) return an empty list as a result.

You could say that the backtracking happens with acc passed to helper-fn, but much more I'd like to think of this implementation of a pure function call that results in the self assembly of possible prime-rings through a series of recursive function calls.

;; Clojure implementation of http://coj.uci.cu/24h/problem.xhtml?abb=1196
;; This version generates all possible rings of primes for any given n
;; Leon Grapenthin, Nov. 14 2013

(def is-prime?
  "Returns true if n is a prime number. Memoized."
  (memoize              ;; remember all results returned by this function
                        ;; so that a second call with the same n does not
                        ;; require calculation
   (fn is-prime?
     [n]
     (cond
      (even? n) (= 2 n) ;; if n is even, return whether
                        ;; its 2, the only even prime number
      (= 1 n) false     ;; if n is one, return false
      :otherwise
      (->> (range 2 n)  ;; build a sequence from 2 to n
           (filter (comp zero?
                         (partial mod n))) ;; filter those were dividing
                                           ;; n by them has a rest of 0
           empty?))))) ;; none could be found? => It's a prime number.

(defn lazy-mapcat
  ;; stolen from http://clojurian.blogspot.de/2012/11/beware-of-mapcat.html
  [f coll]
  (lazy-seq
   (if (not-empty coll)
     (concat
      (f (first coll))
      (lazy-mapcat f (rest coll))))))

(defn rings-of-primes
  "Returns a lazy sequence of possible prime rings for length."
  [length]
  (let [n-range (range 1 (inc length))
        helper-fn
        (fn helper-fn
          ;; tries to build the seq until acc has length and the ring
          ;; condition is fulfilled, otherwise returns nil
          [used acc]
          (let [last-elem (peek acc)]
            (if (and (= length (count acc))
                     (is-prime?
                      (+ last-elem
                         (first acc))))
              [acc]
              (let [;; slight optimization: a prime number (+ x y) with
                    ;; (not= x y) can only be built when the parities of
                    ;; x and y differ:
                    parity-filter (if (even? last-elem)
                                    odd?
                                    even?)]
                (->> n-range
                     (filter #(and (parity-filter %)
                                   (not (used %))
                                   (is-prime? (+ %
                                                 last-elem))))
                     (lazy-mapcat #(helper-fn 
                                    (conj used %)
                                    (conj acc %))))))))]
    (helper-fn #{1} [1])))

;; (time
;;  (first (rings-of-primes 100)))
;; "Elapsed time: 57.316798 msecs"
;; [1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18 19 22
;;  21 20 23 24 29 30 31 28 25 34 27 26 33 38 35 32 39
;;  40 43 36 37 42 41 48 49 52 45 44 53 50 47 54 55 46
;;  51 56 57 70 61 66 65 62 69 58 73 64 63 68 59 72 67
;;  60 71 78 79 84 83 74 75 76 81 82 85 88 91 90 89 92
;;  87 80 77 86 93 98 95 96 97 94 99 100]

Answer 2

You've got your finger right on the nose of the solution but just don't quite see it, so let's take a quick detour and see if it becomes a little clearer.

In a purely functional language, where you can't mutate anything and therefore cannot have loop indexers etc, how do you write loops?

That's right; you recurse. Why? Because when your only state is in local, and immutable, the only way to change the values in your local is to create new local frames with the values you want.

Now then, back to backtracking, the beauty of not having indices to manage in a loop, is that when you want to move back a few iterations; all you do is return from each frame until you're back where you want to be.

Alternatively, you can backtrack functionally by holding on to your old closures states and move forward into them instead of backwards up the stack when you want to go to an old state. This is however unpleasant as you alluded to above.

Now if you want to get an even more beautiful look at backtracking, you can take a look at Monads and how you do control flow with them, google and I'm sure you can find monadic implementations in racket. Looking at Parser Combinators is a great place to see functional approaches to backtracking.