stairway.clj

(ns user)

(defn reached-top-of-staircase?
  "Tests to make sure the steps get us to the top of the stairway."
  [{:keys  [stairway-height]} step-vec]
  (= stairway-height (apply + step-vec)))

(defn compute-max-steps
  "The idea here is that the maximum number of steps we could take is the
  stairway height divided by the smallest step.   "
  [{:keys [stairway-height step-options]} ]
  (->> step-options
       (filter #(< 0 %))
       (apply min)
       (quot stairway-height)))

(defn smallest-possible-steps
  "This would be the smallest possible vector of step options."
  [{:keys  [stairway-height step-options] :as all}]
  (into []  (repeat
             (compute-max-steps  all)
             (apply min step-options))))

(defn largest-possible-steps
  "This would be the largest possible vector of step options."
  [{:keys  [stairway-height step-options] :as all}]
  (into []  (repeat
             (compute-max-steps  all)
             (apply max step-options))))

(defn inc-digit
  "Takes a number, and increments it to the next of the step options.
  If it is already the largest in the step options, it will return nil.
  "
  [{:keys [step-options]} d]
  (let [cur-index (first (keep-indexed #(if (= d %2) %1) step-options))
        next-index (inc cur-index)]
    (get step-options next-index nil)))

(defn inc-vector
  "
  Takes this: 0,0,0
  Returns this: 0,0,1

  At some point, it adjusts the base to increment: 0,1,0

  Only uses digits from step-options. "
  [{:keys [stairway-height step-options] :as all} v]
  (if (= v (largest-possible-steps all))
    nil  ; this would mean we are at the end of posibilities
    (let [v-len      (count v)                ; length of the current vector
          inc-value  (inc-digit all (last v))     ; this would be the next "value" to increment to.
          min-digit (apply min step-options)] ; if we go up a base number, this
                                        ; would be the min digit.
      (if inc-value  ;; returns nil if it can't increment and needs to increment base.
        (assoc v (dec v-len) inc-value) ;;
        (conj (inc-vector all
                          (into [] (drop-last v))) ; we wan we want to
                                        ; increment, drop last value, replace with "min digit"
              min-digit)))))

(defn generate-all-possibilities
  "Generates all possibilities.
  For instance:

  (generate-all-possibilities {:step-options [0 1 2 ] :stairway-height 3})

  [[0 0 1] [0 0 2] [0 1 0] [0 1 1] [0 1 2] [0 2 0]
  [0 2 1] [0 2 2] [1 0 0] [1 0 1] [1 0 2] [1 1 0]
  [1 1 1] [1 1 2] [1 2 0] [1 2 1] [1 2 2] [2 0 0]
  [2 0 1] [2 0 2] [2 1 0] [2 1 1] [2 1 2] [2 2 0]
  [2 2 1] [2 2 2] [2 2 2]] "
  [{:keys [stairway-height step-options] :as all}]
  (loop [cur-vector        (smallest-possible-steps all) ;; init to smallest possible steps.
         all-possibilities []]
    (if (= cur-vector (largest-possible-steps all))
      (conj all-possibilities cur-vector) ;; we are done.
      (let [result (inc-vector all cur-vector)]
        (recur result (conj  all-possibilities result))))))

(defn clean-step-options
  "Just take step options, make sure zero is one of the elements, and order it
  asc.  Basically a data cleansing step."
  [step-options]
  (-> step-options
      (conj 0) ;; make sure we have a zero.
      set ;; dedup
      sort ;; sort
      vec))


(defn num-ways
  "Given a tuple of step-options (how many steps i can take at a time) and a
  stairway hieght, return all combinations of the steps i could take to reach
  the top. https://www.youtube.com/watch?v=5o-kdjv7FD0  "
  [step-options stairway-height]
  (let [all {:step-options (clean-step-options step-options)
             :stairway-height stairway-height}]
    (->> (generate-all-possibilities all)
         (filter (partial  reached-top-of-staircase? all)) ; filter anything that doesn't get us to the top of the stairs.
         (map #(remove zero? %))                           ; cleanup.
         set)))

(comment
  
  (num-ways [0, 1, 2, 3] 5)

  ;=>  ((1 3 1) (3 1 1) (1 1 3) (1 1 1 1 1))

   (->>  (num-ways [0 11 12 9 23] 23)
         (sort-by count))

   ;=> ((23) (11 12) (12 11))
 )

https://www.youtube.com/watch?v=5o-kdjv7FD0