# 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

\$

```