Finding Local Extremes

Question

Write a function or program that takes in a list and produces a list of the local extremes.

In a list [x_0, x_1, x_2...] a local extreme is an x_i such that x_(i-1) < x_i and x_(i+1) < x_i or x_(i-1) > x_i and x_(i+1) > x_i. Notice that the first and last elements of the list can never be local extremes.

So for some examples

local_extremes([1, 2, 1]) = [2]
local_extremes([0, 1, 0, 1, 0]) = [1, 0, 1]
local_extremems([]) = []

This is code golf so the shortest code wins!

Answer 1

J - 19 char

Couldn't help it ;)

(}:#~0,0>2*/\2-/\])

Explanation follows:

• 2-/\] - Over each pair of elements in the argument (each 2-item long infix), take the difference.
• 2*/\ - Now over each pair of the new list, take the product.
• 0> - Test whether each result is less than 0. This only happens if the multiplicands had alternating signs, i.e. it doesn't happen if they had the same sign or either was zero.
• 0, - Declare that the first element isn't an extreme element.
• }: - Cut off the last element, because that can't possibly be an extreme either.
• #~ - Use the true values on the right side to pick items from the list on the left side.

Usage:

   (}:#~0,0>2*/\2-/\]) 1 2 1
2
   (}:#~0,0>2*/\2-/\]) 0 1 0 1 0
1 0 1
   (}:#~0,0>2*/\2-/\]) i.0   NB. i.0 is the empty list (empty result also)

   (}:#~0,0>2*/\2-/\]) 3 4 4 4 2 5
2

Answer 2

Mathematica 66 58 51

Current Solution

Shortened thanks to a contribution by Calle.

