News

muvee Reveal - the latest incarnation of muvee's flagship product - has just been released on 11 June 2008! The behaviours of the 8 bundled styles are specified using muSE, in addition to all the styles developed for the now discontinued muvee autoProducer 6.1.

Wednesday, August 15, 2007

The stair climbing robot

An interesting problem called "the stair climbing robot" was recently posted on 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 (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?

I thought I'll try to solve it using muSE's lcons lazy function. Here's a solution -

; A step function which fails 50% of the time.
(define (step)
(if (= 0 (rand 2))
(do (print "DOWN") ())
(do (print "UP") T)))

; Gets the second element of a list s,
; forcing the value of the first element if
; the list happens to be lazy.

(define (forced-next s) (first s) (first (rest s)))

; (steps) generates a sequence of
; successful upward steps. To climb N steps,
; just take N elements from (steps).

(define (steps)
(lcons (if (step)
T
(forced-next (rest (steps))))
(steps)))

; Climb 1 step
(take 1 (steps))

No comments: