Stair-climbing puzzle

From Chung-Chieh Shan (LtU):

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?

C++

<lang cpp> void step_up() {

 while (!step()) step_up();

} </lang>

The following uses a variable and is a bit longer, but avoids a possible stack overflow: <lang cpp> void step_up() {

 for (int i = 0; i < 1; step()? ++i : --i);

} </lang>

Clojure

First, some boilerplate.

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>

E

This is at first a very direct

Translation of: Clojure

The problem framework:

<lang e>var level := 41 var prob := 0.5001

def step() {

   def success := entropy.nextDouble() < prob
   level += success.pick(1, -1)
   return success

}</lang>

Counting solution:

<lang e>def stepUpCounting() {

   var deficit := 1
   while (deficit > 0) {
       deficit += step().pick(-1, 1)
   }

}</lang>

Ordinary recursive solution: <lang e>def stepUpRecur() {

   if (!step()) {
       stepUpRecur()
       stepUpRecur()
   }

}</lang>

Eventual-recursive solution. This executes on the vat queue rather than the stack, so while it has the same space usage properties as the stack-recursive version it does not use the stack which is often significantly smaller than the heap. Its return value resolves when it has completed its task.

<lang e>def stepUpEventualRecur() {

   if (!step()) {
       return when (stepUpEventualRecur <- (),
                    stepUpEventualRecur <- ()) -> {} 
   }

}</lang>

Fully eventual counting solution. This would be appropriate for controlling an actual robot, where the climb operation is non-instantaneous (and therefore eventual): <lang e>def stepUpEventual() {

   # This general structure (tail-recursive def{if{when}}) is rather common
   # and probably ought to be defined in a library.
 
   def loop(deficit) {
       if (deficit > 0) {
           return when (def success := step()) -> {
               loop(deficit + success.pick(-1, 1))
           }
       }
   }
   return loop(1)

}</lang>

Haskell

In Haskell, stateful computation is only allowed in a monad. Then suppose we have a monad Robot with an action step :: Robot Bool. We can implement stepUp like this:

<lang haskell>stepUp :: Robot () stepUp = untilM step stepUp

untilM :: Monad m => m Bool -> m () -> m () untilM test action = do

   result <- test
   if result then return () else action >> untilM test action</lang>

Here's an example implementation of Robot and step, as well as a main with which to test stepUp.

<lang haskell>import Control.Monad.State import System.Random (StdGen, getStdGen, random)

type Robot = State (Int, StdGen)

step :: Robot Bool step = do

   (i, g) <- get
   let (succeeded, g') = random g
   put (if succeeded then i + 1 else i - 1, g')
   return succeeded

startingPos = 20 :: Int

main = do

   g <- getStdGen
   putStrLn $ "The robot is at step #" ++ show startingPos ++ "."
   let (endingPos, _) = execState stepUp (startingPos, g)
   putStrLn $ "The robot is at step #" ++ show endingPos ++ "."</lang>

J

Solution (Tacit): <lang j>step =: 0.6 > ?@0: attemptClimb =: [: <:`>:@.step 0: isNotUpOne =: -.@(+/@])

step_up=: (] , attemptClimb)^:isNotUpOne^:_</lang> Note that 0: is not a number but a verb (function) that returns the number zero irrespective of its argument(s). Therefore the above solution for step_up meets the restrictions of no variables or numbers.

J's verbs (functions) always take an argument i.e. there is no such thing as a niladic verb. Verbs that ignore their arguments (e.g. step and attemptClimb) achieve the same effect.

Solution (Explicit): <lang j>step_upX=: monad define

 ClimbAttempts=. y
 while. -. +/ClimbAttempts do. 
   ClimbAttempts=. ClimbAttempts , <:`>:@.step #
 end.

)</lang>

Example usage: <lang j> step_up NB. output is sequence of falls & climbs required to climb one step. _1 1 _1 _1 1 1 1

  +/\ _1 1 _1 _1 1 1 1  NB. running sum of output (current step relative to start)

_1 0 _1 _2 _1 0 1

  +/\ step_up         NB. another example

_1 _2 _3 _2 _3 _2 _1 _2 _3 _4 _3 _2 _3 _2 _3 _2 _3 _2 _1 _2 _1 _2 _1 0 1</lang>

OCaml

<lang ocaml>let rec step_up() =

 while not(step()) do
   step_up()
 done

</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."
 while not step():
   step_up2() # undo the fall</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>