Last active
August 7, 2019 16:44
-
-
Save joefromct/55b7542f50264bbdbab23dd2df4ad852 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(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)) | |
) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
https://www.youtube.com/watch?v=5o-kdjv7FD0