Project Euler Problem 15

Ivar Thorson bio photo By Ivar Thorson

I remembered the answer to this this one from school…probably because my statistics professor was extremely attractive and somehow her words lodged themselves especially deeply in my young mind.

Anyway, finding the number of routes through a grid uses the same math as binomial coefficients. Two quick definitions of factorial later, and this problem was done:

;; Humorous recursive definitions are so amusing
(def factorials (map first (iterate (fn [[p n]] [(* p n) (+ 1 n)]) [1 1])))
(defn factorial [a] (nth factorials a))

;; More practical definition:
(defn factorial [n] (reduce * (range 2 (inc n))))

(defn a-choose-b [a b]
  "Returns the number of ways of choosing b items from a items."
  (/ (factorial a)
     (* (factorial b)
        (factorial (- a b)))))

(defn monotonic-paths [n]
  "Returns # of monotonic paths through grid of n x n size"
  (a-choose-b (* 2 n) n))

(defn euler-15 [gridsize]
  (monotonic-paths gridsize))

(euler-15 20)

See you tomorrow!