Write a function accepting an integer list l and returning a triple (a b c) such that a is the smallest element in l, c is the largest element in l, and b is the smallest element not in l such that a < b < c.
$ cat mmm.rkt #lang racket (require rnrs/sorting-6 rackunit "utl.rkt" "priority-queue.rkt") (define (ht-min-missing-max l) ; Given the unsorted list of integers l, return the ; triple (mn sm mx) such that mn is the smallest ; integer in l, mx is the largest integer in l and ; sm is the smallest integer strictly between mn and mx ; not in l. If there's no such integer, sm is undefned. ; If there's no such triple, return is undefined. (define (smallest-missing mn mx ht) ; Given the sorted integer vector v, return the ; smallest integer strictly between v's min and max ; elements not in v. Return undefined if there's ; no such integer. (let loop ((i (+ mn 1))) (when (< i mx) (if (hash-has-key? ht i) (loop (+ i 1)) i)))) (let* ((e (car l)) (ht (make-hash (list (cons e #t))))) (let loop ((l (cdr l)) (mn e) (mx e)) (if (null? l) (list mn (smallest-missing mn mx ht) mx) (let ((e (car l))) (hash-set! ht e #t) (loop (cdr l) (min mn e) (max mx e))))))) (define (pq-min-missing-max l) ; Given the unsorted list of integers l, return the ; triple (mn sm mx) such that mn is the smallest ; integer in l, mx is the largest integer in l and ; sm is the smallest integer strictly between mn and mx ; not in l. If there's no such integer, sm is undefned. ; If there's no such triple, return is undefined. (define (smallest-missing-element! min-q) ; Given the minimum priority queue min-q, return the ; smallest integer strictly between min-q's min and max ; elements not in min-q. Code assumes such an integer ; exists. (let loop ((min-e (pq-dq! min-q))) (let ((next-min-e (+ min-e 1))) (if (= next-min-e (pq-dq! min-q)) (loop next-min-e) next-min-e)))) (define (largest-element! min-q) ; Return the largest element in the given the minimum ; priority queue min-q Code assumes such an element ; exists. (let loop ((le (pq-dq! min-q))) (if (pq-empty? min-q) le (loop (pq-dq! min-q))))) (let* ((min-q (pq-new < l)) (min (pq-top min-q)) (sme (smallest-missing-element! min-q))) (list min sme (largest-element! min-q)))) (define (sorted-min-missing-max l) ; Given the unsorted list of integers l, return the ; triple (mn sm mx) such that mn is the smallest ; integer in l, mx is the largest integer in l and ; sm is the smallest integer strictly between mn and mx ; not in l. If there's no such integer, sm is undefned. ; If there's no such triple, return is undefined. (define (missing-min v) ; Given the sorted integer vector v, return the ; smallest integer strictly between v's min and max ; elements not in v. Return undefined if there's ; no such integer. (let ((n (vector-length v))) (let loop ((i 1) (mm (+ (vector-ref v 0) 1))) (when (< i n) (let ((e (vector-ref v i))) (if (= e mm) (loop (+ i 1) (+ e 1)) mm)))))) (unless (null? l) (let ((v (vector-sort < (list->vector l)))) (list (vector-ref v 0) (missing-min v) (vector-ref v (- (vector-length v) 1)))))) (let ((in '(-1 4 5 -23 24)) (out '(-23 -22 24))) (for-each (lambda (f) (check-equal? (f in) out)) (list sorted-min-missing-max ht-min-missing-max pq-min-missing-max))) (define (chopped-permuted-iota n) (let loop () (let* ((l (permuted-iota n)) (a (car l)) (b (cadr l)) (min-ab (min a b))) (if (or (= min-ab 0) (= (max a b) (- n 1))) (loop) (values min-ab (cddr l)))))) (define (run-test iters l-size f) (let loop ((i 0)) (when (< i iters) (let-values (((mn l) (chopped-permuted-iota l-size))) (check-equal? (f l) (list 0 mn (- l-size 1))) (loop (+ i 1)))))) (run-test 100 20 sorted-min-missing-max) (run-test 100 20 ht-min-missing-max) (run-test 100 20 pq-min-missing-max) (define (time-it f N l) (let loop ((t 0) (n N)) (if (= n 0) (round (/ t N)) (let-values (((a b c d) (time-apply f (list l)))) (loop (+ t b) (- n 1)))))) (define (time n l) (printf "~a ~a ~a ~a\n" (length l) (time-it sorted-min-missing-max n l) (time-it ht-min-missing-max n l) (time-it pq-min-missing-max n l) )) (define N 20) (printf "n sorted hash table priority queue\n" ) (do ((i 100002 (+ i 100000))) ((> i 500002)) (let-values (((mn l) (chopped-permuted-iota i))) (time N l))) $ mzscheme mmm.rkt n sorted hash table priority queue 100000 54 50 200 200000 120 121 421 300000 191 187 661 400000 257 327 917 500000 333 404 1174 $