How many peaks in my mountain range?

Question

A list of positive integers can be visualized as a quantized mountain range where each list entry represents the height of one vertical section of the mountains.

For example, the list

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

can become the range

      x
    x x      
   xxxxx   xxx   x
 xxxxxxxx xxxxxx x
xxxxxxxxxxxxxxxxxx

(Less poetic people might call this a bar chart, but I digress.)

The question in this challenge is: How many peaks are in the mountain range of some arbitrary list? Essentially, how many local maxima are in the list?

A peak is defined as a contiguous section of one or more columns of the mountain range that are all equal in height, where the columns immediately to the left and the right are lower in height.

It's easy to visually tell that the example has four peaks at these parenthesized locations:

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

Note how the (3, 3, 3) plateau section counts as a peak because it is a contiguous set of columns equal in height, higher than its neighboring columns.

The last (3) counts as a peak as well because, for the purposes of this challenge, we'll define the left neighbor of the leftmost column and the right neighbor of the rightmost column to both be height zero.

This means that a list with only one value, for example 1, 1, 1, can be interpreted as 0, 1, 1, 1, 0, and thus has one peak, not none: 0, (1, 1, 1), 0.

The only list with zero peaks is the empty list.

Challenge

Write a function or program that takes in an arbitrary list of positive integers and prints or returns the number of peaks in the corresponding mountain range.

The shortest code in bytes wins. Tiebreaker is earlier post.

Test Cases

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

Answer 1

CJam (32 26 24 21 bytes)

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

Expected input is space-separated numbers.

Online demo ; full test suite (expected output is a 1 per test case).

Thanks to Martin for informing me that the current version of CJam improves one of the operators used, saving 2 chars; and for a further 3-char saving.

Dissection

Two phases: deduplicate, then identify local maxima in each set of three.

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

Answer 2

JavaScript (ES6), 54 51 bytes

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

Explanation

Takes an array of numbers

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)

Test

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>

Answer 3

Pyth, 25 23 bytes

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

Explanation:

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              

Answer 4

Julia, 66

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

Pad, differentiate: y=diff([0;x;0]).
Ignore the plateaus: y=y[y.!=0].
Count + to - zero crossings: sum((y[1:end-1].>0)&(y[2:end].<0)).

Answer 5

MATLAB, 29 27 bytes

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

Anonymous function which finds the peaks in the data and counts how many there are. 0 is prepended and appended to the data to ensure peaks at the very edges are detected as per the question.

This will also work with Octave. You can try online here. Simply paste the above code into the command line, and then run it with ans([1,2,1,3,4,5,6,1]) (or whatever other input).

---

As the numbers are always +ve, we can assume they are greater than zero, so can save 2 bytes by using nnz instead of numel.

Answer 6

Python 3, 75 bytes

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

This is my first codegolf so there may be some places to cut down on it, especially the d=((n==p)&d)+(n>p) part. However it works on all the test cases

Answer 7

Mathematica, 42 36 33 32 bytes

Thanks to Martin Büttner for saving 1 byte.

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

PeakDetect just does almost everything!

Test cases:

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

Answer 8

Pyth, 18 bytes

su_>VGtG2eMr++ZQZ8

Based on @PeterTaylor's repeated greater than solution, but with a twist.

++ZQZ: Add zeros on both sides.

eMr ... 8: Remove repeats.

u ... 2 ...: Apply the following twice:

>VGTG: Map each pair of numbers to whether they are in decreasing order.

_: And reverse.

A 1 in the output corresponds to a 1, 0 in prior step, which corresponds to a < b > c in the input due to the reversal.

s: Sum (and print)

Answer 9

CJam, 27 26 bytes

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

Uses the run length coding to remove duplicates. After that we check for every triplet if the middle one is the largest number.

Try it here! Passes Peter Taylor's test suite.

Answer 10

MATL, 22 bytes

0ih0hdZS49+c'21*?0'XXn

