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.
Programming Praxis 
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])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.
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()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.
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:
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:
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:
Here’s a slightly improved version of that regex matcher:
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:
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.
@Daniel, glad someone had a prettier numpy solution!