CODEWITHSUNDEEP
recursionvectorclojurelisptail-recursion
Jack Evans
Jack Evans

Reputation: 1717

Clojure, sum a list of vectors, recording positions along the way

Say I have a list of vectors

([0 0] [1 0] [1 0] [1 0])

I want to be able to add the list of vectors together and record each unique position along the way. 

                [0 0]
[0 0] + [1 0] = [1 0]
[1 0] + [1 0] = [2 0]
[2 0] + [1 0] = [3 0]

Giving 4 unique positions.

([0 0] [1 0] [2 0] [3 0])

Any idea how I could achieve this in Clojure?

I've tried the following code, but it overflows for large number of vectors :(

(defn add-vectors [vectors]
  (let [[a b] vectors]
    (vec(map + a b))))

(defn get-positions [dirs positions]
  (if (empty? (rest dirs))
    (set positions)
    (do
      (let [next-pos (add-vectors (take 2 dirs))]
        (get-directions (conj (rest (rest dirs)) next-pos) (conj positions next-pos))))))

the (conj (rest (rest dirs)) replaces the first element in the next recursive call with the sum of the first two vectors from the last call.

Upvotes: 1

Views: 884

Answers (1)

Sam Estep
Sam Estep

Reputation: 13324

To add two numbers together, you can use the + function, as you know:

(+ 2 1)
;;=> 3

To add two vectors together, you can use the mapv function to zip together the two vectors using +:

(mapv + [1 0] [1 0])
;;=> [2 0]

To perform a left fold of this vector addition across a sequence of vectors, you can use reduce:

(reduce #(mapv + %1 %2) [[0 0] [1 0] [1 0] [1 0]])
;;=> [3 0]

Or, replacing that function literal with a usage of partial:

(reduce (partial mapv +) [[0 0] [1 0] [1 0] [1 0]])
;;=> [3 0]

To obtain all the intermediate steps of this left fold, you can use reductions:

(reductions (partial mapv +) [[0 0] [1 0] [1 0] [1 0]])
;;=> ([0 0] [1 0] [2 0] [3 0])

Finally, to return only the unique elements from this sequence, you can use set:

(set (reductions (partial mapv +) [[0 0] [1 0] [1 0] [1 0]]))
;;=> #{[0 0] [1 0] [3 0] [2 0]}

Upvotes: 7

Related Questions