Problem Statement

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? Here's a pseudo-code of a simple recursive solution without using variables: Inductive proof that step_up() steps up one step, if it terminates:

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

Let's start with the solution:

REBOL [
    Title: "Stair Climber"
    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!"