Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
share|improve this question
    
So, the plateau can be arbitrary long? – nicael Jan 9 at 8:04
    
@nicael Yes, it could be – Helka Homba Jan 9 at 8:05
    
Can we take input as an array, not as string? – nicael Jan 9 at 8:26
    
@nicael Yes, anything reasonable – Helka Homba Jan 9 at 8:28

17 Answers 17

up vote 2 down vote accepted

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)

share|improve this answer

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

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>

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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              
share|improve this answer
    
Nice. Unusually, a port to CJam is shorter: 0q~0]{2ew::-:g0-}2*1-, for 22. – Peter Taylor Jan 9 at 20:50

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.

share|improve this answer

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.

share|improve this answer

Retina, 33 bytes

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

Takes input as a space-separated, unary list.

Try it online! Or use this version which takes care of the decimal to unary conversion.

share|improve this answer

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 *)
share|improve this answer
    
I find my answer to be sufficiently different from yours to post another one. – LegionMammal978 Jan 9 at 12:25
    
@LegionMammal978 The result of input {1} is 1, as is expected. – njpipeorgan Jan 9 at 12:41
    
I mean {1, 2, 2, 3, 4, 3, 5, 3, 2, 1, 2, 3, 3, 3, 2, 2, 1, 3} – LegionMammal978 Jan 9 at 12:42
    
@LegionMammal978 That's tricky. I've not find a solution. – njpipeorgan Jan 9 at 12:54
    
My updated solution just flattens "plateaus". – LegionMammal978 Jan 9 at 12:55

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

share|improve this answer

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;
}
share|improve this answer
    
@user81655 Thanks for drawing my attention to that subtlety. (I've not used .map()| before.) – Neil Jan 9 at 18:04

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

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)

share|improve this answer
    
Or you could you Pyth, a procedural/functional golfing language! – isaacg Jan 9 at 18:58
    
OK, MATL is MATLAB for golfing, but MATLAB is beating MATL. – Generic User Jan 9 at 19:10
    
Very nice! Some tips: [1,G] --> 5L saves 3 bytes. [2,0] --> 6L saves 3 bytes – Luis Mendo Jan 10 at 4:54
1  
@GenericUser Not anymore :-) codegolf.stackexchange.com/a/69050/36398 – Luis Mendo Jan 10 at 5:08
    
@Rainer I'm thinking of removing and (&) from MATL (and same for or). It can always be replaced by *o, and often by just *, as in this case. What do you think? That way the characters & and | could be used for other functions in the future. – Luis Mendo Jan 10 at 13:10

Mathematica, 55 39 36 35 bytes

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

Now works on all of the test cases!

share|improve this answer
    
Cool! But FindPeaks[#,0,0,-∞] is needed, otherwise it fails for the last test case. – njpipeorgan Jan 9 at 12:30
    
Last/@ saves a byte. And the last ",0" might be unnecessary? – njpipeorgan Jan 9 at 13:14
    
Same trick for you: Last/@ --> #&@@@ – Martin Ender Jan 12 at 10:34

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.

share|improve this answer

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!

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.