Find all paths to climb a digital mountain

gistfile1.clj

(ns climbing
  (:require [clojure.string :as string])
  )

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; part  a ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Each mountain block has 2 children it follows that for a mountain of size n
; the total paths will equal total number of block sequences from top to base
; taking one from each row which is given by p=2^(n-1)

(defn simple-path-count
  "How many ways are there to climb a mountain of size n?"
  [n]
  (Math/pow 2 (- n 1))
  )


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; part  b ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; The input mountain definition is parsed and its blocks stored in an array with
; index equal to the block position. Block position starts with 0
; for top block and ends with n-1 for right most base block. An exhaustive depth
; first search is used to find all path taking into consideration the placement of
; paths at arbitrary positions.

(defn filter-mountain-levels
  "Remove blanks from input mountain"
  [lvls]
  (map
    (fn [x] (filter #(not (string/blank? %)) x))
    lvls
    )
  )

(defn parse-mountain
  "Turn input mountian into a list of lists of strings representing the state of each
  block"
  [mnt]
  (map #(map str %) mnt)
  )

(defn get-row
  "This functions returns the block row given its position"
  [pos]
  (def est-row (* 0.5 (- (Math/sqrt (+ (* 8 pos) 9)) 3)))
  (def int-row (int est-row))
  (if (< 0.0 (- est-row int-row))
    (+ 1 int-row)
    int-row
    )
  )

(defn get-max-pos
  "Returns the largest block position index for a given row"
  [row]
  (- (* 0.5 (* row (+ row 1))) 1)
  )

(defn create-block
  "Create db entry for block. The first entry in list contains position of last block
  before base row."
  [db blk]
  (def pos  (count (rest db)))
  (def row (get-row pos))
  (def children (if (<= pos (first db))
                  [(+ (+ pos row) 1), (+ (+ pos row) 2)]
                  []
                  )
    )
  (conj db {:value blk :children children})
  )

(defn create-db
  "Create db of mountain block data from mountain input"
  [mnt]
  (def position-before-base (-> (count (flatten mnt)) (get-row) (- 1) (get-max-pos)))
  (reduce
    (fn [db row] (reduce create-block db row))
    [position-before-base]
    mnt
    )
  )

(defn count-paths
  "Count paths to mountain base from mountain top using exahaustive depth first search"
  [blk_index db]
  (def blk (nth db blk_index))
  (cond
    (empty? (:children blk))
      1
    (= (:value blk) "X")
      0
    :else
      (let [children (:children blk)
            left-child (first children)
            right-child (nth children 1)]
        (+ (count-paths left-child db)
           (count-paths right-child db))
        )
    )
  )

(defn path-count-with-traps
  "How many ways are there to climb this 'mountain' with traps?
   'mountain' represents a mountain of size n = (count mountain),
   and (nth mountain i) is a String with exactly i+1 'O's or 'X's 
   and the rest spaces.
   "
  [mountain]
  (def db (->
            mountain
            parse-mountain
            filter-mountain-levels
            create-db
            )
    )
  (count-paths 0 (rest db))
  )

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; part b bonus ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Find closed form solution for paths from base to top for mountain of size n with
; trap located at row r and column c.
;
; Mountain coordinate system has origin at mountain top, left most base block at
; (n-1,-n+1) and right most base block at (n-1, n-1)
;
; Number of paths will be total paths from base top minus the number of paths
; passing through trap.
;
; Total paths is given by 2^(n-1)
;
; Number of paths passing through trap has 2 parts, paths terminating at trap and
; paths originating at trap. Total paths passing through trap will be product of
; two parts.
;
; Number of paths terminating at trap is given by 2^(n-r-1)
;
; Total paths originating from trap is a little harder. If a few are computed manually
; it can be seen that a pattern forms where the number of paths originating
; from a block is equal to the sum of the paths originating from the two blocks above it.
; This is Pascal's Triangle. It follows that the total number of paths originating from trap
; is given by the binomial coefficient of the coordinates, namely,
;
; binomial-coefficient(r, (r+c)/2)
;
; Total paths passing through trap is,
;
; 2^(n-r-1) * binomial-coefficient(r, (r+c)/2)
;
; Total paths is then
;
;  2^(n-1)[1-2^(-r) * binomial-coefficient(r, (r+c)/2)]

(defn fact
  ([n] (fact n 1))
  ([n acc]
    (if (= (int n) 0)
      acc
      (recur (dec n) (* acc n))
      )
    )
  )

(defn binomial-coefficient
  [n k]
  (/ (fact n) (* (fact k) (fact (- n k))))
  )

(defn path-count-with-trap-at-row-and-column
  "Compute total paths from base to mountain top for mountain of size n
  with trap located at row r and column c"
  [n r c]
  (def k (* 0.5 (+ c r)))
  (def total-paths (Math/pow 2 (- n 1)))
  (def trap-factor (* (binomial-coefficient r k) (Math/pow 2 (- r))))
  (int (* total-paths (- 1 trap-factor)))
  )