14
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ To make sure I understand correctly: Numbers greater than the numbers on either side? \$\endgroup\$ – undergroundmonorail Feb 26 '14 at 21:57
  • \$\begingroup\$ @undergroundmonorail Greater or less than. So it either has to be a local minimum, where it's neighbors are both greater, or a maximum where they're both smaller \$\endgroup\$ – jozefg Feb 26 '14 at 21:57
  • \$\begingroup\$ Oh, I see. I misread it \$\endgroup\$ – undergroundmonorail Feb 26 '14 at 21:58
  • 2
    \$\begingroup\$ and what about sequence 1 2 2 1 shouldn't those 2 be considered as extremes too? - I know, this would make the solution much more difficult... \$\endgroup\$ – V-X Feb 27 '14 at 13:08

21 Answers 21

5
\$\begingroup\$

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}

\$\endgroup\$
  • \$\begingroup\$ Your Mathematica style is much more concise than mine. When do we start calling it "Wolfram Language"? \$\endgroup\$ – Michael Stern Feb 27 '14 at 1:20
  • \$\begingroup\$ I see this !Mathematica graphics \$\endgroup\$ – Dr. belisarius Feb 27 '14 at 1:24
  • \$\begingroup\$ Michael Stern, I suspect Wolfram Language will only become official at version 10, some form of which already available on Raspberry Pi. \$\endgroup\$ – DavidC Feb 27 '14 at 1:29
  • \$\begingroup\$ BTW, someone inserted a line of code that converts the Math ML to graphics. I'm not sure why. \$\endgroup\$ – DavidC Feb 27 '14 at 1:38
  • \$\begingroup\$ I'm not sure why he did it. I can't see any differences in the "modified" code \$\endgroup\$ – Dr. belisarius Feb 27 '14 at 2:09
6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Umm, this may not work if the input is, say, 3, 4, 4, 4, 4, 5, i.e. you may get a zero in the "0=" step if 0 is added to 0. \$\endgroup\$ – Lord Soth Feb 27 '14 at 1:19
  • \$\begingroup\$ Also, I do not know about this language, but, instead of taking the signum in the first step, you can leave the difference as it is. Then, in the second step, multiply the elements instead, and in the third you may check if the product is negative (this also avoids that 0 problem). Perhaps this may result in a shorter code. \$\endgroup\$ – Lord Soth Feb 27 '14 at 1:21
  • \$\begingroup\$ Good catch, and yes, this saves two characters. Updating. \$\endgroup\$ – algorithmshark Feb 27 '14 at 1:50
5
\$\begingroup\$

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)
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ It's shorter to unpack x into 3 variables: f=->a{a.each_cons(3){|x,y,z|p y if((x<=>y)+(z<=>y)).abs==2}} \$\endgroup\$ – daniero Feb 27 '14 at 1:58
  • \$\begingroup\$ @daniero Thanks; I didn't even know you could do that! Edited \$\endgroup\$ – Doorknob Feb 27 '14 at 2:03
  • \$\begingroup\$ really? :D Btw, now that each term is 3 character shorter, it's overall cheaper to do x>y&&y<z||x<y&&y>z (even tho the spaceship operator is very pretty) ;) \$\endgroup\$ – daniero Feb 27 '14 at 2:20
  • \$\begingroup\$ also... !((x..z)===y) is even shorter though not as clever \$\endgroup\$ – Not that Charles Feb 27 '14 at 2:25
  • \$\begingroup\$ @Charles That fails when x < z. \$\endgroup\$ – Doorknob Feb 27 '14 at 2:31
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ You can use a deque instead of a vector to gain 2 characters. \$\endgroup\$ – Morwenn Feb 27 '14 at 10:01
  • \$\begingroup\$ Also, instead of using i and j, you can declare int i; right after the collection and use in is the two loops instead of declaring two variables. \$\endgroup\$ – Morwenn Feb 27 '14 at 10:02
  • \$\begingroup\$ Finally, you can probably get get rid of the increment i++ in your for loop and begin your condition by if(v[++i]>[i-1]... in order to gain one character again. \$\endgroup\$ – Morwenn Feb 27 '14 at 10:04
2
\$\begingroup\$

Matlab - 45 bytes

x=input('');y=diff(x);x(find([0 y].*[y 0]<0))
\$\endgroup\$
2
\$\begingroup\$

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):.

