Update Submatrix in Larger Matrix in Clojure

Question

How can I update a large matrix, represented as nested vectors, by inserting a smaller submatrix at a particular position.

(def submatrix [[1 1] [1 1]])
(def matrix [[0 0 0] [0 0 0] [0 0 0]])
(def pos [1 1])
(defn update-matrix
   "Returns new matrix with the submatrix inserted at the [x y] pos as
    the top left position of the submatrix."
   [matrix submatrix pos]
    ; implementation??
)

Desired output: (formatted for readability)

[[0 0 0]
 [0 1 1]
 [0 1 1]]

My progress so far:

I can update a subvector in a vector:

(def v [0 1 2 3 4 5 6])
(def subv ["x" "y" "z"])
(def pos 2)
(concat (take pos v) subv (drop (+ pos (count subv)) v)
; [0 1 "x" "y" "z" 5 6]

But I don't know where to go from here, or what might be most idiomatic.

Answer 1

Getting it right

We can define the required function as

(defn update-submatrix [m sub-m [x y]]
  (replace-subvec
    m
    (map (fn [l r] (replace-subvec l r y)) (subvec m x) sub-m)
    x))

... where (replace-subvec v s start) replaces the elements of vector v from index start with those of sequence s, as long as s lasts. For example,

(replace-subvec (vec (range 10)) (range 3) 5)
; [0 1 2 3 4 0 1 2 8 9]

A clear but slow implementation is

(defn replace-subvec [v s start]
  (vec (concat (subvec v 0 start) s (subvec v (+ start (count s))))))

... giving, for the example in the question,

(def submatrix [[1 1] [1 1]])
(def matrix [[0 0 0] [0 0 0] [0 0 0]])
(def pos [1 1])

(update-submatrix matrix submatrix pos)
; [[0 0 0] [0 1 1] [0 1 1]]

Speeding it up

The key to speeding up update-submatrix is to speed up replace-subvec.

We can do so in two ways:

• run through the altered elements by incrementing through a loop, and
• use a transient collection within the function.

This gives us

(defn replace-subvec [v s start]
  (loop [v (transient v), s s, i start]
    (if (empty? s)
      (persistent! v)
      (recur (assoc! v i (first s)) (rest s) (inc i)))))

The effect is identical.

Answer 2

You can reduce over a sequence of update coordinates, at each step copying one item from the submatrix into the appropriate place in the larger matrix:

user> (defn update-matrix [matrix submatrix [y x]]
        (reduce (fn [m [row col]]
                  (assoc-in m [(+ row y) (+ col x)] 
                            (get-in submatrix [row col])))
                matrix
                (for [y (range (count submatrix))
                      x (range (count (first submatrix)))]
                  [y x])))
#'user/update-matrix
user> (update-matrix [[0 0 0] [0 0 0] [0 0 0]] [[1 1] [1 1]] [1 1])
[[0 0 0] [0 1 1] [0 1 1]]

Answer 3

Here's my 15 min. shot at it:

(defn update-matrix
  "Returns new matrix with the submatrix inserted at the [x y] pos as
  the top left position of the submatrix."
  [matrix submatrix pos]
  (let [[x y] pos
        height (count submatrix)
        width (count (get submatrix 0))]
    (loop [i 0 m matrix]
      (if (< i height)
        (let [item (vec (concat (vec (drop-last width (get matrix x))) (get submatrix i)))]
          (recur (+ 1 i) (assoc m (+ i y) item)))
        m))))

Let me know if that doesn't work.