Skip to content

Instantly share code, notes, and snippets.

@malloc47
Last active May 24, 2016 02:45
Show Gist options
  • Save malloc47/454aab6b368b2980be5d3a7926bee9f1 to your computer and use it in GitHub Desktop.
Save malloc47/454aab6b368b2980be5d3a7926bee9f1 to your computer and use it in GitHub Desktop.
(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))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment