Stair-climbing puzzle
From Rosetta Code
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 [from the initial position] (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?
[edit] ActionScript
[edit] Iterative
function stepUp()
{
var i:int = 0;
while(i < 1)
if(step())i++;
else i--;
}
[edit] Recursive
function stepUp()
{
if(!step())
{
stepUp();
stepUp();
}
}
[edit] Ada
procedure Step_Up is
begin
while not Step loop
Step_Up;
end loop;
end Step_Up;
The following is a test program simulating Step:
with Ada.Numerics.Discrete_Random;
with Ada.Text_IO;
procedure Scaffolding is
package Try is new Ada.Numerics.Discrete_Random (Boolean);
use Try;
Dice : Generator;
Level : Integer := 0;
function Step return Boolean is
begin
if Random (Dice) then
Level := Level + 1;
Ada.Text_IO.Put_Line ("Climbed up to" & Integer'Image (Level));
return True;
else
Level := Level - 1;
Ada.Text_IO.Put_Line ("Fell down to" & Integer'Image (Level));
return False;
end if;
end Step;
procedure Step_Up is
begin
while not Step loop
Step_Up;
end loop;
end Step_Up;
begin
Reset (Dice);
Step_Up;
end Scaffolding;
Sample output:
Fell down to-1 Climbed up to 0 Fell down to-1 Climbed up to 0 Fell down to-1 Fell down to-2 Climbed up to-1 Climbed up to 0 Climbed up to 1
[edit] ALGOL 68
Translation of: Ada
Works with: ALGOL 68 version Standard - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386
PROC step up = VOID:The following is a test program simulating step:
BEGIN
WHILE NOT step DO
step up
OD
END # step up #;
PROC scaffolding = VOID:
BEGIN
INT level := 0;
PROC step = BOOL:
BEGIN
IF random > 0.5 THEN
level +:= 1;
print(("Climbed up to",level, new line));
TRUE
ELSE
level -:= 1;
print(("Fell down to",level, new line));
FALSE
FI
END # step #;
PROC step up = VOID:
BEGIN
WHILE NOT step DO
step up
OD
END # step up #;
step up
END # scaffolding #;
scaffolding
Sample output:
Fell down to -1 Fell down to -2 Climbed up to -1 Climbed up to +0 Climbed up to +1
[edit] AutoHotkey
Recursive solution:
step_up()
{
While !step()
step_up()
}
[edit] C
void step_up(void)
{
while (!step()) {
step_up();
}
}
The following uses a variable and is a bit longer, but avoids a possible stack overflow:
void step_up(void)
{
int i = 0;
while (i < 1) {
if (step()) {
++i;
} else {
--i;
}
}
}
[edit] C++
void step_up()
{
while (!step()) step_up();
}
The following uses a variable and is a bit longer, but avoids a possible stack overflow:
void step_up()
{
for (int i = 0; i < 1; step()? ++i : --i);
}
[edit] C#
void step_up() {
for (; step() == false; )step_up();
}
[edit] 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) )
[edit] Tail-recursive
The internal recursion uses a counter; see the function documentation.
(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)))) ) )
[edit] Recursive
This satisfies Chung-chieh's challenge to avoid using numbers. Might blow the stack as p approaches 0.5.
(defn step-up2
"Non-tail-recursive. No numbers."
[]
(if (not (step))
(do (step-up2) ;; undo the fall
(step-up2) ;; try again
)
true))
[edit] Common Lisp
(defun step-up ()
(unless (step) (step-up) (step-up)))
[edit] D
The recursive version (note that "step_up" is equivalent to "step_up()" in D):
void step_up()
{
while(!step)
step_up;
}
The non-recursive version, using 1 variable:
void step_up_nr()
{
for(uint i = 0; i < 1; step ? ++i : --i) {};
}
Test program:
import std.stdio;
import std.random;
int position;
bool step()
{
bool r = rand() > (uint.max / 2);
if(r)
writefln("Climbed up to %d", ++position);
else
writefln("Fell down to %d", --position);
return r;
}
void step_up()
{
while(!step)
step_up;
}
void main()
{
rand_seed(0, 0); // to make it somewhat repeatable
step_up;
}
Sample output:
Fell down to -1 Fell down to -2 Fell down to -3 Fell down to -4 Climbed up to -3 Fell down to -4 Climbed up to -3 Climbed up to -2 Climbed up to -1 Climbed up to 0 Climbed up to 1
[edit] E
This is at first a very direct Translation of: Clojure
The problem framework:
var level := 41
var prob := 0.5001
def step() {
def success := entropy.nextDouble() < prob
level += success.pick(1, -1)
return success
}
Counting solution:
def stepUpCounting() {
var deficit := 1
while (deficit > 0) {
deficit += step().pick(-1, 1)
}
}
Ordinary recursive solution:
def stepUpRecur() {
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.
def stepUpEventualRecur() {
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):
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)
}
[edit] Forth
Recursive. May exceed return stack unless compiler optimizes tail calls.
: step-up begin step 0= while recurse repeat ;
Counting. Avoids using a named variable.
: step-up -1 begin step if 1+ else 1- then ?dup 0= until ;
[edit] Fortran
Translation of: C++
Works with: Fortran version 90 and later
module StairRobot
implicit none
contains
logical function step()
! try to climb up and return true or false
step = .true. ! to avoid compiler warning
end function step
recursive subroutine step_up_rec
do while ( .not. step() )
call step_up_rec
end do
end subroutine step_up_rec
subroutine step_up_iter
integer :: i = 0
do while ( i < 1 )
if ( step() ) then
i = i + 1
else
i = i - 1
end if
end do
end subroutine step_up_iter
end module StairRobot
[edit] 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:
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
Here's an example implementation of Robot and step, as well as a main with which to test stepUp.
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 ++ "."
[edit] J
Solution (Tacit):
step =: 0.6 > ?@0:
attemptClimb =: [: <:`>:@.step 0:
isNotUpOne =: -.@(+/@])
step_up=: (] , attemptClimb)^:isNotUpOne^:_
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. J programmers use verbs which ignore their arguments (e.g. step and attemptClimb) to replace verbs which do not take an argument.
Solution (Explicit):
step_upX=: monad define NB. iterative
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:
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
Another approach might be:
keepTrying=: (, {: - _1 ^ step)^:({. >: {:)^:_
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:
keepTrying 2
2 1 0 1 2 3
keepTrying 3
3 2 3 2 3 2 3 4
keepTrying 4
4 5
[edit] Java
Translation of: C++
public void stepUp() {
while (!step()) stepUp();
}
The following uses a variable and is a bit longer, but avoids a possible stack overflow:
public void stepUp(){
for (int i = 0; i < 1; step() ? ++i : --i);
}
[edit] Logo
Recursive.
to step.up
if not step [step.up step.up]
end
Constant space (fully tail-recursive).
to step.up [:n 1]
if :n=0 [stop]
(step.up ifelse step [:n-1] [:n+1])
end
[edit] Lua
function step_up()
while !step() do step_up() end
end
</lua>
=={{header|Mathematica}}==
<lang Mathematica>StepUp[] := If[!Step[], StepUp[]; StepUp[]]
[edit] MATLAB
function step_up()
while ~step()
step_up();
end
[edit] OCaml
let rec step_up() =
while not(step()) do
step_up()
done
;;
[edit] Oz
Recursive solution:
proc {StepUp}
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 StepUp is not in tail position.
Iterative solution:
proc {StepUp}
Level = {NewCell 0}
in
for until:@Level == 1 do
if {Step} then Level := @Level + 1
else Level := @Level - 1
end
end
end
Oz has arbitrary large integers. So if the robot is very unlucky, the contents of the Level 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.
[edit] Perl
sub step_up { step_up until step; }
[edit] Perl 6
sub step_up { step_up until step; }
[edit] PicoLisp
(de stepUp ()
(until (step1) # ('step1', because 'step' is a system function)
(stepUp) ) )
[edit] PureBasic
Iterative version using one variable.
Procedure step_up()
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%.
Procedure step_up()
While Not _step()
step_up()
Wend
EndProcedure
Demonstration program.
Global level
Procedure _step()
If Random(1) ;equal chance of stepping up or falling down
level + 1
PrintN("Climbed up to " + Str(level))
ProcedureReturn #True
Else
level - 1
PrintN("Fell down to " + Str(level))
ProcedureReturn #False
EndIf
EndProcedure
;recursive
Procedure step_up()
While Not _step()
step_up()
Wend
EndProcedure
If OpenConsole()
PrintN("Begin at level: " + Str(level))
step_up()
PrintN("*** Now at level: " + Str(level))
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
Input()
CloseConsole()
EndIf
Sample output:
Begin at level: 0 Fell down to -1 Climbed up to 0 Fell down to -1 Climbed up to 0 Climbed up to 1 *** Now at level: 1
[edit] Python
[edit] Iterative
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
[edit] Recursive
This satisfies Chung-chieh's challenge to avoid using numbers. Might blow the stack as p approaches 0.5.
def step_up2():
"No numbers."
while not step():
step_up2() # undo the fall
[edit] R
The step() function described would not be idiomatic R, since it would require using the global assignment operator to get the side effect.
step <- function() {
success <- runif(1) > p
## Requires that the "robot" is a variable named "level"
level <<- level - 1 + (2 * success)
success
}
[edit] Recursive Solution
stepUp <- function() {
while(! step()) {
stepUp()
}
}
[edit] Iterative Solution
stepUpIter <- function() {
i <- 0
while ( ! i) {
i <- i - 1 + (2 * step())
}
}
Example output:
> p <- 0.25 > level <- 1 > print(level) [1] 1 > stepUp() > print(level) [1] 2 > stepUpIter() > print(level) [1] 3
[edit] REBOL
rebol [
Title: "Stair Climber"
Date: 2009-12-14
Author: oofoe
URL: http://rosettacode.org/wiki/Stair_Climbing
]
random/seed now
step: does [random/only reduce [yes no]]
; Iterative solution with symbol stack. No numbers, draws a nifty
; diagram of number of steps to go. This is intended more to
; demonstrate a correct solution:
step_up: func [/steps s] [
either not steps [
print "Starting up..."
step_up/steps copy [|]
][
while [not empty? s][
print [" Steps left:" s]
either step [remove s][append s '|]
]
]
]
step_up print ["Success!" crlf]
; Recursive solution. No numbers, no variables. "R" means a recover
; step, "+" means a step up.
step_upr: does [if not step [prin "R " step_upr prin "+ " step_upr]]
step_upr print ["Success!" crlf]
; Small recursive solution, no monitoring:
step_upt: does [if not step [step_upt step_upt]]
step_upt print "Success!"
Output:
Starting up...
Steps left: |
Steps left: | |
Steps left: |
Success!
R R + R R R R R R R + + R + + + + + + R + R R + R + R + R + + + Success!
Success!
[edit] Ruby
def step_up
start_position = $position
step until ($position == start_position + 1)
end
# assumptions about the step function:
# - it maintains the current position of the robot "as a side effect"
# - the robot is equally likely to step back as to step up
def step
if rand < 0.5
$position -= 1
p "fall (#$position)" if $DEBUG
return false
else
$position += 1
p "rise (#$position)" if $DEBUG
return true
end
end
$position = 0
step_up
Sample run:
$ ruby -d stair.climbing.rb "fall (-1)" "rise (0)" "fall (-1)" "rise (0)" "fall (-1)" "fall (-2)" "rise (-1)" "rise (0)" "rise (1)"
[edit] Scala
Simple recursive solution:
def stepUp { while (! step) stepUp }
Non-recursive solution which almost gets away with not having named variables:
def stepUp {
def rec: List[Boolean] => Boolean = step :: (_: List[Boolean]) match {
case true :: Nil => true
case true :: false :: rest => rec(rest)
case other => rec(other)
}
rec(Nil)
}
[edit] Scheme
(define (step-up n-steps)
(cond ((zero? n-steps) 'done)
((step) (step-up (- n-steps 1)))
(else (step-up (+ n-steps 1)))))
[edit] Smalltalk
Works with: GNU Smalltalk
The following uses a block closure and the recursive solution which consumes stack until successful.
Smalltalk at: #stepUp put: 0.
stepUp := [ [ step value ] whileFalse: [ stepUp value ] ].
[edit] Tcl
The setup (note that level and steps are not used elsewhere, but are great for testing…)
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
}
}
[edit] Iterative Solution
All iterative solutions require a counter variable, but at least we can avoid any literal digits...
proc step-up-iter {} {
for {incr d} {$d} {incr d} {
incr d [set s -[step]]; incr d $s
}
}
[edit] Recursive Solution
This is the simplest possible recursive solution:
proc step-up-rec {} {
while {![step]} step-up-rec
}
[edit] TI-83 BASIC
TI-83 BASIC doesn't have functions (only subroutines), so a variable must be used as the return value for prgmSTEP. Set A to 1 before calling to display the offset from the stair it was called from (store in D). Set B to 1 to pause after each attempt. C is the return variable for prgmSTEP. D is the stair it is on (only used for display, and not used if A isn't 1).
prgmSTEP:
If rand>.5:Then
0→C
Disp "FALL"
If A=1:Then
D-1→D
Disp D
End
Else
1→C
Disp "CLIMB"
If A=1:Then
D+1→D
Disp D
End
End
If B=1
Pause
prgmSTEPUP:
prgmSTEP
While C=0
prgmSTEPUP
prgmSTEP
End
