matrix.clj

(ns matrix)

(defn mget
  [m i j]
  (-> m (nth j) (nth i)))

(defn mset
  [m i j v]
  (assert (and (< j (count m))
               (< i (count (first m)))))
  (update m j #(assoc % i v)))

(defn mzero
  [i j]
  (vec (take j (repeat (vec (take i (repeat 0)))))))

(defn set-row
  [m i v]
  (assoc m i (if (sequential? v)
               v
               (->> v repeat (take (-> m first count)) vec))))

(defn set-col
  [m i v]
  (reduce (fn [a b] (mset a i b v)) m (range (count m))))

;; example usage

(defn dpmat
  "Side-effecting num paths through matrix solution"
  [i j]
  (let [array (-> (mzero i j)
                  (set-row 0 (bigint 1))
                  (set-col 0 (bigint 1))
                  to-array-2d)]
    (doseq [i (range 1 i)
            j (range 1 j)]
      (aset array j i (+ (aget array (dec j) i)
                         (aget array j (dec i)))))
    (aget array (dec j) (dec i))))

(defn dpmat-pure
  "Non side-effecting compuatation"
  [i j]
  (let [mat (-> (mzero i j)
              (set-row 0 (bigint 1))
              (set-col 0 (bigint 1)))]
    (mget
     (reduce (fn [m [i j]]
               (mset m i j
                     (+ (mget m (dec i) j)
                        (mget m i (dec j)))))
             mat
             (for [i (range 1 i)
                   j (range 1 j)]
               [i j]))
     (dec i)
     (dec j))))

(declare dpmatm)

(defn dpmat' [i j]
  "Recursive num paths through matrix solution"
  (if (or (= i 1) (= j 1))
    (bigint 1)
    (+ (dpmatm (dec i) j)
       (dpmatm i (dec j)))))

(def dpmatm (memoize dpmat'))

(defn combinatorial-solution
  [i j]
  (org.apache.commons.math3.util.ArithmeticUtils/binomialCoefficientDouble
   (- (+ i j) 2) (dec (min i j))))