Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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!

share|improve this question
    
To make sure I understand correctly: Numbers greater than the numbers on either side? –  undergroundmonorail Feb 26 at 21:57
    
@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 –  jozefg Feb 26 at 21:57
    
Oh, I see. I misread it –  undergroundmonorail Feb 26 at 21:58
2  
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... –  V-X Feb 27 at 13:08

15 Answers 15

up vote 6 down vote accepted

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}

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

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)
share|improve this answer
1  
Wow, that's an awesome algorithm! :D +1 –  Doorknob Feb 27 at 2:43

J - 20 char

Couldn't help it ;)

(}.@}:#~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.
  • }.@}: - Cut off the first and the last element, because those can't possibly be extrema, and we lost information for them anyway by doing the pairs stuff above.
  • #~ - Use the true values on the right side to pick items from the list on the left side.

Usage:

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

   (}.@}:#~0>2*/\2-/\]) 3 4 4 4 2 5
2
share|improve this answer
    
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. –  Lord Soth Feb 27 at 1:19
    
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. –  Lord Soth Feb 27 at 1:21
    
Good catch, and yes, this saves two characters. Updating. –  algorithmshark Feb 27 at 1:50

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
share|improve this answer
    
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}} –  daniero Feb 27 at 1:58
    
@daniero Thanks; I didn't even know you could do that! Edited –  Doorknob Feb 27 at 2:03
    
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) ;) –  daniero Feb 27 at 2:20
    
also... !((x..z)===y) is even shorter though not as clever –  Not that Charles Feb 27 at 2:25
    
@Charles That fails when x < z. –  Doorknob Feb 27 at 2:31

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

share|improve this answer
    
You can use a deque instead of a vector to gain 2 characters. –  Morwenn Feb 27 at 10:01
    
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. –  Morwenn Feb 27 at 10:02
    
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. –  Morwenn Feb 27 at 10:04
    
@Morwenn Thanks. –  hosch250 Feb 27 at 16:39

Matlab - 45 bytes

x=input('');y=diff(x);x(find([0 y].*[y 0]<0))
share|improve this answer

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

share|improve this answer
    
It’s shorter to use the lambda operator. –  Wrzlprmft Feb 27 at 10:06
    
if(l[i]-l[i-1])*(l[i]-l[i+1])>0 would reduce the code by 11 characters... –  V-X Feb 27 at 13:25
    
@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! –  undergroundmonorail Feb 27 at 13:53
    
@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. :) –  undergroundmonorail Feb 27 at 13:53
    
@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. –  undergroundmonorail Feb 27 at 14:04

Haskell 52

f a=[x|(p,x,n)<-zip3 a(tail a)(drop 2 a), x>max p n]
share|improve this answer
1  
this only check local maximum, for minumum need to add || x<min p n –  karakfa Feb 27 at 19:46
    
x>p&&x>n has one less character than x>max p n :-) –  yatima2975 Feb 27 at 20:25
    
space after , is not necessary either. –  karakfa Feb 27 at 21:51

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.

share|improve this answer

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;}}
share|improve this answer

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
)
share|improve this answer

APL - 19 chars

{⍵/⍨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.

share|improve this answer
    
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. –  algorithmshark Feb 27 at 15:45
    
Your K version would beat my APL version then. My code needs at least two numbers. –  user10639 Feb 28 at 9:09

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
share|improve this answer

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 _ = []
share|improve this answer

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}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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