Stair-climbing puzzle: Difference between revisions

=== Iterative ===

V deficit = 1

L deficit > 0

deficit--

E

=== Recursive ===

L !step()

=={{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>

=={{header|Arturo}}==

stepUp: function [].export:[Position][

]

{{out}}

=={{header|AutoHotkey}}==

Recursive solution:

{

While !step()

step_up()

=={{header|AWK}}==

function step_up() {

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 sharp|C#}}==

while (!step()) step_up();

=={{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

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}}

=={{header|Elixir}}==

{{trans|Erlang}}

defp step, do: 1 == :rand.uniform(2)

end

=={{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|Factor}}==

=={{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|FreeBASIC}}==

Iterative version using one variable.

Dim As Integer i

Do

End If

Loop Until i = 1

Recursive version.

While Not step_()

step_up()

Wend

Demonstration program.

If Int((Rnd * 2)) Then

Print "Robot sube"

step_up

=={{header|Go}}==

38 bytes, no variables, no numbers.

=={{header|Groovy}}==

class Stair_climbing{

static void main(String[] args){

}

=={{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|Julia}}==

As specified, shorter and fewer numbers preferred. It may be supposed that the robot would reach the bottom of any steps well before blowing the stack to reboot.

step_up() = while !step() step_up() end

Here is an example to test the code with a step that has a 1/3 failure rate:

step() = (b = rand([true,true,false]); println(b); b)

step_up()

{{output}}

<pre>

=={{header|Kotlin}}==

{{trans|D}}

import java.util.Random

fun main(args: Array<String>) {

stepUp()

{{out}}

=={{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|Mathematica}}/{{header|Wolfram Language}}==

=={{header|MATLAB}}==

while ~step()

step_up();

=={{header|Nim}}==

One liner (yes it is possible in 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}}==

<span style="color: #008080;">procedure</span> <span style="color: #000000;">step_up</span><span style="color: #0000FF;">()</span>

<span style="color: #008080;">while</span> <span style="color: #008080;">not</span> <span style="color: #000000;">step</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">do</span> <span style="color: #000000;">step_up</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>

=={{header|PicoLisp}}==

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

=={{header|PowerShell}}==

{

If ( -not ( Step ) )

# Test

$VerbosePreference = 'Continue'

{{out}}

<pre>VERBOSE: Fell one step

=={{header|Prolog}}==

The robot code is very short

The test program keeps track of the level in a dynamic predicate.

setup :-

retractall(level(Level)),

assert(level(NewLevel)),

{{out}}

<pre>

=={{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 ===

"""Straightforward implementation: keep track of how many level we

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

deficit -= 1

else:

=== Recursive ===

''p'' approaches 0.5.

"No numbers."

while not step():

=={{header|Quackery}}==

=={{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|Raku}}==

(formerly Perl 6)

=={{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}}==

end

=={{header|Ring}}==

stepup()

func stp

return 0

=={{header|Ruby}}==

start_position = $position

step until ($position == start_position + 1)

$position = 0

Sample run:

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

=={{header|Run BASIC}}==

result = stepUp()

print "Robot stepped "+word$("up down",stepp+1)

End Function

=={{header|Rust}}==

while !step() {

step_up();

}

=={{header|SAS}}==

%macro step();

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

%mend step;

===Recursive===

%macro step_up();

%step_up;

===Iterative===

%macro step_up();

%mend step_up;

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|Wren}}==

{{trans|Kotlin}}

{{libheader|Wren-fmt}}

import "/fmt" for Conv

}

{{out}}

=={{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.

An example step function:

{{trans|D}}

fcn step(){ //-->0|1

r:=(0).random(2); // 0 or 1

r

}

{{out}}

<pre>