[ create a new paste ] login | about

Link: http://codepad.org/zW0EmC9m    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Jun 15:
; 3sum

(define-syntax fold-of
  (syntax-rules (range in is)
    ((_ "z" f b e) (set! b (f b e)))
    ((_ "z" f b e (v range fst pst stp) c ...)
      (let* ((x fst) (p pst) (s stp)
             (le? (if (positive? s) <= >=)))
        (do ((v x (+ v s))) ((le? p v) b)
          (fold-of "z" f b e c ...))))
    ((_ "z" f b e (v range fst pst) c ...)
      (let* ((x fst) (p pst) (s (if (< x p) 1 -1)))
        (fold-of "z" f b e (v range x p s) c ...)))
    ((_ "z" f b e (v range pst) c ...)
      (fold-of "z" f b e (v range 0 pst) c ...))
    ((_ "z" f b e (x in xs) c ...)
      (do ((t xs (cdr t))) ((null? t) b)
        (let ((x (car t)))
          (fold-of "z" f b e c ...))))
    ((_ "z" f b e (x is y) c ...)
      (let ((x y)) (fold-of "z" f b e c ...)))
    ((_ "z" f b e p? c ...)
      (if p? (fold-of "z" f b e c ...)))
    ((_ f i e c ...)
      (let ((b i)) (fold-of "z" f b e c ...)))))

