Write a function that accepts an integer array. If the array can be split into two sequences, the first of which is a sequence of non-increasing values and the second of which is a sequence of non-decreasing values, the function should return the index of a minimum value, otherwise it should return -1.
$ cat dia.rkt #lang racket (define (v-shaped-array a) ; If the given array can be split into two sequences, the first ; of which is a sequence of non-increasing values and the ; second of which is a sequence of non-decreasing values, ; return the index of a least value, otherwise return -1. (define n (vector-length a)) (if (< n 1) -1 (let loop ((l 1) ; non-increasing(a[0..l)) (r (- n 1))) ; non-decreasing(a[r..n)) (cond ((>= l r) (- l 1)) ((>= (vector-ref a (- l 1)) (vector-ref a l)) (loop (+ l 1) r)) ((<= (vector-ref a (- r 1)) (vector-ref a r)) (loop l (- r 1))) (#t -1))))) (module+ test (require rackunit srfi/43) (check-eq? (v-shaped-array #()) -1) (check-eq? (v-shaped-array #(1)) 0) (check-eq? (v-shaped-array #(1 3 1)) -1) (check-eq? (v-shaped-array #(2 1 3 1 2)) -1) (define n 23) (define v (vector-map (lambda (i e) (random n)) (make-vector n))) (define min-v (vector-fold (lambda (i mn e) (min mn e)) (vector-ref v 0) v)) (define (vector-reduce k v l r) (let loop ((i (+ l 1))) (cond ((>= i r) #t) ((k (vector-ref v (- i 1)) (vector-ref v i)) (loop (+ i 1))) (#t #f)))) (define (non-increasing v l r) (vector-reduce >= v l r)) (define (non-decreasing v l r) (vector-reduce <= v l r)) (define (partition v i) (let ((v (vector-copy v))) (vector-sort! v >= 0 i) (vector-sort! v <= i (vector-length v)) v)) (do ((i 0 (+ i 1))) ((= i n) (void)) (let* ((v (partition v i)) (min-i (v-shaped-array v))) (check-not-eq? min-i -1) (check-eq? (vector-ref v min-i) min-v) (check-true (non-increasing v 0 min-i)) (check-true (non-decreasing v min-i n))))) $ raco test dia.rkt raco test: (submod "dia.rkt" test) 96 tests passed $