Programming Praxis

10 Responses to “Peaks”

1. matthew said

   February 15, 2019 at 10:26 AM

   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

   February 15, 2019 at 1:38 PM

   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

   February 16, 2019 at 7:40 AM

   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

   February 16, 2019 at 5:41 PM

   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

   February 17, 2019 at 3:17 AM

   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

   February 17, 2019 at 3:22 AM

   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

   February 17, 2019 at 7:36 AM

   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

   February 17, 2019 at 5:05 PM

   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

   February 17, 2019 at 5:55 PM

   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

    February 17, 2019 at 6:36 PM

    @Daniel, glad someone had a prettier numpy solution!