Stair-climbing puzzle
From Chung-Chieh Shan (LtU):
You are encouraged to solve this task according to the task description, using any language you may know.
Your stair-climbing robot has a very simple low-level API: the "step" function takes no argument and attempts to climb one step as a side effect. Unfortunately, sometimes the attempt fails and the robot clumsily falls one step instead. The "step" function detects what happens and returns a boolean flag: true on success, false on failure. Write a function "step_up" that climbs one step up (by repeating "step" attempts if necessary). Assume that the robot is not already at the top of the stairs, and neither does it ever reach the bottom of the stairs. How small can you make "step_up"? Can you avoid using variables (even immutable ones) and numbers?
Clojure
First, some boilerplate.
<lang clojure>
- the initial level
(def level (atom 41))
- the probability of success
(def prob 0.5001)
(defn step
[] (let [success (< (rand) prob)] (swap! level (if success inc dec)) success) )
</lang>
Tail-recursive
The internal recursion uses a counter; see the function documentation.
<lang clojure> (defn step-up1
"Straightforward implementation: keep track of how many level we need to ascend, and stop when this count is zero." [] (loop [deficit 1] (or (zero? deficit)
(recur (if (step) (dec deficit) (inc deficit)))) ) ) </lang>
Recursive
This satisfies Chung-chieh's challenge to avoid using numbers. Might blow the stack as p approaches 0.5.
<lang clojure> (defn step-up2
"Non-tail-recursive. No numbers." [] (if (not (step)) (do (step-up2) ;; undo the fall
(step-up2) ;; try again )
true))
</lang>
OCaml
<lang ocaml>let rec step_up() =
if not(step()) then (step_up(); step_up())
- </lang>
Python
Iterative
<lang python>def step_up1()
"Straightforward implementation: keep track of how many level we need to ascend, and stop when this count is zero." deficit = 1 while deficit > 0: if step(): deficit -= 1 else: deficit += 1</lang>
Recursive
This satisfies Chung-chieh's challenge to avoid using numbers. Might blow the stack as p approaches 0.5.
<lang python>def step_up2():
"No numbers." if not step(): step_up2() # undo the fall step_up2() # try again</lang>
Tcl
The setup (note that level
and steps
are not used elsewhere, but are great for testing…)
<lang tcl>set level 41
set prob 0.5001
proc step {} {
global level prob steps incr steps if {rand() < $prob} {
incr level 1 return 1
} else {
incr level -1 return 0
}
}</lang>
Iterative Solution
All iterative solutions require a counter variable, but at least we can avoid any literal digits... <lang tcl>proc step-up-iter {} {
for {incr d} {$d} {incr d} {
incr d [set s -[step]]; incr d $s
}
}</lang>
Recursive Solution
This is the simplest possible recursive solution: <lang tcl>proc step-up-rec {} {
while {![step]} step-up-rec
}</lang>