\$\endgroup\$
  • \$\begingroup\$ if(l[i]-l[i-1])*(l[i]-l[i+1])>0 would reduce the code by 11 characters... \$\endgroup\$ – V-X Feb 27 '14 at 13:25
  • \$\begingroup\$ @wrz Ah, you're right. I was thrown off by the fact that def e(l):\n is the same number of characters as e=lambda l:, but I forgot that you don't need to use the return keyword. Thanks! \$\endgroup\$ – undergroundmonorail Feb 27 '14 at 13:53
  • \$\begingroup\$ @v-x Oh, I like that a lot. Thank you :) edit: Actually you can save more than that! Since (l[i]-l[i-1])*(l[i]-l[i+1]) is 1 if l[i] is a local extreme and 0 otherwise, I don't need to use >0. I can just let python interpret it as a bool. :) \$\endgroup\$ – undergroundmonorail Feb 27 '14 at 13:53
  • \$\begingroup\$ @wrz I can't figure out how to edit a comment that's already been edited (the pencil icon seems to replace the edit button. is this by design?). I just wanted to add that, if I was smart, I'd have realized that my one-line function didn't need the \n in the declaration at all! That would have saved two characters, but the inclusion of return still makes it not worth it. \$\endgroup\$ – undergroundmonorail Feb 27 '14 at 14:04
2
\$\begingroup\$

Haskell 50

f a=[x|(p,x,n)<-zip3 a(tail a)(drop 2 a),x>p&&x>n]
\$\endgroup\$
  • 1
    \$\begingroup\$ this only check local maximum, for minumum need to add || x<min p n \$\endgroup\$ – karakfa Feb 27 '14 at 19:46
  • \$\begingroup\$ x>p&&x>n has one less character than x>max p n :-) \$\endgroup\$ – yatima2975 Feb 27 '14 at 20:25
  • \$\begingroup\$ space after , is not necessary either. \$\endgroup\$ – karakfa Feb 27 '14 at 21:51
  • 1
    \$\begingroup\$ change x>p&&x>n to (x>p)==(x>n) for local minimums too, adds 4 more chars. \$\endgroup\$ – karakfa Jul 9 '16 at 13:24
2
\$\begingroup\$

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).

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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;}}
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Perl 5 -p, 49 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 43 42 bytes

#~Pick~ArrayFilter[#[[2]]!=Median@#&,#,1]&

Try it online!

I guess Nothing is too long...

#~Pick~                                  &  (* select elements of the input where, *)
       ArrayFilter[                 ,#,1]   (*  when considering the block of length 1 *)
                                            (*    on either side of that element, *)
                   #[[2]]!=Median@#&        (*  its median is not that element *)
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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
)
\$\endgroup\$
0
\$\begingroup\$

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 _ = []
\$\endgroup\$
0
\$\begingroup\$

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}
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ While we're at it, I have a K version, too, in 22 characters: {x@1+&0>2_*':-':0 0,x}. 6 of these characters (2_ and 0 0,) are spent protecting against a length error if the argument is shorter than two items, so if not for that problem it would be 16... The action is also a little different--we have to turn the boolean list into a list of indices with 1+& and use that to index x again--but it's shorter and also a very K-ish thing to do. \$\endgroup\$ – algorithmshark Feb 27 '14 at 15:45
  • \$\begingroup\$ Your K version would beat my APL version then. My code needs at least two numbers. \$\endgroup\$ – user10639 Feb 28 '14 at 9:09
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.