Peaks

February 15, 2019

Given an array of integers, a peak is a subarray of minimal length in which the integer values increase and then decrease. For instance, in the array [5,5,4,5,4] there is a peak [4,5,4] and in the array [6,5,4,4,4,4,4,5,6,7,7,7,7,7,6] there is a peak [6,7,7,7,7,7,6]. Note that [4,5,6,7,7,7,7,7,6] shows a pattern of increasing and decreasing values, but it is not minimal because the first two items can be removed and the remaining subarray remains a peak. The array [5,5,5,5,4,5,4,5,6,7,8,8,8,8,8,9,9,8] has two peaks, [4,5,4] and [8,9,9,8].

Your task is to write a program that finds all of the peaks in an array. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

10 Responses to “Peaks”

  1. matthew said

    Looks like a job for Regular Expressions:

    import re
    def compare(x,y): return '<' if x < y else '=' if x == y else '>'
    def findpeaks(a):
        cmpstring = "".join([compare(a[i],a[i+1]) for i in range(len(a)-1)])
        return (match.span() for match in re.finditer('<=*>',cmpstring))
    
    a = [5,5,5,5,4,5,4,5,6,7,8,8,8,8,8,9,9,8]
    for (start,end) in findpeaks(a):
        print(a[start:end+1])
    
    [4, 5, 4]
    [8, 9, 9, 8]
    

    By the way, what’s with the “This post is ad-supported” in the emails? Didn’t used to get them, they are quite annoying.

  2. Smith said
    def peak(a=[5,5,5,5,4,5,4,5,6,7,8,8,8,8,8,9,9,8]):
        a = np.pad(np.array(a), (0, 1) , mode='edge')
        indices = np.arange(len(a)-1)
    
        # where first derivative is not zero, normalized to -1 and 1
        d1 = a[:-1] - a[1:]
        mask = d1 != 0
        mask2, im = (np.abs(d1[mask]) / d1[mask]), indices[mask]
    
        # where first derivate changes from negative 1 to positive 1
        mask3 = ((mask2[:-1] - mask2[1:]) == -2)
        
        l, r = im[:-1][mask3], im[1:][mask3] + 1
        return [a[f:s+1].tolist() for f,s in zip(l,r)]
    
    peak()
    
    [[4, 5, 4], [8, 9, 9, 8]]
    
  3. Globules said

    A Haskell version. We run-length encode the input lists so that we only have to look for three consecutive values that match the pattern low-high-low.

    import Control.Arrow ((&&&))
    import Data.List (group)
    
    type Run a = (Int, a)
    
    -- Run length encode the argument.
    rle :: Eq a => [a] -> [Run a]
    rle = map (length &&& head) . group
    
    -- Run length decode the argument.
    rld :: [Run a] -> [a]
    rld = concatMap (uncurry replicate)
    
    -- Expand three runs into a list.
    expand :: (Run a, Run a, Run a) -> [a]
    expand (x, y, z) = rld [x] ++ rld [y] ++ rld [z]
    
    -- Trim the leading and trailing runs to a single element each.
    trim :: (Run a, Run a, Run a) -> (Run a, Run a, Run a)
    trim ((_, x), keep, (_, z)) = ((1, x), keep, (1, z))
    
    -- Do these three runs indicate a peak?
    isPeak :: Ord a => (Run a, Run a, Run a) -> Bool
    isPeak ((_, x), (_, y), (_, z)) = x < y && y > z
    
    -- The list of peaks in the argument list.
    peaks :: Ord a => [a] -> [[a]]
    peaks = map (expand . trim) . filter isPeak . consec . rle
      where consec xs = zip3 xs (drop 1 xs) (drop 2 xs)
    
    main :: IO ()
    main = do
      print $ peaks ([] :: [()])
      print $ peaks [1]
      print $ peaks [1, 2]
      print $ peaks [5, 5, 4, 5, 4]
      print $ peaks [6, 5, 4, 4, 4, 4, 4, 5, 6, 7, 7, 7, 7, 7, 6]
      print $ peaks [5, 5, 5, 5, 4, 5, 4, 5, 6, 7, 8, 8, 8, 8, 8, 9, 9, 8]
    
    $ ./peaks
    []
    []
    []
    [[4,5,4]]
    [[6,7,7,7,7,7,6]]
    [[4,5,4],[8,9,9,8]]
    
  4. matthew said

    Here’s another Haskell solution. It uses a regex like my first solution, but since we don’t have regexs for arbitrary data types (don’t see why not), I’ve implemented simple regex matching as well:

    data Pattern a = A a | Seq [Pattern a] | Alt (Pattern a) (Pattern a)
    
    -- A simple regex matcher. Try to match initial segment of
    -- list. Return list of (length, remaining list) pairs.
    match :: Ord a => Pattern a -> (Int,[a]) -> [(Int,[a])]
    match (A a) (n,[]) = []
    match (A a) (n, a':s)
     | a == a' = [(n+1,s)]
     | otherwise = []
    match (Seq []) ns = [ns]
    match (Seq (p:pp)) ns = concatMap (match (Seq pp)) (match p ns)
    match (Alt p1 p2) ns = match p1 ns ++ match p2 ns
    
    -- Find all matches and return list of (start,end) pairs
    matchall p n [] = matchone p n []
    matchall p n s = matchone p n s ++ matchall p (n+1) (tail s)
    matchone p n s = [(n,n') | (n',s') <- match p (n,s)]
    
    -- Define star as a recursive pattern
    star p = p' where p' = Alt (Seq []) (Seq [p,p'])
    
    re = Seq([A GT,star(A EQ),A LT])
    
    prepeaks a = matchall re 0 (zipWith compare (tail a) a)
    peaks a = [take (n-m+1) (drop m a) | (m,n) <- prepeaks a]
    
    main = do
      print $ peaks [1]
      print $ peaks [1, 2]
      print $ peaks [5, 5, 4, 5, 4]
      print $ peaks [1, 2, 1, 2, 1, 2, 1]
      print $ peaks [6, 5, 4, 4, 4, 4, 4, 5, 6, 7, 7, 7, 7, 7, 6]
      print $ peaks [5, 5, 5, 5, 4, 5, 4, 5, 6, 7, 8, 8, 8, 8, 8, 9, 9, 8]
    
  5. Daniel said

    Here’s a solution in C.

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct peak {
      int idx;
      int len;
    } peak_t;
    
    void get_peaks(int* array, int n, peak_t** peaks, int* n_peaks) {
      int capacity = 1;
      *peaks = malloc(sizeof(peak_t) * capacity);
      *n_peaks = 0;
      peak_t peak;
      int in_peak = 0;
      for (int i = 1; i < n; ++i) {
        if (array[i] > array[i - 1]) {
          peak.idx = i - 1;
          peak.len = 2;
          in_peak = 1;
          continue;
        }
        if (!in_peak) continue;
        ++(peak.len);
        if (array[i] == array[i - 1]) continue;
        ++(*n_peaks);
        if (*n_peaks > capacity) {
          capacity *= 2;
          *peaks = realloc(*peaks, sizeof(peak_t) * capacity);
        }
        (*peaks)[*n_peaks - 1] = peak;
        in_peak = 0;
      }
    }
    
    void free_peaks(peak_t** peaks) {
      free(*peaks);
      *peaks = NULL;
    }
    
    void print_array(int* array, int n) {
      printf("[");
      for (int i = 0; i < n; ++i) {
        if (i > 0) printf(", ");
        printf("%d", array[i]);
      }
      printf("]\n");
    }
    
    int main(int argc, char* argv[]) {
      int n = argc - 1;
      int* array = malloc(sizeof(int) * n);
      for (int i = 0; i < n; ++i) {
        array[i] = atoi(argv[i+1]);
      }
      peak_t* peaks;
      int n_peaks;
      get_peaks(array, n, &peaks, &n_peaks);
      for (int i = 0; i < n_peaks; ++i) {
        print_array(array + peaks[i].idx, peaks[i].len);
      }
      free_peaks(&peaks);
      free(array);
      return EXIT_SUCCESS;
    }
    

    Example:

    $ ./a.out 5 5 5 5 4 5 4 5 6 7 8 8 8 8 8 9 9 8
    [4, 5, 4]
    [8, 9, 9, 8]
    
  6. Daniel said

    Here’s a solution in Python.

    def get_peaks(l):
        tmp = [y - x for x, y in zip(l, l[1:])]
        tmp = [x for x in enumerate(tmp) if x[1] != 0]
        tmp = [(x[0], y[0]) for x, y in zip(tmp, tmp[1:]) if x[1] > 0 > y[1]]
        tmp = [l[x:y+2] for x, y in tmp]
        return tmp
    
    l = [5,5,5,5,4,5,4,5,6,7,8,8,8,8,8,9,9,8]
    for peak in get_peaks(l):
        print(peak)
    

    Output:

    [4, 5, 4]
    [8, 9, 9, 8]
    
  7. matthew said

    Here’s a slightly improved version of that regex matcher:

    data Pattern a = A a | Seq [Pattern a] | Alt [Pattern a]
    
    match :: Eq a => Pattern a -> (Int,[a]) -> [(Int,[a])]
    match (A a) (n,[]) = []
    match (A a) (n, a':s)
     | a == a' = [(n+1,s)]
     | otherwise = []
    match (Seq pp) ns = foldl (flip (concatMap . match)) [ns] pp
    match (Alt pp) ns = concatMap (flip match ns) pp
    
  8. Daniel said

    Here’s another Python solution.

    import numpy as np
    
    def get_peaks(l):
        x = np.sign(np.diff(l))
        y = np.nonzero(x)[0]
        x = np.diff(x[y])
        x = np.where(x == -2)[0]
        x = [l[y[x]:y[x+1]+2] for x in x]
        return x
    
    l = [5,5,5,5,4,5,4,5,6,7,8,8,8,8,8,9,9,8]
    
    for peak in get_peaks(l):
        print(peak)
    

    Output:

    [4, 5, 4]
    [8, 9, 9, 8]
    
  9. Daniel said

    In line 8 of my last post, I used the same name for both the list and the variable used to loop over the list. It seems to work, but was not my intent, arising from a renaming of variables.

    Here’s the updated line 8.

    x = [l[y[z]:y[z+1]+2] for z in x]
    
  10. Smith said

    @Daniel, glad someone had a prettier numpy solution!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: