Stair-climbing puzzle: Difference between revisions
Realize in F#
Drkameleon (talk | contribs) (Added Arturo implementation) |
(Realize in F#) |
||
(6 intermediate revisions by 4 users not shown) | |||
Line 35:
=== Iterative ===
<
V deficit = 1
L deficit > 0
Line 41:
deficit--
E
deficit++</
=== Recursive ===
<
L !step()
step_up2()</
=={{header|ActionScript}}==
===Iterative===
<
{
var i:int = 0;
Line 56:
if(step())i++;
else i--;
}</
===Recursive===
<
{
if(!step())
Line 65:
stepUp();
}
}</
=={{header|Ada}}==
<
begin
while not Step loop
Step_Up;
end loop;
end Step_Up;</
The following is a test program simulating Step:
<
with Ada.Text_IO;
Line 106:
Reset (Dice);
Step_Up;
end Scaffolding;</
Sample output:
<pre>
Line 122:
=={{header|Aime}}==
{{trans|C}}
<
{
while (!step()) {
step_up();
}
}</
=={{header|ALGOL 68}}==
Line 137:
{{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
END # step up #;</
PROC scaffolding = VOID:
BEGIN
Line 170:
END # scaffolding #;
scaffolding</
Sample output:
<pre>
Line 182:
=={{header|Arturo}}==
<
stepUp: function [].export:[Position][
Line 203:
]
stepUp</
{{out}}
Line 219:
=={{header|AutoHotkey}}==
Recursive solution:
<
{
While !step()
step_up()
}</
=={{header|AWK}}==
<syntaxhighlight lang="awk">
function step_up() {
while (!step()) { step_up() }
}
</syntaxhighlight>
=={{header|BASIC}}==
Line 238:
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
END SUB</
See also: [[#BBC BASIC|BBC BASIC]], [[#Liberty BASIC|Liberty BASIC]], [[#PureBasic|PureBasic]], [[#TI-83 BASIC|TI-83 BASIC]]
Line 246:
=={{header|BBC BASIC}}==
Recursive solution:
<
IF NOT FNstep PROCstepup : PROCstepup
ENDPROC</
=={{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;
Line 270:
}
}
}</
=={{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))
Line 303:
(let [success (< (rand) prob)]
(swap! level (if success inc dec))
success) )</
=== 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."
Line 315:
(or (zero? deficit)
(recur (if (step) (dec deficit)
(inc deficit)))) ) )</
=== Recursive ===
Line 321:
''p'' approaches 0.5.
<
"Non-tail-recursive. No numbers."
[]
Line 328:
(step-up2) ;; try again
)
true))</
=={{header|Common Lisp}}==
<
(unless (step) (step-up) (step-up)))</
=={{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;
Line 371:
rand_seed(0, 0); // to make it somewhat repeatable
step_up;
}</
Sample output:
<pre>Fell down to -1
Line 384:
Climbed up to 0
Climbed up to 1</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
Recursive version using no variables other than the Boolean returned by "Step"
<syntaxhighlight lang="Delphi">
{Recursive version}
procedure Step_Up;
begin
while not Step do Step_Up;
end;
</syntaxhighlight>
Iterative versions using one variable.
<syntaxhighlight lang="Delphi">
{Iterative version}
procedure Step_Up;
var I: integer;
begin
while I<1 do
if Step then Inc(I) else Dec(I);
end;
</syntaxhighlight>
Functional example program
<syntaxhighlight lang="Delphi">
var Position: integer;
function Step(Memo: TMemo): boolean;
begin
Result:=Random(2)=1;
if Result then Inc(Position)
else Dec(Position);
If Result then Memo.Lines.Add(Format('Climbed up to %d', [Position]))
else Memo.Lines.Add(Format('Fell down to %d', [Position]));
end;
procedure StepUp(Memo: TMemo);
begin
while not Step(Memo) do StepUp(Memo);
end;
procedure ShowStairClimb(Memo: TMemo);
begin
Position:=0;
Randomize;
StepUp(Memo);
end;
</syntaxhighlight>
{{out}}
<pre>
Fell down to -1
Climbed up to 0
Fell down to -1
Climbed up to 0
Climbed up to 1
Elapsed Time: 4.600 ms.
</pre>
=={{header|E}}==
Line 391 ⟶ 462:
The problem framework:
<
var prob := 0.5001
Line 398 ⟶ 469:
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.
Line 441 ⟶ 512:
}
return loop(1)
}</
=={{header|EchoLisp}}==
<
(define (step-up) (while (not (step)) (step-up)))
;; checking this is tail-recusive :
Line 466 ⟶ 537:
(climb stairs)
(writeln 'stairs stairs 'probability success 'steps STEPS)))
</syntaxhighlight>
{{out}}
Line 496 ⟶ 567:
=={{header|Elixir}}==
{{trans|Erlang}}
<
defp step, do: 1 == :rand.uniform(2)
Line 508 ⟶ 579:
end
IO.inspect Stair_climbing.step_up</
=={{header|Erlang}}==
<
-module(stair).
-compile(export_all).
Line 526 ⟶ 597:
step_up() ->
step_up(step()).
</syntaxhighlight>
=={{header|Euphoria}}==
<
if not step() then
step_up()
step_up()
end if
end procedure</
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
let rec step_up() = while not(step()) do step_up()
</syntaxhighlight>
=={{header|Factor}}==
<
=={{header|Forth}}==
Recursive. May exceed return stack unless compiler optimizes tail calls.
<
Counting. Avoids using a named variable.
<
=={{header|Fortran}}==
Line 549 ⟶ 624:
{{works with|Fortran|90 and later}}
<
implicit none
Line 576 ⟶ 651:
end subroutine step_up_iter
end module StairRobot</
=={{header|FreeBASIC}}==
Line 582 ⟶ 657:
Iterative version using one variable.
<
Dim As Integer i
Do
Line 591 ⟶ 666:
End If
Loop Until i = 1
End Sub</
Recursive version.
<
While Not step_()
step_up()
Wend
End Sub</
Demonstration program.
<
If Int((Rnd * 2)) Then
Print "Robot sube"
Line 619 ⟶ 694:
step_up
Sleep</
=={{header|Go}}==
38 bytes, no variables, no numbers.
<
=={{header|Groovy}}==
<syntaxhighlight lang="grovy">
class Stair_climbing{
static void main(String[] args){
Line 638 ⟶ 713:
}
</syntaxhighlight>
=={{header|Haskell}}==
Line 644 ⟶ 719:
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
Line 650 ⟶ 725:
untilM test action = do
result <- test
if result then return () else action >> untilM test action</
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)
Line 672 ⟶ 747:
putStrLn $ "The robot is at step #" ++ show startingPos ++ "."
let (endingPos, _) = execState stepUp (startingPos, g)
putStrLn $ "The robot is at step #" ++ show endingPos ++ "."</
=={{header|Icon}} and {{header|Unicon}}==
Line 681 ⟶ 756:
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())
end</
You can subtract a few more characters (and multiply the difficulty
of understanding) with:
<
(|not step(), step_up())
end</
=={{header|J}}==
'''Solution (Tacit):'''
<
attemptClimb =: [: <:`>:@.step 0:
isNotUpOne =: -.@(+/@])
step_up=: (] , attemptClimb)^: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.
Line 703 ⟶ 778:
'''Solution (Explicit):'''
<
while. -. +/y do. y=. y , _1 1 {~ step 0 end.
)
Line 709 ⟶ 784:
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
_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</
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
4 5</
=={{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}}==
Line 747 ⟶ 822:
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:
<syntaxhighlight lang
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
| if . >= ($r|length) then true else ($r[.] == 1) end ;</
We can now define step_up:
<
if step then tick
else tick | step_up | step_up
end;</
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:
<syntaxhighlight lang
{{out}}
<
11</
===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
Line 777 ⟶ 852:
if $time|step then $goal - 1 else $goal + 1 end
| [ ($time|tick), .] | tco_step_up
end ;</
The simulation can then be started as follows:
<syntaxhighlight lang
=={{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
</syntaxhighlight>
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()
</syntaxhighlight>
{{output}}
<pre>
Line 807 ⟶ 882:
=={{header|Kotlin}}==
{{trans|D}}
<
import java.util.Random
Line 829 ⟶ 904:
fun main(args: Array<String>) {
stepUp()
}</
{{out}}
Line 845 ⟶ 920:
=={{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
Line 865 ⟶ 940:
Print "Robot fell down"
End If
End Function</
=={{header|Logo}}==
Recursive.
<
if not step [step.up step.up]
end</
Constant space (fully tail-recursive).
<
if :n=0 [stop]
(step.up ifelse step [:n-1] [:n+1])
end</
=={{header|Lua}}==
<syntaxhighlight lang="lua">
function step_up()
while not step() do step_up() end
end
</syntaxhighlight>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
=={{header|MATLAB}}==
<
while ~step()
step_up();
end</
=={{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
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
Line 926 ⟶ 1,001:
end
end
</syntaxhighlight>
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;
end;</
=={{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)
(stepUp) ) )</
=={{header|PowerShell}}==
<
{
If ( -not ( Step ) )
Line 983 ⟶ 1,058:
# Test
$VerbosePreference = 'Continue'
StepUp</
{{out}}
<pre>VERBOSE: Fell one step
Line 999 ⟶ 1,074:
=={{header|Prolog}}==
The robot code is very short
<
The test program keeps track of the level in a dynamic predicate.
<
setup :-
Line 1,019 ⟶ 1,094:
retractall(level(Level)),
assert(level(NewLevel)),
N > 0. % Fail if 0 because that is a non step up.</
{{out}}
<pre>
Line 1,043 ⟶ 1,118:
=={{header|PureBasic}}==
Iterative version using one variable.
<
Protected i
Repeat: If _step(): i + 1: Else: i - 1: EndIf: Until i = 1
EndProcedure</
Recursive version. Stack may overflow as probability of a fall approaches or exceeds 50%.
<
While Not _step()
step_up()
Wend
EndProcedure</
Demonstration program.
<
Procedure _step()
Line 1,083 ⟶ 1,158:
Input()
CloseConsole()
EndIf</
Sample output:
<pre>Begin at level: 0
Line 1,096 ⟶ 1,171:
=== Iterative ===
<
"""Straightforward implementation: keep track of how many level we
need to ascend, and stop when this count is zero."""
Line 1,104 ⟶ 1,179:
deficit -= 1
else:
deficit += 1</
=== Recursive ===
Line 1,110 ⟶ 1,185:
''p'' approaches 0.5.
<
"No numbers."
while not step():
step_up2() # undo the fall</
=={{header|Quackery}}==
<
=={{header|R}}==
Line 1,123 ⟶ 1,198:
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:
Line 1,162 ⟶ 1,237:
=={{header|Racket}}==
<
(define p 0.5001)
(define (step)
Line 1,172 ⟶ 1,247:
(else (step-up (add1 n)))))
(step-up 1)</
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
=={{header|REBOL}}==
<
Title: "Stair Climber"
URL: http://rosettacode.org/wiki/Stair_Climbing
Line 1,217 ⟶ 1,292:
step_upt: does [if not step [step_upt step_upt]]
step_upt print "Success!"</
Output:
Line 1,232 ⟶ 1,307:
=={{header|REXX}}==
<
end
return</
=={{header|Ring}}==
<
stepup()
Line 1,249 ⟶ 1,324:
func stp
return 0
</syntaxhighlight>
=={{header|Ruby}}==
<
start_position = $position
step until ($position == start_position + 1)
Line 1,273 ⟶ 1,348:
$position = 0
step_up</
Sample run:
<pre>$ ruby -d stair.climbing.rb
Line 1,287 ⟶ 1,362:
=={{header|Run BASIC}}==
<
result = stepUp()
Line 1,300 ⟶ 1,375:
print "Robot stepped "+word$("up down",stepp+1)
End Function
</syntaxhighlight>
=={{header|Rust}}==
<
while !step() {
step_up();
}
}</
=={{header|SAS}}==
<syntaxhighlight lang="sas">
%macro step();
%sysfunc(round(%sysfunc(ranuni(0))))
%mend step;
</syntaxhighlight>
===Recursive===
<syntaxhighlight lang="sas">
%macro step_up();
Line 1,331 ⟶ 1,406:
%step_up;
</syntaxhighlight>
===Iterative===
<syntaxhighlight lang="sas">
%macro step_up();
Line 1,344 ⟶ 1,419:
%mend step_up;
</syntaxhighlight>
Line 1,366 ⟶ 1,441:
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
Line 1,377 ⟶ 1,452:
}
rec(Nil)
}</
=={{header|Scheme}}==
<
(cond ((zero? n-steps) 'done)
((step) (step-up (- n-steps 1)))
(else (step-up (+ n-steps 1)))))</
=={{header|Seed7}}==
<
begin
while not doStep do
step_up;
end while;
end func;</
=={{header|Sidef}}==
<
while (!step()) {
step_up();
}
}</
=={{header|Smalltalk}}==
Line 1,404 ⟶ 1,479:
The following uses a block closure and the recursive solution which consumes stack until successful.
<
stepUp := [ [ step value ] whileFalse: [ stepUp value ] ].</
=={{header|Standard ML}}==
<syntaxhighlight lang="sml">
(*
* val step : unit -> bool
Line 1,419 ⟶ 1,495:
*)
fun step_up() = step() orelse (step_up() andalso step_up())
</syntaxhighlight>
Alternate version:
<syntaxhighlight lang="sml">fun step() = true
fun step_up() = while step() = false do step_up()
</syntaxhighlight>
=={{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 {} {
Line 1,447 ⟶ 1,529:
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}}==
Line 1,465 ⟶ 1,547:
<code>prgmSTEP</code>:
<
0→C
Disp "FALL"
Line 1,481 ⟶ 1,563:
End
If B=1
Pause</
<code>prgmSTEPUP</code>:
<
While C=0
prgmSTEPUP
prgmSTEP
End</
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Conv
var rand = Random.new(1268) // generates short repeatable sequence
Line 1,516 ⟶ 1,598:
}
stepUp.call()</
{{out}}
Line 1,530 ⟶ 1,612:
=={{header|XPL0}}==
<
int I;
[I:= 0;
Line 1,539 ⟶ 1,621:
proc Step_up; \Recursive version
while not Step do Step_up;</
=={{header|zkl}}==
Line 1,545 ⟶ 1,627:
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.
<
fcn stepUp{ while(not step()){ self.fcn() } }</
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
Line 1,558 ⟶ 1,640:
r
}
stepUp();</
{{out}}
<pre>
|