Список положительных целых чисел можно представить в виде квантованного горного хребта, где каждая запись списка представляет высоту одного вертикального участка гор.

Например, список

1, 2, 2, 3, 4, 3, 5, 3, 2, 1, 2, 3, 3, 3, 2, 2, 1, 3

может стать ассортиментом

      x
    x x      
   xxxxx   xxx   x
 xxxxxxxx xxxxxx x
xxxxxxxxxxxxxxxxxx

(Менее поэтические люди могли бы назвать это гистограммой, но я отвлекся.)

Вопрос в этой задаче: сколько пиков в горном массиве какого-то произвольного списка? По сути, сколько локальных максимумов в списке?

Пик определяется как непрерывный участок одного или нескольких столбцов горного хребта, которые все равны по высоте, где столбцы непосредственно слева и справа имеют меньшую высоту.

Легко увидеть, что в примере есть четыре пика в этих скобках:

1, 2, 2, 3, (4), 3, (5), 3, 2, 1, 2, (3, 3, 3), 2, 2, 1, (3)

Обратите внимание, как участок (3, 3, 3)плато считается пиком, потому что это непрерывный набор столбцов, равных по высоте, выше, чем его соседние столбцы.

Последнее также (3)считается пиком, потому что для целей этой задачи мы определим левого соседа самого левого столбца и правого соседа самого правого столбца равными нулю высоты.

Это означает , что список только с одним значением, например 1, 1, 1, может быть интерпретирован как 0, 1, 1, 1, 0и , таким образом , имеет один пик, а не никто: 0, (1, 1, 1), 0.

Единственный список с нулевыми пиками - это пустой список.

Вызов

Напишите функцию или программу, которая принимает произвольный список натуральных чисел и печатает или возвращает количество пиков в соответствующей горной цепи.

Самый короткий код в байтах побеждает. Tiebreaker - более ранний пост.

Тестовые случаи

Input List -> Output Peak Count

[empty list] -> 0
1, 1, 1 -> 1
1, 2, 2, 3, 4, 3, 5, 3, 2, 1, 2, 3, 3, 3, 2, 2, 1, 3 -> 4
1 -> 1
1, 1 -> 1
2, 2, 2, 2, 2 -> 1
90 -> 1
2, 1, 2 -> 2
5, 2, 5, 2, 5 -> 3
2, 5, 2, 5, 2, 5, 2 -> 3
1, 2, 3, 4 -> 1
1, 2, 3, 4, 1, 2 -> 2
1, 3, 5, 3, 1 -> 1
7, 4, 2, 1, 2, 3, 7 -> 2
7, 4, 2, 1, 2, 1, 2, 3, 7 -> 3
1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2 -> 10
1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1 -> 10
2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2 -> 10
1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 3, 3, 1 -> 4
12, 1, 2, 1, 2, 3, 3, 3, 2, 4, 4, 4, 1, 5, 5, 4, 7, 9 -> 6
87, 356, 37673, 3676, 386, 909, 909, 909, 909, 454, 909, 909 -> 3
87, 356, 37673, 3676, 386, 909, 909, 909, 909, 454, 909, 908, 909 -> 4

Pyth, 18 байт

su_>VGtG2eMr++ZQZ8

На основе @ PeterTaylor повторяется больше, чем решение, но с изюминкой.

++ZQZ: Добавить нули с обеих сторон.

eMr ... 8: Удалить повторы.

u ... 2 ...: Примените следующее дважды:

>VGTG: Сопоставить каждую пару чисел с тем, находятся ли они в порядке убывания.

_И наоборот.

1 на выходе соответствует 1, 0предыдущему шагу, который соответствует a < b > cвходу из-за обращения.

s: Сумма (и печать)

CJam ( 32 26 24 21 байт)