(define-syntax list-of (syntax-rules ()
  ((_ arg ...) (reverse (fold-of
    (lambda (d a) (cons a d)) '() arg ...)))))

(define (make-set limit)

  (define (hash x) ; universal hash function
    (define (mod n) (modulo n 4294967296))
    (cond ((boolean? x) (if x 1 0))
          ((symbol? x) (hash (symbol->string x)))
          ((char? x) (char->integer x))
          ((integer? x) (mod x))
          ((real? x)
            (let* ((r (inexact->exact x))
                   (n (numerator r))
                   (d (denominator r)))
              (mod (+ n (* 37 d)))))
          ((rational? x) (mod (+ (numerator x) (* 37 (denominator x)))))
          ((complex? x)
            (mod (+ (hash (real-part x))
                    (* 37 (hash (imag-part x))))))
          ((null? x) 4294967295)
          ((pair? x)
            (let loop ((x x) (s 0))
              (if (null? x) s
                (loop (cdr x) (mod (+ (* 31 s) (hash (car x))))))))
          ((vector? x)
            (let loop ((i (- (vector-length x) 1)) (s 0))
              (if (negative? i) s
                  (loop (- i 1) (mod (+ (* 31 s) (hash (vector-ref x i))))))))
          ((string? x)
            (let loop ((i (- (string-length x) 1)) (s 0))
              (if (negative? i) s
                (loop (- i 1) (mod (+ (* 31 s) (hash (string-ref x i))))))))
          ((procedure? x) (error 'hash "can't hash procedure"))
          ((port? x) (error 'hash "can't hash port"))
          (else (error 'hash "don't know how to hash object"))))

  (define (member? set key)
    (let* ((h (modulo (hash key) limit))
           (b (vector-ref set h)))
      (if (member key b) #t #f)))

  (define (adjoin set key)
    (let* ((h (modulo (hash key) limit))
           (b (vector-ref set h)))
      (cond ((member key b) set)
      (else (vector-set! set h (cons key b)) set))))

  (define (delete set key)
    (define (remove x xs)
      (let loop ((xs xs) (zs (list)))
        (cond ((null? xs) zs)
              ((equal? (car xs) x)
                (append (cdr xs) zs))
              (else (loop (cdr xs) (cons (car xs) zs))))))
    (let* ((h (modulo (hash key) limit))
           (b (vector-ref set h)))
      (cond ((not (member key b)) set)
      (else (vector-set! set h (remove key b)) set))))

  (define (intersect set1 set2)
    (let ((set (make-set limit)))
      (let loop ((keys (enlist set1)))
        (cond ((null? keys) set)
              ((set2 'member? (car keys))
                (set! set (set 'adjoin (car keys)))
                (loop (cdr keys)))
              (else (loop (cdr keys)))))))

  (define (union set1 set2)
    (let ((set (make-set limit)))
      (let loop ((keys (enlist set1)))
        (when (pair? keys)
          (set! set (set 'adjoin (car keys)))
          (loop (cdr keys))))
      (let loop ((keys (set2 'enlist)))
        (when (pair? keys)
          (set! set (set 'adjoin (car keys)))
          (loop (cdr keys))))
      set))

  (define (minus set1 set2)
    (let ((set (make-set limit)))
      (let loop ((keys (enlist set1)))
        (when (pair? keys)
          (set! set (set 'adjoin (car keys)))
          (loop (cdr keys))))
      (let loop ((keys (set2 'enlist)))
        (when (pair? keys)
          (set! set (set 'delete (car keys)))
          (loop (cdr keys))))
      set))

  (define (enlist set)
    (let loop ((i 0) (s (list)))
      (if (= i limit) s
        (loop (+ i 1) (append (vector-ref set i) s)))))

  (define (size set)
    (let loop ((i 0) (s 0))
      (if (= i limit) s
        (loop (+ i 1) (+ s (length (vector-ref set i)))))))

  (define (new set)
    (lambda (message . arg) (dispatch set message arg)))

  (define (dispatch set message arg)
    (case message
      ((member?) (member? set (car arg)))
      ((adjoin) (new (adjoin set (car arg))))
      ((delete) (new (delete set (car arg))))
      ((intersect) (intersect set (car arg)))
      ((union) (union set (car arg)))
      ((minus) (minus set (car arg)))
      ((enlist) (enlist set))
      ((size) (size set))
      (else (error 'set "invalid message"))))

  (new (make-vector limit (list))))

(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 (vector-sort! vec comp)
  (define-syntax while
    (syntax-rules ()
      ((while pred? body ...)
        (do () ((not pred?)) body ...))))
  (define-syntax assign!
    (syntax-rules ()
      ((assign! var expr)
        (begin (set! var expr) var))))

  (define len (vector-length vec))
  (define-syntax v (syntax-rules () ((v k) (vector-ref vec k))))
  (define-syntax v! (syntax-rules () ((v! k x) (vector-set! vec k x))))
  (define-syntax cmp (syntax-rules () ((cmp a b) (comp (v a) (v b)))))
  (define-syntax lt? (syntax-rules () ((lt? a b) (negative? (cmp a b)))))
  (define-syntax swap! (syntax-rules () ((swap! a b)
    (let ((t (v a))) (v! a (v b)) (v! b t)))))
  (define (vecswap! a b s)
    (do ((a a (+ a 1)) (b b (+ b 1)) (s s (- s 1))) ((zero? s))
      (swap! a b)))

  (define (med3 a b c)
    (if (lt? b c)
        (if (lt? b a) (if (lt? c a) c a) b)
        (if (lt? c a) (if (lt? b a) b a) c)))
  (define (pv-init a n)
    (let ((pm (+ a (quotient n 2))))
      (when (> n 7)
        (let ((pl a) (pn (+ a n -1)))
          (when (> n 40)
            (let ((s (quotient n 8)))
              (set! pl (med3 pl (+ pl s) (+ pl s s)))
              (set! pm (med3 (- pm s) pm (+ pm s)))
              (set! pn (med3 (- pn s s) (- pn s) pn))))
          (set! pm (med3 pl pm pn))))
      pm))

  (let qsort ((a 0) (n len))
    (if (< n 7)
        (do ((pm (+ a 1) (+ pm 1))) ((not (< pm (+ a n))))
          (do ((pl pm (- pl 1)))
              ((not (and (> pl a) (> (cmp (- pl 1) pl) 0))))
            (swap! pl (- pl 1))))
        (let ((pv (pv-init a n)) (r #f)
              (pa a) (pb a) (pc (+ a n -1)) (pd (+ a n -1)))
          (swap! a pv) (set! pv a)
          (let loop ()
            (while (and (<= pb pc) (<= (assign! r (cmp pb pv)) 0))
              (when (= r 0) (swap! pa pb) (set! pa (+ pa 1)))
              (set! pb (+ pb 1)))
            (while (and (>= pc pb) (>= (assign! r (cmp pc pv)) 0))
              (when (= r 0) (swap! pc pd) (set! pd (- pd 1)))
              (set! pc (- pc 1)))
            (unless (> pb pc)
              (swap! pb pc) (set! pb (+ pb 1)) (set! pc (- pc 1)) (loop)))
          (let ((pn (+ a n)))
            (let ((s (min (- pa a) (- pb pa)))) (vecswap! a (- pb s) s))
            (let ((s (min (- pd pc) (- pn pd 1)))) (vecswap! pb (- pn s) s))
            (let ((s (- pb pa))) (when (> s 1) (qsort a s)))
            (let ((s (- pd pc))) (when (> s 1) (qsort (- pn s) s))))))))

(define (3sum-brute xs)
  (define (x n) (vector-ref xs n))
  (let ((len (vector-length xs)))
  (list-of (sort < (list (x i) (x j) (x k)))
    (i range len)
    (j range (+ i 1) len)
  (k range (+ j 1) len)
  (zero? (+ (x i) (x j) (x k))))))

(define (3sum-search xs)
  (define (x n) (vector-ref xs n))
  (let ((s (make-set 97)) (len (vector-length xs)))
    (do ((i 0 (+ i 1))) ((= i len))
      (s 'adjoin (x i)))
    (list-of (sort < (list (x i) (x j) k))
      (i range len)
      (j range (+ i 1) len)
      (k is (- (+ (x i) (x j))))
      (s 'member? k))))

(define (prune xs)
  (let ((s (make-set 97)))
    (do ((xs xs (cdr xs))) ((null? xs))
      (s 'adjoin (car xs)))
    (s 'enlist)))

(define (cmp a b) (if (< a b) -1 (if (< b a) 1 0)))

(define (3sum-sort xs)
  (vector-sort! xs cmp)
  (let ((len (vector-length xs)) (zs (list)))
    (define (x n) (vector-ref xs n))
    (do ((i 0 (+ i 1))) ((= i (- len 2)))
      (let loop ((lo (+ i 1)) (hi (- len 1)))
        (when (< lo hi)
          (let ((s (+ (x i) (x lo) (x hi))))
            (cond ((negative? s) (loop (+ lo 1) hi))
                  ((positive? s) (loop lo (- hi 1)))
                  (else (set! zs (cons (sort < (list (x i) (x lo) (x hi))) zs))))))))
    zs))

(define xs '#(8 -25 4 10 -10 -7 2 -3))
(display (3sum-brute xs)) (newline)
(display (prune (3sum-search xs))) (newline)
(display (3sum-sort xs)) (newline)


Output:
1
2
3
((-10 2 8) (-7 -3 10))
((-7 -3 10) (-10 2 8))
((-7 -3 10) (-10 2 8))


Create a new paste based on this one


Comments: