[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/jUEoq05B    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Mar 20:
; two kaprekar exercises

(define (take n xs)
  (let loop ((n n) (xs xs) (ys '()))
    (if (or (zero? n) (null? xs))
        (reverse ys)
        (loop (- n 1) (cdr xs)
              (cons (car xs) ys)))))

(define (drop n xs)
  (let loop ((n n) (xs xs))
    (if (or (zero? n) (null? xs)) xs
      (loop (- n 1) (cdr xs)))))

(define (range . args)
  (case (length args)
    ((1) (range 0 (car args) (if (negative? (car args)) -1 1)))
    ((2) (range (car args) (cadr args) (if (< (car args) (cadr args)) 1 -1)))
    ((3) (let ((le? (if (negative? (caddr args)) >= <=)))
           (let loop ((x(car args)) (xs '()))
             (if (le? (cadr args) x)
                 (reverse xs)
                 (loop (+ x (caddr args)) (cons x xs))))))
    (else (error 'range "unrecognized arguments"))))

(define (filter pred? xs)
  (let loop ((xs xs) (ys '()))
    (cond ((null? xs) (reverse ys))
          ((pred? (car xs))
            (loop (cdr xs) (cons (car xs) ys)))
          (else (loop (cdr xs) ys)))))

(define sort #f)
(define merge #f)
(let ()
  (define dosort
    (lambda (pred? ls n)
      (if (= n 1)
          (list (car ls))
          (let ((i (quotient n 2)))
            (domerge pred?
                     (dosort pred? ls i)
                     (dosort pred? (list-tail ls i) (- n i)))))))
  (define domerge
    (lambda (pred? l1 l2)
      (cond
        ((null? l1) l2)
        ((null? l2) l1)
        ((pred? (car l2) (car l1))
         (cons (car l2) (domerge pred? l1 (cdr l2))))
        (else (cons (car l1) (domerge pred? (cdr l1) l2))))))
  (set! sort
    (lambda (pred? l)
      (if (null? l) l (dosort pred? l (length l)))))
  (set! merge
    (lambda (pred? l1 l2)
      (domerge pred? l1 l2))))

(define (digits n . args)
  (let ((b (if (null? args) 10 (car args))))
    (let loop ((n n) (d '()))
      (if (zero? n) d
          (loop (quotient n b)
                (cons (modulo n b) d))))))

(define (undigits ds . args)
  (let ((b (if (null? args) 10 (car args))))
    (let loop ((ds ds) (n 0))
      (if (null? ds) n
          (loop (cdr ds) (+ (* n b) (car ds)))))))

(define (normalize n)
  (let loop ((ds (digits n)))
    (if (= (length ds) 4) ds
      (loop (cons 0 ds)))))

(define (step n)
  (let* ((ds (normalize n))
         (big (undigits (sort > ds)))
         (little (undigits (sort < ds))))
    (- big little)))

(define (chain n)
  (let loop ((ns (list n)))
    (if (member (car ns) '(0 6174))
        (reverse ns)
        (loop (cons (step (car ns)) ns)))))

(display (chain 2011)) (newline)

(display (apply max (map length (map chain (range 1 10000))))) (newline)

(define (kaprekar? k)
  (let* ((n (length (digits k)))
         (k2 (* k k))
         (ds (reverse (digits k2)))
         (left (undigits (reverse (drop n ds))))
         (right (undigits (reverse (take n ds)))))
    (= (+ left right) k)))

(display (kaprekar? 703)) (newline)

(display (filter kaprekar? (range 1 1000))) (newline)


Output:
1
2
3
4
(2011 1998 8082 8532 6174)
8
#t
(1 9 45 55 99 297 703 999)


Create a new paste based on this one


Comments: