Re: The "Strand" puzzle --- ( Continued Fractions using Lisp orPython? )

B. Pym wrote:

B. Pym wrote:
 

e.g. -------- For the (street)  Numbers (1,2,3,4,5,6,7,8)
 
       (1,2,3,4,5)  and  (7,8)  both add up to 15.
 
 
 
"In a given street of houses with consecutive numbers between
50 and 500, find the house number, for which, the sum of
numbers on the left is equal to the sum of numbers on the
right"

 
Gauche Scheme
 
(define (strand lst)
  (let go ((left-sum 0) (tail lst))
    (if (null? tail)
      #f
      (let ((right-sum (fold + 0 (cdr tail))))
        (cond ((< left-sum right-sum)
               (go (+ left-sum (car tail)) (cdr tail)))
              ((= left-sum right-sum) (car tail))
              (#t #f))))))
 
(strand '(1 2 3 4 5 6 7 8))
  ===>
6
 
(lrange 2 5)
  ===>
(2 3 4)
 
(any
  (lambda (n)
    (if (strand (lrange 50 n))
      n
      #f))
  (lrange 500 50 -1))
  ===>
352
 
(strand (lrange 50 352))
 ===>
251

 
 
Faster:
 
(define (strand lst)
  (let go ((left-sum 0) (right-sum (fold + 0 (cdr lst))) (tail lst))
    (cond ((< left-sum right-sum)
           (go (+ left-sum (car tail))
               (- right-sum (cadr tail))
               (cdr tail)))
          ((= left-sum right-sum) (car tail))
        

Using "do":

(define (strand lst)
  (do ((tail lst (cdr tail))
       (left-sum 0 (+ left-sum (car tail)))
       (right-sum (fold + 0 (cdr lst)) (- right-sum (cadr tail))))
    ((>= left-sum right-sum)
     (if (= left-sum right-sum) (car tail) #f))))