here's my first scheme implementation.
Code:
(use-modules (ice-9 format))
(define num->chain
(lambda (num)
(if (< num 10)
(list num)
(cons (remainder num 10) (num->chain (quotient num 10))))))
(define reverse-chain
(lambda (c)
(define reverse-helper
(lambda (l-in l-out)
(if (null? l-in)
l-out
(reverse-helper (cdr l-in) (cons (car l-in) l-out)))))
(reverse-helper c '())))
(define empty-chain? null?)
(define chain->num
(lambda (chain)
(if (empty-chain? chain)
0
(+ (car chain) (* 10 (chain->num (cdr chain)))))))
(define is-palindrome?
(lambda (n)
(define same-chain?
(lambda (c1 c2)
(cond ((empty-chain? c1)
(if (empty-chain? c2)
#t
#f))
((empty-chain? c2)
(if (empty-chain? c1)
#t
#f))
((= (car c1) (car c2))
(same-chain? (cdr c1) (cdr c2)))
(else #f))))
(same-chain? n (reverse-chain n))))
(define find-lychrel-numbers
(lambda (limit max-tries)
(define iterate
(lambda (chain)
(num->chain (+ (chain->num chain) (chain->num (reverse-chain chain))))))
(define is-lychrel-number?
(lambda (chain try)
(cond ((> try max-tries)
#f)
((is-palindrome? chain)
(chain->num chain))
(else
(is-lychrel-number? (iterate chain) (+ try 1))))))
(define loop
(lambda (number)
(if (< number limit)
(let ((result (is-lychrel-number? (num->chain number) 0)))
(if (not result)
(format #t "~d is a candidate\n" number))
(loop (+ 1 number))))))
(loop 1)))
(find-lychrel-numbers 10000 40)
it works by storing the numbers in chains of digits and then reversing these chains and adding them. this saves the overhead of using int->string and string->int conversion.
in case anybody's interested, it takes this much time:
Code:
howlingmadhowie% time guile lychrel.scm 1>/dev/null
guile lychrel.scm > /dev/null 2,02s user 0,01s system 98% cpu 2,065 total
Bookmarks