Cases[Partition[#,3,1],{a_,b_,c_}/;(a-b) (b-c)<0⧴b]&

Partition[#,3,1] finds the triples.

(a-b) (b-c)<0 is true if and only if b is below a, c, or above a,c. and looks at takes the signs of the differences. A local extreme will return either {-1,1} or {1,-1}.

---

Examples

Cases[Partition[#, 3, 1], {a_, b_, c_} /; (a - b) (b - c) < 0 :> b] &[{1, 2, 1}]
Cases[Partition[#, 3, 1], {a_, b_, c_} /; (a - b) (b - c) < 0 :> b] &[{0, 1, 0, 1, 0}]
Cases[Partition[#, 3, 1], {a_, b_, c_} /; (a - b) (b - c) < 0 :> b] &[{}]
Cases[Partition[#, 3, 1], {a_, b_, c_} /; (a - b) (b - c) < 0 :> b] &[{9, 10, 7, 6, 9, 0, 3, 3, 1, 10}]

{2}
{1, 0, 1}
{}
{10, 6, 9, 0, 1}

---

Earlier Solution

This looks examples all triples (generated by Partition) and determines whether the middle element is less than both extremes or greater than the extremes.

Cases[Partition[#,3,1],{a_,b_,c_}/;(b<a∧b<c)∨(b>a∧b>c)⧴b]& ;

---

First Solution

This finds the triples, and looks at takes the signs of the differences. A local extreme will return either {-1,1} or {1,-1}.

Cases[Partition[#,3,1],x_/;Sort@Sign@Differences@x=={-1,1}⧴x[[2]]]&

Example

Cases[Partition[#,3,1],x_/;Sort@Sign@Differences@x=={-1,1}:>x[[2]]]&[{9, 10, 7, 6, 9, 0, 3, 3, 1, 10}]

{10, 6, 9, 0, 1}

---

Analysis:

Partition[{9, 10, 7, 6, 9, 0, 3, 3, 1, 10}]

{{9, 10, 7}, {10, 7, 6}, {7, 6, 9}, {6, 9, 0}, {9, 0, 3}, {0, 3, 3}, {3, 3, 1}, {3, 1, 10}}

% refers to the result from the respective preceding line.

Differences/@ %

{{1, -3}, {-3, -1}, {-1, 3}, {3, -9}, {-9, 3}, {3, 0}, {0, -2}, {-2, 9}}

Sort@Sign@Differences@x=={-1,1} identifies the triples from {{9, 10, 7}, {10, 7, 6}, {7, 6, 9}, {6, 9, 0}, {9, 0, 3}, {0, 3, 3}, {3, 3, 1}, {3, 1, 10}} such that the sign (-, 0, +) of the differences consists of a -1 and a 1. In the present case those are:

{{9, 10, 7}, {7, 6, 9}, {6, 9, 0}, {9, 0, 3}, {3, 1, 10}}

For each of these cases, x, x[[2]] refers to the second term. Those will be all of the local maxima and minima.

{10, 6, 9, 0, 1}

Answer 3

Javascript - 62 45 Characters

f=a=>a.filter((x,i)=>i&&i<a.length-1&&(a[i-1]-x)*(a[i+1]-x)>0)

Edit

f=a=>a.filter((x,i)=>(a[i-1]-x)*(a[i+1]-x)>0)

Answer 4

Ruby, 83 70 60 55 49 characters

f=->a{a.each_cons(3){|x,y,z|p y if(x-y)*(z-y)>0}}

Prints all local extremes to STDOUT.

Uses the <=> "spaceship" operator, which I really like. (It returns 1 if the first thing is greater than the second, -1 if it's less, and 0 if equal. Therefore, if they add to -2 or 2, that means the middle is an extreme.)

Not anymore, as @daniero pointed out that the "obvious" way is actually shorter!

Changed yet again! Now it uses the awesome algorithm found in MT0's answer (+1 to him!).

Also, I like each_cons which selects each n groups of consecutive elements in an array. And trailing if is interesting too.

Overall, I just like how elegant it looks.

Some sample runs:

irb(main):044:0> f[[1,2,1]]
2
=> nil
irb(main):045:0> f[[1,0,1,0,1]]
0
1
0
=> nil
irb(main):046:0> f[[]]
=> nil
irb(main):047:0> f[[1,2,3,4,5,4,3,2,1]]
5
=> nil
irb(main):048:0> f[[1,1,1,1,1]]
=> nil
irb(main):049:0> f[[10,0,999,-45,3,4]]
0
999
-45
=> nil

Answer 5

C++ - 208 chars

Longest solution again:

#include<iostream>
#include<deque>
using namespace std;
int main(){deque<int>v;int i;while(cin){cin>>i;v.push_back(i);}for(i=0;i<v.size()-2;)if(v[++i]>v[i-1]&v[i]>v[i+1]|v[i]<v[i-1]&v[i]<v[i+1])cout<<v[i]<<' ';}

To use, enter your integers, then any character that will crash the input stream - any non-number characters should work.

Input: 0 1 0 x

Output: 1

Answer 6

Jelly, 8 bytes

IṠIỊ¬T‘ị

Try it online!

Explanation

IṠIỊ¬T‘ị
I          Differences between adjacent elements {of the input}
 Ṡ         Take the sign of each difference
  I        Differences between adjacent difference signs
   Ị       Mark the elements that are     in the range -1..1 inclusive
    ¬                                 not
     T     Take the indexes of the marked elements
      ‘      with an offset of 1
       ị   Index back into the original list

An element is only a local extreme if its difference with its left neighbour has an opposite sign to its difference with its right neighbour, i.e. the signs of the differences differ by 2 or -2. Jelly has a number of useful primitives for dealing with "find elements with certain properties" (in particular, we can find elements with certain properties in one list and use that to extract elements from a different list), meaning that we can translate back to the original list more or less directly (we just need to offset by 1 because the first and last elements of the original list got lost in the difference-taking).

Answer 7

Matlab - 45 bytes

x=input('');y=diff(x);x(find([0 y].*[y 0]<0))

Answer 8

Python 2.7 - 73 bytes

e=lambda l:[l[i]for i in range(1,len(l)-1)if(l[i]-l[i-1])*(l[i]-l[i+1])]

Not too impressive (Look at every element of the list except the first and last, see if it's larger or smaller than its neighbours). I'm mostly only posting it because not everyone knows you can do x<y>z and have it work. I think that's kind of neat.

Yes, x<y>z is a cool feature of python, but it's not actually optimal in this case. Thanks to V-X for the multiplication trick, that didn't occur to me at all. Wrzlprmft reminded me that declaring an anonymous function is less keystrokes than def x(y):.

Answer 9

Haskell 50

f a=[x|(p,x,n)<-zip3 a(tail a)(drop 2 a),x>p&&x>n]

Answer 10

05AB1E, 11 10 bytes

¥.±¥Ä2Q0šÏ

Try it online or verify a few more test cases.

Explanation:

¥           # Get the forward differences (deltas) of the (implicit) input-list
            #  i.e. [9,10,7,6,9,0,3,3,1,10] → [1,-3,-1,3,-9,3,0,-2,9]
 .±         # Get the signum of each delta (-1 if neg.; 0 if 0; 1 if pos.)
            #  → [1,-1,-1,1,-1,1,0,-1,1]
   ¥        # Get the forward differences of that list again
            #  → [-2,0,2,-2,2,-1,-1,2]
    Ä       # Convert each integer to its absolute value
            #  → [2,0,2,2,2,1,1,2]
     2Q     # And now check which ones are equal to 2 (1 if truthy; 0 if falsey)
            #  → [1,0,1,1,1,0,0,1]
       0š   # Prepend a 0
            #  → [0,1,0,1,1,1,0,0,1]
         Ï  # And only leave the values in the (implicit) input-list at the truthy indices
            #  → [10,6,9,0,1]
            # (after which the result is output implicitly)

Answer 11

Python with Numpy – 81 74 67 bytes (61 54 without the import line)

import numpy
e=lambda a:a[1:-1][(a[2:]-a[1:-1])*(a[1:-1]-a[:-2])<0]

The input needs to be a Numpy array.

Answer 12

C, 83

x,y,z;main(){y=z=0;while(scanf("%d",&x)){(y-z)*(y-x)>0?printf("%d ",y):1;z=y,y=x;}}

Answer 13

awk - 32 chars

{c=b;b=a;a=$0;$0=b}(b-c)*(a-b)<0

No hope of beating a language like J or APL on brevity, but I thought I'd throw my hat into the ring anyway. Explanation:

• At any given time, a, b, and c hold x_i, x_(i-1), and x_(i-2)
• b-c and a-b approximate the derivative before and after x_(i-1)
• If their product is negative, then one is negative and the other is positive, therfore x_(i-1) is a local extreme, so print

Answer 14

Brachylog, 17 bytes

s₃{b≠h.&k≠&{⌉|⌋}}

Try it online!

Takes input through the input variable and generates the output through the output variable.

s₃{             }    For a length-3 substring of the input:
  {b                 its last two elements
    ≠                are distinct,
     h               and the first of those elements is
      .              the output variable;
       &k            its first two elements
         ≠           are also distinct;
          &{⌉| }     either its largest element
          &{ |⌋}     or its smallest element
                }    is also the output variable.

If runs of values could be guaranteed to be absent, s₃{{⌉|⌋}.&bh} would save four bytes.

Answer 15

Perl 5 -p, 49 bytes

s/\d+ (?=(\d+) (\d+))/say$1if($1-$&)*($1-$2)>0/ge

Try it online!

Answer 16

Wolfram Language (Mathematica), 43 42 41 bytes

BlockMap[#2&@@#/.Median@#->Set@$&,#,3,1]&

Try it online!

BlockMap[                       &,#,3,1]&   (* for every consecutive triple of elements *)
         #2&@@#                             (* take the second (middle) element, *)
               /.Median@#->Set@$            (* discarding it if it is not a local extreme *)

Answer 17

PHP, 116 114 113

function _($a){for(;$a[++$i+1];)if(($b=$a[$i])<($c=$a[$i-1])&$b<($d=$a[$i+1])or$b>$c&$b>$d)$r[]=$a[$i];return$r;}

Example usage:

print_r(_(array(2, 1, 2, 3, 4, 3, 2, 3, 4)));

Array
(
    [0] => 1
    [1] => 4
    [2] => 2
)

Answer 18

Haskell, 70C

Golfed version

e(a:b:c:r)
 |a<b&&b>c||a>b&&b<c=b:s
 |True=s
 where s=e(b:c:r)
e _=[]

Ungolfed version

-- if it's possible to get three elements from the list, take this one
extrema (a:b:c:rest)
    | a<b && b>c = b:rec
    | a>b && b<c = b:rec
    | otherwise = rec
    where rec = extrema (b:c:rest)
-- if there are fewer than three elements in the list, there are no extrema
extrema _ = []

Answer 19

Javascript: 102 characters

function h(a){for(u=i=[];++i<a.length-1;)if(x=a[i-1],y=a[i],z=a[i+1],(x-y)*(y-z)<0)u.push(y);return u}

Answer 20

APL, 19 bytes

{⍵/⍨0,⍨0,0>2×/2-/⍵}

I converted the 20 char J version to APL. But I add a zero to the beginning and the end instead of removing the first and last digit. Otherwise it works just like the J version.

⍵ - formal parameter omega. This is the input to the function.

Answer 21

Python 2, 59 bytes

f=lambda l=0,c=0,*r:r and(c,)*(l<c>r[0]or l>c<r[0])+f(c,*r)

Try it online!

This function mostly avoids the costly business of indexing, by taking the elements of the list as arguments, instead of the list itself. While there is more than one element left in the list, we recursively build up the list, checking for a maximum at each step.