0q~0]e`1f=2ew::>2,/,(

Ожидаемый ввод - разделенные пробелами числа.

Онлайн демо ; полный набор тестов (ожидаемый результат для 1каждого теста).

Спасибо Мартину за сообщение, что текущая версия CJam улучшает один из используемых операторов, сохраняя 2 символа; и для дальнейшего сохранения 3-х символов.

рассечение

Две фазы: дедупликация, затем определение локальных максимумов в каждом наборе из трех.

0q~0]      e# Put the input in an array wrapped in [0 ... 0]
e`1f=      e# Use run-length encoding to deduplicate
2ew::>     e# Map [a b c ...] to [(a>b) (b>c) ...]
2,/        e# Split on [0 1], which since we've deduplicated occurs when (a<b) (b>c)
,(         e# Count the parts and decrement to give the number of [0 1]s

JavaScript (ES6), 54 51 байт

m=>m.map(n=>{h=n<p?h&&!++r:n>p||h;p=n},r=h=p=0)|r+h

объяснение

Принимает массив чисел

m=>
  m.map(n=>{       // for each number n in the mountain range
      h=
        n<p?       // if the number is less than the previous number:
          h&&      // if the previous number was greater than the number before it
          !++r     // increment the number of peaks and set h to 0
        :n>p||h;   // if the number is greater than the previous number, set h to 1
      p=n          // set p to the current number
    },
    r=             // r = number of peaks
    h=             // h = 1 if the previous number was higher than the one before it
    p=0            // p = previous number
  )|r+h            // return the output (+ 1 if the last number was higher)

Тест

var solution = m=>m.map(n=>{h=n<p?h&&!++r:n>p||h;p=n},r=h=p=0)|r+h

Mountain Range (space-separated) = <input type="text" id="input" value="87 356 37673 3676 386 909 909 909 909 454 909 908 909" />
<button onclick="result.textContent=solution(input.value.split(' ').map(n=>+n))">Go</button>
<pre id="result"></pre>

Pyth, 25 23 байта

L._M-M.:b2s<R0y-y+Z+QZZ

Объяснение:

L              y = lambda b:
  ._M -M .:          signs of subsets
           b          of b
           2          of length 2. That is, signs of differences.

s <R              number of elements less than
     0              0 in
     y -            y of ... with zeroes removed
         y +          y of
             Z        the input with zeroes tacked on both sides
             + Q Z
       Z              

Юлия, 66

x->(y=diff([0;x;0]);y=y[y.!=0];sum((y[1:end-1].>0)&(y[2:end].<0)))

Pad, дифференцируются: y=diff([0;x;0]).
Игнорировать плато y=y[y.!=0].
Граф +до -пересечения нуля: sum((y[1:end-1].>0)&(y[2:end].<0)).

MATLAB, 29 27 байт

@(a)nnz(findpeaks([0 a 0]))

Анонимная функция, которая находит пики в данных и подсчитывает их количество. 0 добавляется и добавляется к данным, чтобы гарантировать, что пики на самых краях обнаружены в соответствии с вопросом.

Это также будет работать с Octave . Вы можете попробовать онлайн здесь . Просто вставьте приведенный выше код в командную строку, а затем запустите его с ans([1,2,1,3,4,5,6,1])(или любым другим вводом).

Поскольку числа всегда + ve, мы можем предположить, что они больше нуля, поэтому можем сохранить 2 байта, используя nnzвместо numel.

Python 3, 75 байт

def m(t):
 a=p=d=0
 for n in t+[0]:a+=(n<p)&d;d=((n==p)&d)+(n>p);p=n
 return a

Это мой первый Codegolf, поэтому могут быть некоторые места, чтобы сократить его, особенно d=((n==p)&d)+(n>p)часть. Однако это работает на всех тестовых случаях

Mathematica, 42 36 33 32 байта

Спасибо Мартину Бюттнеру за сохранение 1 байта.

Tr@PeakDetect[#&@@@Split@#,0,0]&

PeakDetect просто делает почти все!

Тестовые случаи:

Total@PeakDetect[#&@@@Split@#,0,0]&@{12,1,2,1,2,3,3,3,2,4,4,4,1,5,5,4,7,9}
(* 6 *)
Total@PeakDetect[#&@@@Split@#,0,0]&@{87,356,37673,3676,386,909,909,909,909,454,909,908,909}
(* 4 *)

CJam, 27 26 байтов

A0q~0A]e`1f=3ew{~@e>>}%1e=

Использует кодирование длины серии для удаления дубликатов. После этого мы проверяем для каждого триплета, является ли средний самый большой номер.

Попробуй это здесь! Проходит тестовый набор Питера Тейлора .

MATL , 22 байта

0ih0hdZS49+c'21*?0'XXn

Использует текущую версию языка / компилятора.

пример

>> matl
 > 0ih0hdZS49+c'21*?0'XXn
 >
> [1, 2, 2, 3, 4, 3, 5, 3, 2, 1, 2, 3, 3, 3, 2, 2, 1, 3]
4

объяснение

0ih0h           % input array. Append and prepend 0
dZS             % sign of difference between consecutive elements. Gives -1, 0, 1
49+c            % convert to a string of '0','1','2' 
'21*?0'XX       % use (lazy) regular expression to detect peaks: '20' or '210' or '2110'...
n               % number of matches. Implicity print

Mathematica, 55 39 36 35 байт

Length@FindPeaks[#&@@@Split@#,0,0]&

Теперь работает на всех тестовых случаях!

Retina , 33 31 байт

Спасибо Нейлу за сохранение 2 байта.

\b(1+)(?<!\1,\1)(,\1)*\b(?!,\1)

Попробуйте онлайн!

Принимает ввод как разделенный запятыми унарный список.

JavaScript ES6, 96 94 байта

t=>(a=t.filter((x,i)=>x!=t[i-1])).filter((x,i)=>(x>(b=a[i-1])||!b)&&(x>(c=a[i+1])||!c)).length

Принцип: разложите плато в одиночные пики, найдите пики, которые определены как выше, чем следующий и предыдущий элементы.

Принимает ввод в виде массива.

Демо-версия:

f=t=>
(a=t.filter((x,i)=>x!=t[i-1]))    //collapse every plateau into the pick
    .filter((x,i)=>
       (x>(b=a[i-1])||!b)&&(x>(c=a[i+1])||!c)    //leave only those values which are greater than the succeeding and preceding ones
    ).length

document.write(
  f([])+"<br>"+
  f([1, 1, 1])+"<br>"+
  f([1, 2, 2, 3, 4, 3, 5, 3, 2, 1, 2, 3, 3, 3, 2, 2, 1, 3])+"<br>"+
  f([1])+"<br>"+
  f([1, 1])+"<br>"+
  f([2, 2, 2, 2, 2])+"<br>"+
  f([90])+"<br>"+
  f([2, 1, 2])+"<br>"+
  f([5, 2, 5, 2, 5])+"<br>"+
  f([2, 5, 2, 5, 2, 5, 2])+"<br>"+
  f([1, 2, 3, 4])+"<br>"+
  f([1, 2, 3, 4, 1, 2])+"<br>"+
  f([1, 3, 5, 3, 1])+"<br>"+
  f([7, 4, 2, 1, 2, 3, 7])+"<br>"+
  f([7, 4, 2, 1, 2, 1, 2, 3, 7])+"<br>"+
  f([1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2])+"<br>"+
  f([1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1])+"<br>"+
  f([2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2])+"<br>"+
  f([1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 3, 3, 1])+"<br>"+
  f([12, 1, 2, 1, 2, 3, 3, 3, 2, 4, 4, 4, 1, 5, 5, 4, 7, 9])+"<br>"+
  f([87, 356, 37673, 3676, 386, 909, 909, 909, 909, 454, 909, 909])+"<br>"+
  f([87, 356, 37673, 3676, 386, 909, 909, 909, 909, 454, 909, 908, 909])
)

ES6, 50 48 байтов

m=>m.map(h=>{f=h>p?c+=!f:f&&h==p;p=h},p=c=f=0)|c

Сохранено 2 байта благодаря @ user81655.

Ungolfed:

function peaks(mountains) {
    var previous = 0;
    var count = 0;
    var plateau = false;
    for (var height of mountains) {
        if (height > previous) {
            if (!plateau) count++;
            plateau = true;
        } else if (height != previous) {
            plateau = false;
        }
    }
    return count;
}

МАТЛ, 23

Поскольку нам нужно использовать esolangs на основе стека, чтобы быть конкурентоспособными, я переопределил свое решение Julia в MATL.

0i0hhdtg)t5L)0>w6L)0<*s

Нажмите 0, введите 0, объедините дважды. 0i0hh=>x = [0, input(''), 0]

Дифференцировать. d=>x = diff(x)

Дублируйте t, конвертируйте одно в логическое значение и используйте его для индексации другого. tg)=>x=x(x!=0)

Дублируйте снова. t

Первый: [1,G])0>=>y1 = x(1:end-1)>0

Обмен. w

Второе: [2,0])0<=>y2 = x(2:end)<0

Логика и подсчитайте правдивые ценности. *s=>sum(y1 & y2)

Japt, 19 байт

Это было проще, чем я думал, но начало немного расточительно из-за ошибки.

Uu0;Up0 ä< ä> f_} l

Попробуйте онлайн!

Как это работает

Uu0;Up0 ä< ä> f_} l  // Implicit: U = input
Uu0;Up0              // Add 0 to the beginning and end of U. If this isn't done, the algorithm fails on peaks at the end.
        ä<           // Compare each pair of items, returning true if the first is less than the second, false otherwise.
                     // This leaves us with a list e.g. [true, false, false, true, false].
           ä>        // Repeat the above process, but with greater-than instead of less-than.
                     // JS compares true as greater than false, so this returns a list filled with false, with true wherever there is a peak.
              f_} l  // Filter out the falsy items and return the length.

Неконкурентная версия, 15 байт

Uu0 p0 ä< ä> è_

Ранее сегодня я добавил èфункцию, которая похожа, fно возвращает количество совпадений, а не сами совпадения. Я также исправил ошибку, при которой Array.uвозвращалась бы длина массива, а не сам массив.

Попробуйте онлайн!

05AB1E , 9 байтов

Ô0.ø¥0‹ÔO

Попробуйте онлайн!

Объяснение:

Ô0.ø¥0‹ÔO      Full program
Ô              Uniquify (= remove plateaus)
 0.ø           Surround with zeros
    ¥          Push deltas
     0‹        Test each element if lower than 0
               --- we now have a list with 0's (= going uphill) and 
                   1's (going downhill). Since we removed plateaus, all
                   we have to do now is to count the number of ramps
                   going downhill
       Ô       Uniquify (reduce ramps to length 1)
        O      Total sum of the list

Желе , 27 байт

ṡ2EÐḟFs2ḣ€1S€ṡ3M€Fċ2
0;⁸;0Ç

Попробуйте онлайн!

GolfScript, 35

~0+0\{.@=!},+:a,2-,{a\>3<.$2=?1=},,

Тест онлайн

В основном удаляет дубликаты, добавляет 0 к обоим концам и проверяет, сколько троек имеет максимум в центре.

Java 8, 141 байт

l->{int r=0,i=1,t;for(l.add(0,0),l.add(0);i<l.size()-1;r+=t>l.get(i-1)&t>l.get(++i)?1:0)for(;(t=l.get(i))==l.get(i+1);)l.remove(i);return r;}

Вероятно, можно использовать другой подход или использовать массив в качестве входных данных вместо List.

Объяснение:

Попробуй это здесь.

l->{                     // Method with ArrayList<Integer> parameter and int return-type
  int r=0,               //  Result-integer
      i=1,               //  Index-integer
      t;                 //  Temp integer
  for(l.add(0,0),        //  Add a 0 at the start of the list
      l.add(0);          //  Add a 0 at the end of the list
      i<l.size()-1;      //  Loop (1) from index 1 through length-1 (0-indexed)
      r+=                //    After every iteration, raise the result-integer by:
         t>l.get(i-1)    //     If the current item is larger than the previous
         &t>l.get(++i)?  //     and larger than the next:
          1              //      Increase `r` by 1
         :               //     Else:
          0)             //      `r` remains the same
    for(;(t=l.get(i))==l.get(i+1);
                         //   Inner loop (2) as long as there are two adjacent equal items
      l.remove(i)        //    And remove one of those two equal integers
    );                   //   End of inner loop (2)
                         //  End of loop (1) (implicit / single-line body)
  return r;              //  Return the result-integer
}                        // End of method