use itertools::Itertools;
use std::cmp::Ordering;
pub fn valid_mountain_array(a: Vec<i32>) -> bool {
    let mut cmps = a.windows(2).map(|w| w[0].cmp(&w[1])).dedup();
    let first_cmp = cmps.next();
    let second_cmp = cmps.next();
    let third_cmp = cmps.next();
    first_cmp == Some(Ordering::Less)
        && second_cmp == Some(Ordering::Greater)
        && third_cmp.is_none()
}

We use a sliding window to loop on all subslices of size 2. For each subslice we figure out if it is increasing, decreasing or equal. We then use dedup to eliminate all consecutive equal orderings. If our array is a mountain array then our iterator will only loop twice. The first iteration will be on Ordering::Less and the second and last one on Ordering::Greater.

If we take for example [1,2,4,5,3,2,2]:

• windows loops on [1,2], [2,4], [4,5], [5,3], [3,2], [2,2]
• map loops on L,L,L,G,G,E (L is Ordering::Less, G is Ordering::Greater, E is Ordering::Equal).
• dedup loops on L,G,E

and so we are not a mountain because the third comparison is not None.

Ok, let’s go for the parallel solution.

We cannot directly translate the sequential code because there is no dedup. Let’s try thinking a bit in a divide and conquer way. Take for example an input 1, 3, 7, 9, 10, 4, 2. This corresponds to the windows [[1,3], [3,7], [7,9], [9,10], [10,4], [4,2]] and therefore to the comparisons L,L,L,L,G,G.

We divide in two sub-inputs:

• L,L,L
• L,G,G

We must then recurse and finally fuse the resulting solutions. If we do a naive recursion we can see that L,L,L is not mountainy while L,G,G is. The answer we expect is that the initial input [1,3,5,7,9,10,4,2] is a mountain array. This means that a boolean is not enough to store the information needed to re-construct the final solution. The right L,G,G is mountainy but we need to know that the left L,L,L is strictly increasing.

So, instead if having a boolean we are going to use an enumerated type for storing the shape of a sub-window.

#[derive(PartialEq, Eq)]
enum Shape {
    Unknown,
    Increasing,
    Decreasing,
    Mountain,
}

What about more complex shapes ? Like Increasing then Decreasing then Increasing again ? Well, such shapes are invalid because if we have one we are never going to end up with a mountain and we should abort all computations. We are not storing such cases but will instead use a Result<Shape, ()>.

So, with the right types we can now write or parallel algorithm:

pub fn par_valid_mountain_array(a: Vec<i32>) -> bool {
    a.par_windows(2)
        .map(|w| w[0].cmp(&w[1]))
        .map(|o| match o {
            Ordering::Equal => Err(()),
            Ordering::Less => Ok(Shape::Increasing),
            Ordering::Greater => Ok(Shape::Decreasing),
        })
        .try_reduce(
            || Shape::Unknown,
            |a, b| {
                if a == b || a == Shape::Unknown {
                    Ok(b)
                } else if a == Shape::Increasing {
                    match b {
                        Shape::Decreasing => Ok(Shape::Mountain),
                        Shape::Mountain => Ok(Shape::Mountain),
                        _ => Err(()),
                    }
                } else if a == Shape::Mountain && b == Shape::Decreasing {
                    Ok(Shape::Mountain)
                } else {
                    Err(())
                }
            },
        )
        == Ok(Shape::Mountain)
}

Would we have speedup in practice ? Well, it is not completely sure. First we need a very large input because the sequential algorithm is already blazing fast. Another thing which could maybe have an impact is to use a try_fold instead of the map. Since we have a more complex algorithm than the sequential one our work increase will translate into a performance loss. Finally this algorithm seems to put a lot of pressure on the memory bus and will surely not scale nicely.

If you give it a try and manage to get some performance curves, send them to me and I’ll upload them here. It is better to try on valid mountains.