decreasing-increasing arrays


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 
  
 $