Uses current version of the language/compiler.

Example

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

Explanation

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

Answer 11

Mathematica, 55 39 36 35 bytes

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

Now works on all of the test cases!

Answer 12

Retina, 33 31 bytes

Thanks to Neil for saving 2 bytes.

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

Try it online!

Takes input as a comma-separated, unary list.

Answer 13

JavaScript ES6, 96 94 bytes

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

Principle: collapse plateaus into single peaks, find the picks which are defined as being higher than both next and previous elements.

Takes input as an array.

Demo:

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

Answer 14

ES6, 50 48 bytes

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

Saved 2 bytes thanks to @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;
}

Answer 15

MATL, 23

Since we need to use stack based esolangs to be competitive, I reimplemented my Julia solution in MATL.

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

Push 0, input, 0, concatenate twice. 0i0hh => x = [0, input(''), 0]

Differentiate. d => x = diff(x)

Duplicate t, convert one to boolean and use it to index the other. tg) => x=x(x!=0)

Duplicate again. t

First: [1,G])0> => y1 = x(1:end-1)>0

Exchange. w

Second: [2,0])0< => y2 = x(2:end)<0

Logic and, count the truthy values. *s => sum(y1 & y2)

Answer 16

Japt, 19 bytes

That was easier than I thought, but the beginning is slightly wasteful due to a bug.

Uu0;Up0 ä< ä> f_} l

Try it online!

How it works

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.

Non-competing version, 15 bytes

Uu0 p0 ä< ä> è_

Earlier today, I added the è function, which is like f but returns the number of matches rather than the matches themselves. I also fixed a bug where Array.u would return the length of the array rather than the array itself.

Try it online!

Answer 17

05AB1E, 9 bytes

Ô0.ø¥0‹ÔO

Try it online!

Explanation:

Ô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

Answer 18

Jelly, 27 bytes

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

Try it online!

Answer 19

Japt, 14 bytes

iT òÎmÎä> ò> l

Try it (includes all test cases)

Accommodating the empty array cost 2 bytes.

iT òÎmÎä> ò> l     :Implicit input of array
iT                 :Prepend 0
   ò               :Partition between elements where
    Î              :  The sign of their difference is truthy (not 0)
     m             :Map
      Î            :  First element
       ä>          :Consecutive pairs reduced by >
          ò>       :Partition after elements that are greater than the next
             l     :Length

Answer 20

Husk, 11 bytes

#←gẊo±>m←gΘ

Try it online!

#←gẊo±>m←gΘ
#               # how many truthy elements in list of
 ←              # first element of each sublist of
  g             # grouped identical elements of
   Ẋ            # apply to each pair in list
    o±>         # sign of greater than (1 if greater than, 0 otherwise)
       m←       # make list from first element of each sublist of
         g      # grouped identical elements of
          Θ     # input prepended with zero

Answer 21

GolfScript, 35

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

Test online

Basically removes duplicates, adds a 0 to both ends, and checks how many triples have a maximum in the center.

Answer 22

Java 8, 141 bytes

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

Can probably be golfed by using a different approach, or an array as input instead of List.

Explanation:

Try it here.

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

Answer 23

Python 3, 68 bytes

f=lambda a,*b,p=0:(p<a>[*b,0][0])+(len(b)and f(*b,p=[p,a][a!=b[0]]))

Try it online!

Answer 24

><> (Fish), 59 bytes

0i:0(?v:@)$!
v&01~~/
l
1
-
?
\?v  >^&+\ 
& \:?^v
\n;   \&1/

Try it online! - Animated Version

Explanation

Green: Read the input, push 1 if the value is less than the previous, 0 if it's more. Add a 0 and a 1 to the ends of the stack. Set the register to 0.

Blue: While the stack is not empty, check for a 0 followed by a 1. If so increment the register. In all other cases just pop a value.

Yellow: Print the result when the stack is empty.