Friday, August 21, 2009

A small puzzle

I got this from Marshall Spight today.
(define (f a b)
  (if (zero? b)
      a
      (f (logxor a b)
         (* (logand a b) 2))))

Q: F is better known as ______ ?

You may need these auxiliary functions.

(define (logand a b)
  (cond ((zero? a) 0)
        ((zero? b) 0)
        (else
         (+ (* (logand (floor (/ a 2)) (floor (/ b 2))) 2)
            (if (or (even? a)
                    (even? b))
                0
                1)))))

(define (logxor a b)
  (cond ((zero? a) b)
        ((zero? b) a)
        (else 
         (+ (* (logxor (floor (/ a 2)) (floor (/ b 2))) 2)
            (if (even? a)
                (if (even? b) 0 1)
                (if (even? b) 1 0))))))

And please don't just post a spoiler. If you just want ‘first credit’, email me directly.

What's amusing to me is that it isn't obvious if F even terminates.
Post a Comment