Stair-climbing puzzle: Difference between revisions

From [http://lambda-the-ultimate.org/node/1872 Chung-Chieh Shan] (LtU):

 

 

<pre>

func step_up()

* Inductive case (if the step() call returns false): Assume that recursive calls to step_up() step up one step. It stepped down one step (because step() returned false), but now we step up two steps using two step_up() calls. QED

 

The second (tail) recursion above can be turned into an iteration, as follows:

<pre>

}

</pre>

 

=={{header|ActionScript}}==

===Iterative===

{

var i:int = 0;

if(step())i++;

else i--;

===Recursive===

{

if(!step())

stepUp();

}

=={{header|Ada}}==

begin

while not Step loop

Step_Up;

end loop;

The following is a test program simulating Step:

with Ada.Text_IO;

 

Reset (Dice);

Step_Up;

Sample output:

<pre>

=={{header|Aime}}==

{{trans|C}}

{

while (!step()) {

step_up();

}

 

=={{header|ALGOL 68}}==

 

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8.8d.fc9.i386]}}

BEGIN

WHILE NOT step DO

step up

OD

PROC scaffolding = VOID:

BEGIN

END # scaffolding #;

 

Sample output:

<pre>

Climbed up to +1

</pre>

 

=={{header|AutoHotkey}}==

Recursive solution:

{

While !step()

step_up()

 

=={{header|BASIC}}==

For many (most?) BASICs, <code>STEP</code> is a (case-insensitive) keyword, therefore the "step" function would need a different name -- in this example, "step1". (Also, for some BASICs -- notably those influenced by [[Microsoft]]'s [[QuickBASIC]] -- the underscore character ("'''_'''") is invalid inside subroutine names.)

 

IF NOT step1 THEN stepup: stepup

 

See also: [[#BBC BASIC|BBC BASIC]], [[#Liberty BASIC|Liberty BASIC]], [[#PureBasic|PureBasic]], [[#TI-83 BASIC|TI-83 BASIC]]

=={{header|BBC BASIC}}==

Recursive solution:

IF NOT FNstep PROCstepup : PROCstepup

 

=={{header|C}}==

{

while (!step()) {

step_up();

}

 

The following uses a variable and is a bit longer, but avoids a possible stack overflow by risking a probably less likely integer overflow instead:

{

int i = 0;

}

}

 

=={{header|C++}}==

{

while (!step()) step_up();

 

The following uses a variable and is a bit longer, but avoids a possible stack overflow:

{

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

 

=={{header|Clojure}}==

First, some boilerplate.

 

(def level (atom 41))

 

(let [success (< (rand) prob)]

(swap! level (if success inc dec))

 

=== Tail-recursive ===

The internal recursion uses a counter; see the function documentation.

 

"Straightforward implementation: keep track of how many level we

need to ascend, and stop when this count is zero."

(or (zero? deficit)

(recur (if (step) (dec deficit)

 

=== Recursive ===

''p'' approaches 0.5.

 

"Non-tail-recursive. No numbers."

[]

(step-up2) ;; try again

)

=={{header|Common Lisp}}==

 

=={{header|D}}==

The recursive version (note that "step_up" is equivalent to "step_up()" in D):

{

while(!step)

step_up;

The non-recursive version, using 1 variable:

{

for(uint i = 0; i < 1; step ? ++i : --i) {};

Test program:

import std.random;

 

rand_seed(0, 0); // to make it somewhat repeatable

step_up;

Sample output:

<pre>Fell down to -1

Climbed up to 0

Climbed up to 1</pre>

 

=={{header|E}}==

The problem framework:

 

var prob := 0.5001

 

level += success.pick(1, -1)

return success

 

Counting solution:

 

var deficit := 1

while (deficit > 0) {

deficit += step().pick(-1, 1)

}

 

Ordinary recursive solution:

if (!step()) {

stepUpRecur()

stepUpRecur()

}

 

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.

 

if (!step()) {

return when (stepUpEventualRecur <- (),

stepUpEventualRecur <- ()) -> {}

}

 

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

 

[[Category:E examples needing attention]]

# This general structure (tail-recursive def{if{when}}) is rather common

# and probably ought to be defined in a library.

}

return loop(1)

 

=={{header|EchoLisp}}==

(define (step-up) (while (not (step)) (step-up)))

;; checking this is tail-recusive :

(climb stairs)

(writeln 'stairs stairs 'probability success 'steps STEPS)))

 

{{out}}

</pre>

 

 

=={{header|Erlang}}==

-module(stair).

-compile(export_all).

step_up() ->

step_up(step()).

=={{header|Euphoria}}==

if not step() then

step_up()

step_up()

end if

 

=={{header|Forth}}==

Recursive. May exceed return stack unless compiler optimizes tail calls.

Counting. Avoids using a named variable.

 

=={{header|Fortran}}==

 

{{works with|Fortran|90 and later}}

implicit none

 

end subroutine step_up_iter

 

=={{header|Go}}==

38 bytes, no variables, no numbers.

 

=={{header|Haskell}}==

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

 

stepUp = untilM step stepUp

 

untilM test action = do

result <- test

 

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

 

import System.Random (StdGen, getStdGen, random)

 

putStrLn $ "The robot is at step #" ++ show startingPos ++ "."

let (endingPos, _) = execState stepUp (startingPos, g)

 

=={{header|Icon}} and {{header|Unicon}}==

is implemented in Icon (or Unicon) and fails only when the implementation in

another language returns <tt>false</tt>, then:

return step() | (step_up(),step_up())

 

You can subtract a few more characters (and multiply the difficulty

of understanding) with:

(|not step(), step_up())

 

=={{header|J}}==

'''Solution (Tacit):'''

attemptClimb =: [: <:`>:@.step 0:

isNotUpOne =: -.@(+/@])

 

Note that <code>0:</code> is not a number but a verb (function) that returns the number zero irrespective of its argument(s). And, arguably, infinity is not any specific number. And, finally, <code>step</code> is presumed to pre-exist in the task description. Therefore the above solution for <code>step_up</code> could validly be said to meet the restrictions of no variables or numbers.

 

 

'''Solution (Explicit):'''

while. -. +/y do. y=. y , _1 1 {~ step 0 end.

)

step_upR=: monad define NB. recursive (stack overflow possible!)

while. -. step'' do. step_upR'' end.

 

'''Example usage:'''

_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

 

 

Another approach might be:

 

 

Here, the argument is the number of the starting step and the result is a list of the numbers of each visited step including the initial and final steps. For example:

 

2 1 0 1 2 3

keepTrying 3

3 2 3 2 3 2 3 4

keepTrying 4

 

=={{header|Java}}==

{{trans|C++}}

while (!step()) stepUp();

The following uses a variable and is a bit longer, but avoids a possible stack overflow:

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

 

=={{header|jq}}==

 

Since jq is a purely functional language, we need to keep track of time explicitly. This can be done using a clock that ticks the time:

To model the robot's success and failure, we shall assume a sufficiently large array of 0/1 values is available.

To avoid problems with modeling infinite time, we will pad the array with 1s if necessary.

 

"step" returns true or false based on the current time (the input) and the value of "random":

random as $r

 

We can now define step_up:

if step then tick

else tick | step_up | step_up

Now we can start the simulation at time 0; step_up will then emit the number of "step" attempts that have been made to achieve success:

{{out}}

===Tail Call Optimization===

To take advantage of jq's TCO (available in versions of jq after the release of Version 1.4), the step_up

function must be tail-recursive and have arity 0. This can be

achieved by providing [time, goal] as the input as follows:

.[0] as $time | .[1] as $goal

| if $goal == 0 then $time

if $time|step then $goal - 1 else $goal + 1 end

| [ ($time|tick), .] | tco_step_up

The simulation can then be started as follows:

 

=={{header|Liberty BASIC}}==

'Run it several times to see the differences; sometimes the robot falls

'quite a ways before making it to the next step up, but sometimes he makes it

Print "Robot fell down"

End If

 

=={{header|Logo}}==

Recursive.

if not step [step.up step.up]

Constant space (fully tail-recursive).

if :n=0 [stop]

(step.up ifelse step [:n-1] [:n+1])

 

=={{header|Lua}}==

 

function step_up()

while not step() do step_up() end

end

 

 

=={{header|MATLAB}}==

while ~step()

step_up();

 

=={{header|Nim}}==

 

=={{header|OCaml}}==

while not(step()) do

step_up()

done

 

=={{header|Oz}}==

Recursive solution:

if {Not {Step}} then

{StepUp} %% make up for the fall

{StepUp} %% repeat original attempt

end

Might lead to a stack overflow because the first call to <code>StepUp</code> is not in tail position.

 

Iterative solution:

Level = {NewCell 0}

in

end

end

Oz has arbitrary large integers. So if the robot is very unlucky, the contents of the <code>Level</code> variable will fill up all the memory and the program will fail. I believe this problem needs infinite memory to be solved for all cases.

 

=={{header|PARI/GP}}==

 

=={{header|Pascal}}==

Recursive solution:

begin

while not step do

stepUp;

 

=={{header|Perl}}==

 

=={{header|Phix}}==

 

=={{header|PicoLisp}}==

(until (step1) # ('step1', because 'step' is a system function)

 

=={{header|PureBasic}}==

Iterative version using one variable.

Protected i

Repeat: If _step(): i + 1: Else: i - 1: EndIf: Until i = 1

Recursive version. Stack may overflow as probability of a fall approaches or exceeds 50%.

While Not _step()

step_up()

Wend

Demonstration program.

 

Procedure _step()

Input()

CloseConsole()

Sample output:

<pre>Begin at level: 0

 

=== Iterative ===

deficit = 1

while deficit > 0:

deficit -= 1

else:

 

=== Recursive ===

''p'' approaches 0.5.

 

"No numbers."

while not step():

 

=={{header|R}}==

The step() function described would not be idiomatic R, since it would

require using the global assignment operator to get the side effect.

success <- runif(1) > p

## Requires that the "robot" is a variable named "level"

level <<- level - 1 + (2 * success)

success

 

===Recursive Solution===

 

while(! step()) {

stepUp()

}

 

===Iterative Solution===

 

i <- 0

while ( ! i) {

i <- i - 1 + (2 * step())

}

 

Example output:

 

=={{header|Racket}}==

(define p 0.5001)

(define (step)

(else (step-up (add1 n)))))

 

 

=={{header|REBOL}}==

Title: "Stair Climber"

URL: http://rosettacode.org/wiki/Stair_Climbing

]

step_upt: does [if not step [step_upt step_upt]]

 

 

Output:

 

=={{header|REXX}}==

 

 

=={{header|Ruby}}==

start_position = $position

step until ($position == start_position + 1)

 

$position = 0

Sample run:

<pre>$ ruby -d stair.climbing.rb

"rise (0)"

"rise (1)"</pre>

 

=={{header|SAS}}==

 

%macro step();

%sysfunc(round(%sysfunc(ranuni(0))))

%mend step;

 

%macro step_up();

 

 

%step_up;

 

Sample Output:

Simple recursive solution:

 

 

Non-recursive solution which almost gets away with not having named variables:

 

def rec: List[Boolean] => Boolean = step :: (_: List[Boolean]) match {

case true :: Nil => true

}

rec(Nil)

 

=={{header|Scheme}}==

(cond ((zero? n-steps) 'done)

((step) (step-up (- n-steps 1)))

 

=={{header|Seed7}}==

begin

while not doStep do

step_up;

end while;

 

=={{header|Sidef}}==

while (!step()) {

step_up();

}

 

=={{header|Smalltalk}}==

 

The following uses a block closure and the recursive solution which consumes stack until successful.

 

=={{header|Standard ML}}==

(*

* val step : unit -> bool

*)

fun step_up() = step() orelse (step_up() andalso step_up())

 

=={{header|Swift}}==

while !step() {

step_up()

}

 

The following uses a variable and is a bit longer, but avoids a possible stack overflow:

for var i = 0; i < 1; step()? ++i : --i { }

 

=={{header|Tcl}}==

The setup (note that <code>level</code> and <code>steps</code> are not used elsewhere, but are great for testing…)

set prob 0.5001

proc step {} {

return 0

}

===Iterative Solution===

All iterative solutions require a counter variable, but at least we can avoid any literal digits...

for {incr d} {$d} {incr d} {

incr d [set s -[step]]; incr d $s

}

===Recursive Solution===

This is the simplest possible recursive solution:

while {![step]} step-up-rec

 

=={{header|TI-83 BASIC}}==

 

<code>prgmSTEP</code>:

0→C

Disp "FALL"

End

If B=1

 

<code>prgmSTEPUP</code>:

While C=0

prgmSTEPUP

prgmSTEP

 

=={{header|XPL0}}==

int I;

[I:= 0;

 

proc Step_up; \Recursive version

 

=={{header|zkl}}==

 

This version consumes stack space proportional to the number of steps it needs to go up, as opposed to the number of steps it attempts. This is a substantial difference if the probability of success is only somewhat greater than or equal to 1/2.

You could also use "stepUp" instead of self.fcn, self.fcn seems a little clearer and makes it easier to refactor.