Napisz funkcję lub program, który pobiera listę i tworzy listę ekstremów lokalnych.

Na liście [x_0, x_1, x_2...]lokalna skrajność jest x_itaka, że x_(i-1) < x_ii x_(i+1) < x_ilub x_(i-1) > x_ii x_(i+1) > x_i. Zauważ, że pierwszym i ostatnim elementem listy nigdy nie mogą być ekstremy lokalne.

Tak dla niektórych przykładów

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

To jest kod golfowy, więc wygrywa najkrótszy kod!

Mathematica 66 58 51

Aktualne rozwiązanie

Skrócone dzięki wkładowi Calle.

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

Partition[#,3,1] znajduje tróje.

(a-b) (b-c)<0jest prawdziwe wtedy i tylko wtedy gdy bjest poniżej a, cczy powyżej a, c. i patrzy na znaki różnic. Miejscowy skrajny powróci albo {-1,1}albo {1,-1}.

Przykłady

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}

Wcześniejsze rozwiązanie

Wygląda to na przykłady wszystkich trzech (generowanych przez Partition) i określa, czy środkowy element jest mniejszy niż obie skrajności, czy większy niż skrajności.

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

Pierwsze rozwiązanie

Znajduje to potrójne i patrzy na znaki różnic. Miejscowy skrajny powróci albo {-1,1}albo {1,-1}.

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

Przykład

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}

Analiza :

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}}

% odnosi się do wyniku z odpowiedniej linii poprzedniej.

Differences/@ %

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

Sort@Sign@Differences@x=={-1,1}identyfikuje tróje z {{9, 10, 7}, {10, 7, 6}, {7, 6, 9}, {6, 9, 0}, {9, 0, 3}, {0, 3, 3}, {3, 3, 1}, {3, 1, 10}} tak, że znak (-, 0, +) różnic składa się z a -1i a 1. W niniejszej sprawie są to:

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

Dla każdego z tych przypadków x x[[2]]oznacza drugi termin. Będą to wszystkie lokalne maksima i minima.

{10, 6, 9, 0, 1}

J - 19 znaków

Nic na to nie poradzę;)

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

Wyjaśnienie jest następujące:

• 2-/\] - Przy każdej parze elementów w argumencie (każda 2-elementowa długa infiks) weź różnicę.
• 2*/\ - Teraz nad każdą parą nowej listy weź produkt.
• 0> - Sprawdź, czy każdy wynik jest mniejszy niż 0. Dzieje się tak tylko wtedy, gdy multiplikaty mają naprzemienne znaki, tzn. Nie zdarza się, jeśli mają ten sam znak lub którykolwiek był równy zero.
• 0, - Zadeklaruj, że pierwszy element nie jest elementem skrajnym.
• }: - Odetnij ostatni element, ponieważ to też nie może być ekstremalne.
• #~ - Użyj prawdziwych wartości po prawej stronie, aby wybrać elementy z listy po lewej stronie.

Stosowanie:

   (}:#~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

JavaScript - 62 45 znaków

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

Edytować

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

Ruby, 83 70 60 55 49 znaków

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

Drukuje wszystkie lokalne ekstremy do STDOUT.

Korzysta z <=>operatora „statku kosmicznego”, który bardzo mi się podoba. (Zwraca 1, jeśli pierwsza rzecz jest większa od drugiej, -1, jeśli jest mniejsza, a 0, jeśli jest równa. Dlatego, jeśli dodają do -2 lub 2, oznacza to, że środek jest ekstremalny.)

Już nie, jak zauważył @daniero, że „oczywisty” sposób jest w rzeczywistości krótszy!

Zmieniony jeszcze raz! Teraz wykorzystuje niesamowity algorytm znaleziony w odpowiedzi MT0 (+1 dla niego!).

Również podoba mi się, each_consktóry wybiera każdą ngrupę kolejnych elementów w tablicy. ifCiekawe jest również śledzenie .

Ogólnie podoba mi się to, jak elegancko wygląda.

Niektóre przykładowe przebiegi:

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

C ++ - 208 znaków

Najdłuższe rozwiązanie ponownie:

#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]<<' ';}

