Hackerrank 3
Challenge
Prit’s solution
Takes 0.037915 msecs
on input [0 0 0 1 0 1 0]
(defn jumping-on-clouds [c]
"O(n), (= n (count c))
Had to look up the algorithm after couldn't do for 1h.
Was doing something more complicated and O(2^n)"
"""
(loop [c [[c 0]]]
(if-not (seq (filter (fn [[path-left steps]] (seq path-left)) c))
(recur #(map (fn [[path-left steps]]
(if (= (second path-left) 0)
[(drop 2 path-left) (inc steps)])) c)
)
))
(map (fn [[path-left steps]]
[(if (= (second path-left) 0)
[(drop 2 path-left) (inc steps)])
(if (= (first path-left) 0)
[(rest path-left) (inc steps)])
])
[[[1 0 0] 0] [[0 0 1 0] 9]]
)
"""
(loop [c (rest c) jumps 0]
(if (seq c)
(if (= (second c) 0)
(recur (drop 2 c) (inc jumps)) ;; looked up drop online
(recur (rest c) (inc jumps)))
jumps)))
RP’s solution
Takes 0.437988 msecs
on input [0 0 0 1 0 1 0]
(defn cloud
[input]
(let [jump-small 1 jump-big 2]
(trampoline
(fn jump [idx cnt]
(let [idx' (+ idx jump-big)]
(if-let [?zero-or-one (get input idx')]
#(if (zero? ?zero-or-one) ;big or small jump?
(jump idx' (inc cnt)) ;big!
(let [idx'' (+ idx jump-small)] ;else, small
(jump idx'' (inc cnt))))
cnt))) ;else, we are done, return jump count
0 0)))