Stair-climbing puzzle: Difference between revisions
Mathematica |
Added AHK |
||
Line 56: | Line 56: | ||
Climbed up to 1 |
Climbed up to 1 |
||
</pre> |
</pre> |
||
=={{header|AutoHotkey}}== |
|||
Recursive solution: |
|||
<lang AutoHotkey> |
|||
step_up() |
|||
{ |
|||
While !step() |
|||
stepup() |
|||
} |
|||
</lang> |
|||
=={{header|C}}== |
=={{header|C}}== |
Revision as of 02:22, 27 November 2009
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?
Ada
<lang Ada>procedure Step_Up is begin
while not Step loop Step_Up; end loop;
end Step_Up;</lang> The following is a test program simulating Step: <lang Ada>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;</lang> 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
AutoHotkey
Recursive solution: <lang AutoHotkey> step_up() {
While !step() stepup()
} </lang>
C
<lang c>void step_up(void) {
while (!step()) { step_up(); }
}</lang>
The following uses a variable and is a bit longer, but avoids a possible stack overflow: <lang c>void step_up(void) {
int i = 0;
while (i < 1) { if (step()) { ++i; } else { --i; } }
}</lang>
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>
C#
<lang csharp>void step_up() {
for (; step() == false; )step_up();
}</lang>
Clojure
First, some boilerplate.
<lang lisp>;; 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 lisp>(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 lisp>(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
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>
Forth
Recursive. May exceed return stack unless compiler optimizes tail calls. <lang forth>: step-up begin step 0= while recurse repeat ;</lang> Counting. Avoids using a named variable. <lang forth>: step-up -1 begin step if 1+ else 1- then ?dup 0= until ;</lang>
Fortran
<lang fortran>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</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 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.
)</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>
Java
<lang java>public void stepUp() {
while (!step()) stepUp();
}</lang> The following uses a variable and is a bit longer, but avoids a possible stack overflow: <lang java>public void stepUp(){
for (int i = 0; i < 1; step() ? ++i : --i);
}</lang>
Logo
Recursive. <lang logo>to step.up
if not step [step.up step.up]
end</lang> Constant space (fully tail-recursive). <lang logo>to step.up [:n 1]
if :n=0 [stop] (step.up ifelse step [:n-1] [:n+1])
end</lang>
Mathematica
<lang Mathematica>StepUp[] := If[!Step[], StepUp[]; StepUp[]]</lang>
OCaml
<lang ocaml>let rec step_up() =
while not(step()) do step_up() done
- </lang>
Perl
<lang perl>sub step_up { step_up until step; }</lang>
Perl 6
<lang perl6>sub step_up { step_up until step; }</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>
R
The step() function described would not be idiomatic R, since it would require using the global assignment operator to get the side effect. <lang R>step <- function() {
success <- runif(1) > p ## Requires that the "robot" is a variable named "level" level <<- level - 1 + (2 * success) success
}</lang>
Recursive Solution
<lang R>stepUp <- function() {
while(! step()) { stepUp() }
}</lang>
Iterative Solution
<lang R>stepUpIter <- function() {
i <- 0 while ( ! i) { i <- i - 1 + (2 * step()) }
}</lang>
Example output:
> p <- 0.25 > level <- 1 > print(level) [1] 1 > stepUp() > print(level) [1] 2 > stepUpIter() > print(level) [1] 3
Ruby
<lang 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</lang> 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)"
Smalltalk
The following uses a block closure and the recursive solution which consumes stack until successful. <lang smalltalk>Smalltalk at: #stepUp put: 0. stepUp := [ [ step value ] whileFalse: [ stepUp value ] ].</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>