Aby użyć, wprowadź liczby całkowite, a następnie dowolny znak, który spowoduje awarię strumienia wejściowego - wszystkie znaki nienumeryczne powinny działać.

Wejście: 0 1 0 x

Wynik: 1

Matlab - 45 bajtów

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

Python 2.7 - 73 bajty

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

Niezbyt imponujące (spójrz na każdy element listy oprócz pierwszego i ostatniego, zobacz, czy jest większy czy mniejszy niż jego sąsiedzi). Przeważnie publikuję to, ponieważ nie wszyscy wiedzą, że możesz to zrobićx<y>z i , by działało. Myślę, że to trochę miłe.

Tak, x<y>zjest fajną funkcją Pythona, ale w tym przypadku nie jest optymalna. Dzięki VX za zwielokrotnienie, które w ogóle mi się nie przydarzyło. Wrzlprmft przypomniał mi, że zadeklarowanie anonimowej funkcji wymaga mniej naciśnięć klawiszy niż def x(y):.

Haskell 50

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

Galaretka , 8 bajtów

IṠIỊ¬T‘ị

Wypróbuj online!

Wyjaśnienie

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

Element jest tylko ekstremum lokalnym, jeśli jego różnica z lewym sąsiadem ma znak przeciwny do różnicy z prawym sąsiadem, tzn. Znaki różnic różnią się o 2 lub -2. Galaretka ma wiele przydatnych prymitywów do radzenia sobie z „znajdowaniem elementów o określonych właściwościach” (w szczególności możemy znaleźć elementy o określonych właściwościach na jednej liście i użyć go do wyodrębnienia elementów z innej listy), co oznacza, że ​​możemy przełożyć z powrotem na oryginalna lista mniej więcej bezpośrednio (wystarczy przesunąć o 1, ponieważ pierwszy i ostatni element oryginalnej listy zagubił się w podejmowaniu różnic).

Python z Numpy - 81 74 67 bajtów ( 61 54 bez importwiersza)

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

Dane wejściowe muszą być tablicą Numpy.

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;}}

awk - 32 znaki

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

Nie mam nadziei na pokonanie takiego języka jak J lub APL w zwięzłości, ale pomyślałem, że i tak wrzucę kapelusz na ring. Wyjaśnienie:

• W danym czasie a, bi cchwyt x_i, x_(i-1)orazx_(i-2)
• b-ci a-bprzybliżenie pochodnej przed i pox_(i-1)
• Jeśli ich produkt jest negatywny, to jeden jest negatywny, a drugi jest pozytywny x_(i-1), dlatego jest to lokalna skrajność, więc drukuj

Brachylog , 17 bajtów

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

Wypróbuj online!

Pobiera dane wejściowe poprzez zmienną wejściową i generuje dane wyjściowe poprzez zmienną wyjściową.

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.

Jeśli można by zagwarantować, że nie ma przebiegów, s₃{{⌉|⌋}.&bh}można zaoszczędzić cztery bajty.

Perl 5 -p , 49 bajtów

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

Wypróbuj online!

Wolfram Language (Mathematica) , 43 42 bajty

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

Wypróbuj online!

Myślę, że Nothingjest za długi ...

#~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 *)

05AB1E , 11 10 bajtów

¥.±¥Ä2Q0šÏ

Wypróbuj online lub sprawdź kilka innych przypadków testowych .

Wyjaśnienie:

¥           # 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)

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;}

Przykładowe użycie:

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

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

Haskell, 70 ° C

Wersja golfowa

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

Wersja bez golfa

-- 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 _ = []

JavaScript: 102 znaki

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}

APL, 19 bajtów

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

Przekształciłem wersję 20 znaków J na APL. Ale dodaję zero na początku i na końcu, zamiast usuwać pierwszą i ostatnią cyfrę. W przeciwnym razie działa tak jak wersja J.

⍵- parametr formalny omega. To jest wejście do funkcji.

Python 2 , 59 bajtów

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

Wypróbuj online!

Ta funkcja pozwala przede wszystkim uniknąć kosztownego indeksowania, przyjmując elementy listy jako argumenty zamiast samej listy. Chociaż na liście pozostaje więcej niż jeden element, rekurencyjnie tworzymy listę, sprawdzając maksimum na każdym kroku.