39
\$\begingroup\$

Given a list of positive integers determine if there is an element that is either greater than its two neighbors or less than its two neighbors (a "bump"). To be clear a bump can never be the first or last item of the list because they only have one neighbor.

Your program should output one of two consistent values each corresponding to either a list with no bumps or a list with bumps. What the values are is unimportant you may choose them yourself.

This is so answers will be scored in bytes with fewer bytes being better.

Test cases

[] -> False
[1] -> False
[1,2] -> False
[1,2,1] -> True
[1,2,2] -> False
[1,2,3] -> False
[1,2,2,1] -> False
[1,2,2,3] -> False
[1,2,1,2] -> True
[1,3,2] -> True
[3,1,2] -> True
[2,2,2] -> False
\$\endgroup\$
  • 5
    \$\begingroup\$ Test Case Request: Numbers other than 0-1-2-3, also negatives allowed/disallowed? \$\endgroup\$ – Magic Octopus Urn Feb 14 '18 at 22:47
  • \$\begingroup\$ Suggested test case: [1,3,3] (ensures that answers using Dennis's algorithm take the sign of the increments rather than just using the increments themselves) \$\endgroup\$ – ETHproductions Feb 15 '18 at 2:39
  • 1
    \$\begingroup\$ @ETHproductions Isn't that already covered by [1,2,2]? Or am I missing something? \$\endgroup\$ – Nic Hartley Feb 15 '18 at 8:13
  • 2
    \$\begingroup\$ @NicHartley, the deltas of [1,2,2] are the same as the signs of those deltas but that's not the case with [1,3,3]. \$\endgroup\$ – Shaggy Feb 15 '18 at 9:54

40 Answers 40

15
\$\begingroup\$

Jelly, 5 bytes

IṠIỊẠ

Returns 0 if there's a bump, 1 if not.

Try it online!

How it works

IṠIỊẠ  Main link. Argument: A (integer array)

I      Increments; take all forward differences of A.
 Ṡ     Take the signs.
       The signs indicate whether the array is increasing (1), decreasing (-1), or
       constant at the corresponding point. A 1 followed by a -1 indicates a local
       maximum, a -1 followed by a 1 a local minimum.
  I    Increments; take the forward differences again.
       Note that 1 - (-1) = 2 and (-1) - 1 = -2. All other seven combinations of
       signs map to -1, 0, or 1.
   Ị   Insignificant; map each difference d to (-1 ≤ d ≤ 1).
    Ạ  All; return 1 if all differences are insignificant, 0 if not.
\$\endgroup\$
  • 1
    \$\begingroup\$ What is "Increments?". What is being incremented and what does that do? \$\endgroup\$ – Sriotchilism O'Zaic Feb 15 '18 at 7:40
  • 1
    \$\begingroup\$ @WheatWizard I think that this is the equivalent of 05AB1E's deltas (¥) command: an array [n0, n1, n2, n3] is poped and the array [n1-n0, n2-n1, n3-n2] is pushed. \$\endgroup\$ – Kaldo Feb 15 '18 at 8:49
10
\$\begingroup\$

JavaScript (ES6), 38 bytes

Returns a boolean.

a=>a.some(x=n=>x*(x=a<n|-(a>(a=n)))<0)

Test cases

let f =

a=>a.some(x=n=>x*(x=a<n|-(a>(a=n)))<0)

console.log(f([]))              // False
console.log(f([1]))             // False
console.log(f([1,2]))           // False
console.log(f([1,2,1]))         // True
console.log(f([1,2,2]))         // False
console.log(f([1,2,3]))         // False
console.log(f([1,2,2,1]))       // False
console.log(f([1,2,2,3]))       // False
console.log(f([1,2,1,2]))       // True
console.log(f([1,3,2]))         // True
console.log(f([2,0,1]))         // True
console.log(f([2,2,2]))         // False
console.log(f([-4,100000,89]))  // True

How?

We use a to store the previous value of n. We set x to 1 if a < n, -1 if a > n or 0 if a = n. And we test whether old_x * x < 0, which is only possible if (old_x = 1 and x = -1) or (old_x = -1 and x = 1).

Because x is initialized to the anonymous callback function of some(), it is coerced to NaN during the first iteration, which makes the test falsy.

\$\endgroup\$
  • \$\begingroup\$ This will throw in strict mode. \$\endgroup\$ – Aluan Haddad Feb 15 '18 at 8:37
  • 2
    \$\begingroup\$ @AluanHaddad Well, 99% of JS golfed code will throw in strict mode just because of undeclared variables. PPCG and codereview doesn't mix well. :P \$\endgroup\$ – Arnauld Feb 15 '18 at 8:51
  • \$\begingroup\$ That's fair, I'm not really much for golf. \$\endgroup\$ – Aluan Haddad Feb 15 '18 at 8:55
  • 4
    \$\begingroup\$ Then why comment on it lol \$\endgroup\$ – Mark C. Feb 16 '18 at 13:11
8
\$\begingroup\$

Haskell, 42 bytes

any(<0).f(*).f(-)
f a b=zipWith a b$tail b

Try it online!

Explanation

First we have the function f that takes a binary function and a list and applies the binary function to every adjacent pair in the list.

Then our main function applies f(-) to the input list. This calculates the difference list. We then apply f(*) to the list to multiply every adjacent pair. Lastly we ask if any pair is less than zero.

A number in the end list can only be negative if it is the product of a negative and positive number from the difference list. Thus in order to produce a negative entry (and then return true) the original list must switch from increasing to decreasing or vice versa, that is it must have a bump.

\$\endgroup\$
  • \$\begingroup\$ Nice way to deal with the empty list! \$\endgroup\$ – Laikoni Feb 15 '18 at 10:05
6
\$\begingroup\$

Python 2, 43 bytes

f=lambda x,y,z,*t:0>(y-x)*(z-y)or f(y,z,*t)

Returns True if there's a bump, errors if there isn't. (allowed by default)

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Octave with Image Package, 34 32 bytes

2 bytes saved thanks to @StewieGriffin!

@(x)0||prod(im2col(diff(x),2))<0

Try it online!

Explanation

Computes consecutive differences, arranges them in sliding blocks of length 2, obtains the product of each block, and tests if any such product is negative.

\$\endgroup\$
  • \$\begingroup\$ 0||prod(...) saves 2 bytes. You could also skip the entire any part, and use the default truthy/falsy definition to save 5 bytes. \$\endgroup\$ – Stewie Griffin Feb 15 '18 at 8:15
  • \$\begingroup\$ Darn, saving 5 bytes will make your solution shorter than mine :( Nice use of the image package. I didn't know it was on TIO. \$\endgroup\$ – Stewie Griffin Feb 15 '18 at 8:31
  • 1
    \$\begingroup\$ @StewieGriffin Since the challenge requires two consistent values I cannot remove any. Thanks for the 0|| idea! \$\endgroup\$ – Luis Mendo Feb 15 '18 at 12:14
4
\$\begingroup\$

R, 48 bytes

function(x)any(apply(embed(diff(x),2),1,prod)<0)

Try it online!

How it works step-by-step using c(1,4,1,4) as example:

> x=c(1,4,1,4)
> diff(x)
[1]  3 -3  3
> embed(diff(x),2)
     [,1] [,2]
[1,]   -3    3
[2,]    3   -3
> apply(embed(diff(x),2),1,prod)
[1] -9 -9
> any(apply(embed(diff(x),2),1,prod)<0)
[1] TRUE

As a bonus, here is a solution of similar length and concept using package zoo:

function(x)any(zoo::rollapply(diff(x),2,prod)<0)
\$\endgroup\$
  • 1
    \$\begingroup\$ neat! Note to self: remember embed exists. It's too bad that rowProds and colProds doesn't exist as aliases in R. \$\endgroup\$ – Giuseppe Feb 15 '18 at 9:53
  • 1
    \$\begingroup\$ @Giuseppe out of desperation i actually checked if they existed :) but indeed just rowSums and rowMeans... \$\endgroup\$ – plannapus Feb 15 '18 at 9:55
  • 1
    \$\begingroup\$ well, at least looking through the docs, .colSums will reshape the input into a matrix based on additional inputs which probably has a golfing application somewhere....now I just have to find one! \$\endgroup\$ – Giuseppe Feb 15 '18 at 9:58
  • \$\begingroup\$ @Guiseppe: Have a look at the functions in matrixStats package. \$\endgroup\$ – Michael M Feb 16 '18 at 8:58
  • \$\begingroup\$ @MichaelM Unfortunately because of the length of the package name it doesn't make it competitive (57 bytes: function(x)any(matrixStats::colProds(embed(diff(x),2)))<0). But for anything other than code golf, this package is indeed a treasure trove. \$\endgroup\$ – plannapus Feb 16 '18 at 9:09
4
\$\begingroup\$

Haskell, 33 bytes

f(p:r@(c:n:_))=(c-p)*(c-n)>0||f r

Try it online!

True if there's a bump, errors if there's not.

\$\endgroup\$
  • \$\begingroup\$ l`zip3`tail l$drop 2l is just a hair shorter. I wonder if pattern matching is somehow even shorter? \$\endgroup\$ – Lynn Feb 14 '18 at 22:55
3
\$\begingroup\$

Perl 6, 39 bytes

{so~(.[1..*]Zcmp$_)~~/'re L'|'s M'/}

Try it online!

$_ is the list argument to this anonymous function. .[1..*] is the same list, but with the first element dropped. Zcmp zips the two lists together with the cmp operator, resulting in a list of Order values. For example, for an input list 1, 2, 2, 2, 1 this would result in the list More, Same, Same, Less.

Now we just need to know whether that list contains two adjacent elements More, Less or Less, More. The trick I used is to convert the list to a space-delimited string with ~, then test whether it contains either substring re L or s M. (The first one can't be just e L because Same also ends with an "e".)

The smart match operator returns either a Match object (if the match succeeded) or Nil (if it didn't), so so converts whatever it is into a boolean value.

\$\endgroup\$
3
\$\begingroup\$

Japt, 9 bytes

ä- ä* d<0

Try it online!

A mashup of Oliver's answer with the approach used by several other answers.

\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 40 bytes

MatchQ[{___,x_,y_,z_,___}/;x<y>z||x>y<z]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Ruby, 55 46 bytes

->a{a.each_cons(3).any?{|x,y,z|(y-x)*(y-z)>0}}

Try it online!

A lambda accepting an array and returning boolean.

-9 bytes: Replace (x<y&&y>z)||(x>y&&y<z) with (y-x)*(y-z)>0 (thanks to GolfWolf)

->a{
  a.each_cons(3)              # Take each consecutive triplet
    .any?{ |x,y,z|            # Destructure to x, y, z
      (y-x)*(y-z) > 0         # Check if y is a bump
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I think you can use | instead of ||, saving you 1 byte. \$\endgroup\$ – Yytsi Feb 15 '18 at 7:19
  • \$\begingroup\$ 46 bytes \$\endgroup\$ – Cristian Lupascu Feb 15 '18 at 9:38
  • \$\begingroup\$ Save 1 byte with '0<(y-x)*y-=z' \$\endgroup\$ – G B Jun 15 '18 at 6:49
3
\$\begingroup\$

PostgreSQL 173 bytes

SELECT DISTINCT ON(a)a,x>j and x>k OR x<least(j,k)FROM(SELECT a,x,lag(x,1,x)OVER(w)j,lead(x,1,x)OVER(w)k FROM d WINDOW w AS(PARTITION BY rn ORDER BY xn))d ORDER BY 1,2 DESC;
     a     | c 
-----------+---
 {1}       | f
 {1,2}     | f
 {1,2,1}   | t
 {1,2,1,2} | t
 {1,2,2}   | f
 {1,2,2,1} | f
 {1,2,2,3} | f
 {1,2,3}   | f
 {1,3,2}   | t
 {2,2,2}   | f
 {3,1,2}   | t
(11 rows)
\$\endgroup\$
  • \$\begingroup\$ Hello and welcome to the site. I'm not familiar with PostgreSQL but you might be able to reduce the amount of whitespace you use. In general most languages don't require most of the kinds of spacing you use. \$\endgroup\$ – Sriotchilism O'Zaic Feb 15 '18 at 21:38
  • \$\begingroup\$ @WheatWizard it's the sample data into the database, it's irrelevant. \$\endgroup\$ – Evan Carroll Feb 15 '18 at 21:45
  • \$\begingroup\$ What's your code then? We don't allow the input to be inserted directly into the code instead of the input. If that is the case here you ought to rewrite it so that it takes input via a standard method. \$\endgroup\$ – Sriotchilism O'Zaic Feb 15 '18 at 21:48
  • \$\begingroup\$ @WheatWizard from the link you provided, codegolf.meta.stackexchange.com/a/5341/23085 \$\endgroup\$ – Evan Carroll Feb 15 '18 at 21:49
  • 1
    \$\begingroup\$ Ok if that's the input format you are using that's fine then. Best of luck golfing here, it's nice to see people golfing in less commonly used languages. \$\endgroup\$ – Sriotchilism O'Zaic Feb 15 '18 at 21:52
3
\$\begingroup\$

Java 8, 108 104 101 86 84 79 72 bytes

a->{int i=a.length,p=0;for(;i-->1;)i|=p*(p=a[i]-a[i-1])>>-1;return-i>1;}

-2 bytes thanks to @OlivierGrégoire.
-13 bytes thanks to @Nevay.

Try it online.

\$\endgroup\$
  • 1
    \$\begingroup\$ 84 bytes. I changed the iteration order (going down), swapped the two multiplication operands and then could remove a superfluous -1. \$\endgroup\$ – Olivier Grégoire Feb 16 '18 at 10:25
  • 1
    \$\begingroup\$ 79 bytes: a->{int i=a.length;for(;i-->2;)i|=(a[i]-a[--i])*(a[i]-a[i-1])>>-1;return-~i|3;} (returns -1 for truthy cases, 3 for falsey cases) - or, if using the presence/absence of an exception as return value 55 bytes: a->{for(int i=0;++i>0;)i|=(a[i-1]-a[i])*(a[i]-a[i+1]);} \$\endgroup\$ – Nevay Feb 18 '18 at 12:58
  • 1
    \$\begingroup\$ 72 bytes: a->{int i=a.length,p=0;for(;i-->1;)i|=p*(p=a[i]-a[i-1])>>-1;return-i>1;} \$\endgroup\$ – Nevay Feb 20 '18 at 13:11
3
\$\begingroup\$

R, 58 56 bytes

function(x)any(abs(diff(sign(diff(c(NA,x)))))>1,na.rm=T)

Try it online!

Saved 2 bytes thanks to Giuseppe

\$\endgroup\$
  • 3
    \$\begingroup\$ You can get rid of the braces {} for -2 bytes. \$\endgroup\$ – Giuseppe Feb 15 '18 at 7:35
  • \$\begingroup\$ additionally, I think that you can port Stewie Griffin's approach for 42 bytes \$\endgroup\$ – Giuseppe Feb 15 '18 at 9:36
  • \$\begingroup\$ @Giuseppe, I think Stewie ported my method, with the difference that mine can properly handle the empty vector as listed in the test cases. Matlab is a bit more lenient with empty vectors compared to R. \$\endgroup\$ – NofP Feb 18 '18 at 15:35
  • \$\begingroup\$ c() is NULL which is not the same as the empty vector of integers, integer(0), whereas in MATLAB [] is a double by default, but if you want to keep it this way, that's perfectly reasonable. \$\endgroup\$ – Giuseppe Feb 20 '18 at 14:42
3
\$\begingroup\$

J, 16 15 bytes

-1 byte thanks to FrownyFrog

1 e.0>2*/\2-/\]

Try it online!

Original: 16 bytes

0>[:<./2*/\2-/\]

2-/\] - differences of each adjacent items

2*/\ - products of each adjacent items

[:<./ - the minimum

0> - is negative?

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Hello ! Could this not be shortened to this simpler explicit form 0><./2*/\2-/\ (13 bytes) ? \$\endgroup\$ – Mathias Dolidon Feb 16 '18 at 14:27
  • \$\begingroup\$ @Mathias Dolidon This works in the interpreter but here in PPCG it's common to provide a function (J verb) if there is some input. If the verb is tacit one, we don't count the assignment f=. bytes. Please have in mind that I'm relatively new user :) \$\endgroup\$ – Galen Ivanov Feb 16 '18 at 14:48
  • \$\begingroup\$ So am I, and you've clarified the rule for me. Thanks ! :) \$\endgroup\$ – Mathias Dolidon Feb 16 '18 at 15:02
  • 1
    \$\begingroup\$ 1 e.0>2*/\2-/\] \$\endgroup\$ – FrownyFrog Mar 3 '18 at 9:19
  • \$\begingroup\$ @ FrownyFrog Thank you! It seems that I rarely use e. :) \$\endgroup\$ – Galen Ivanov Mar 3 '18 at 18:59
2
\$\begingroup\$

Japt, 11 bytes

-5 bytes thanks to @ETHproductions

ä- mÌäa d>1

Try it online! | Test cases

This uses Dennis's algorithm

\$\endgroup\$
2
\$\begingroup\$

Attache, 39 bytes

Any&:&{_*~?Sum[__]}@Slices&2@Sign@Delta

Try it online!

Pretty happy with how this turned out.

Explanation

This is a composition of four functions:

Delta
Sign
Slices&2
Any&:&{_*~?Sum[__]}

Delta gets the differences between elements. =

Then, Sign is applied to each difference, giving us an array of 1s, 0s, and -1s. =

Then, Slices&2 gives all slices of length two from the array, giving all pairs of differences.

Finally, Any&:&{_*~?Sum[__]} is equivalent to, for input x:

Any[&{_*~?Sum[__]}, x]
Any[[el] -> { el[0] and not (el[0] + el[1] = 0) }, x]

This searches for elements which sum to zero but are not zero. If any such pair of elements exist, then there is a bump.

\$\endgroup\$
2
\$\begingroup\$

MATL, 8 bytes

dZSd|1>a

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Husk, 7 bytes

V<0Ẋ*Ẋ-

Try it online!

Explanation

V<0Ẋ*Ẋ-  Implicit input, say [2,5,5,1,4,5,3]
     Ẋ-  Consecutive differences: [3,0,-4,3,1,-2]
   Ẋ*    Consecutive products: [0,0,-12,3,-2]
V<0      Is any of them negative? Return 1-based index: 3
\$\endgroup\$
2
\$\begingroup\$

Octave, 33 bytes

@(x)0||abs(diff(sign(diff(x))))>1

Try it online!

Explanation:

@(x)                           % Anonymous function taking x as input
                  diff(x)       % Takes the difference between consecutive elements
             sign(diff(x))      % The sign of the differences
        diff(sign(diff(x)))     % The difference between the signs
    abs(diff(sign(diff(x)))>1   % Check if the absolute value is 2
@(x)abs(diff(sign(diff(x)))>1   % Output as matrices that are treated truthy or falsy
\$\endgroup\$
2
\$\begingroup\$

Brachylog, 10 bytes

s₃.¬≤₁∧¬≥₁

Try it online!

Succeeds (true.) if there is a bump, and fails (false.) if there is no bump.

Explanation

This is fairly readable already:

s₃.           There is a substring of the input…
  .¬≤₁        …which is not non-decreasing…
      ∧       …and…
       ¬≥₁    …which is not non-increasing
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 7 bytes

¥ü‚P0‹Z

Try it online!

Explanation

¥         # calculate delta's
 ü‚       # pair each element with the next element
   P      # product of each pair
    0‹    # check each if less than 0
      Z   # max
\$\endgroup\$
  • \$\begingroup\$ Wasn't there a 1-byte alternative to 0‹ that basically checks the number for a negative sign? \$\endgroup\$ – Magic Octopus Urn Feb 16 '18 at 15:33
  • \$\begingroup\$ @MagicOctopusUrn: d used to check that top of stack only contained [0-9], which is the opposite of what we want here. But now it's more intelligent and negative/floats are also counted as numbers. \$\endgroup\$ – Emigna Feb 16 '18 at 15:39
  • \$\begingroup\$ Ahhhh... coulda sworn a saw the negative sign and returned true or something... But I think you're right, I'm remembering your d trick. \$\endgroup\$ – Magic Octopus Urn Feb 16 '18 at 15:48
2
\$\begingroup\$

Brachylog, 10 bytes

s₃s₂ᶠ-ᵐ×<0

Try it online!

Not nearly as neat and elegant as @Fatalize's existing 10 byte answer, but it works!

s₃   % There exists a substring of three elements [I,J,K] in the array such that

s₂ᶠ  % When it's split into pairs [[I,J],[J,K]]

-ᵐ   % And each difference is taken [I-J, J-K]

×    % And those differences are multiplied (I-J)*(J-K)
     % (At a bump, one of those will be negative and the other positive. 
     % At other places, both differences will be positive, or both negative, 
     %  or one of them 0 - ultimately resulting in a non-negative product.)

<0   % The product is negative
\$\endgroup\$
1
\$\begingroup\$

Husk, 9 bytes

▼mεẊ-Ẋo±-

Try it online!

Uses Dennis's algorithm.

\$\endgroup\$
1
\$\begingroup\$

Perl 5, 54 + 2 (-pa) = 56 bytes

map$\|=$F[$_-1]!=(sort{$a-$b}@F[$_-2..$_])[1],2..$#F}{

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 2, 60 bytes

lambda l:any(p>c<n or p<c>n for p,c,n in zip(l,l[1:],l[2:]))

Try it online!

Pretty much the same thing, thought it would be shorter though...

Python 2, 63 bytes

f=lambda l:l[3:]and(l[0]>l[1]<l[2]or l[0]<l[1]>l[2]or f(l[1:]))

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ 58 bytes using multiplication instead \$\endgroup\$ – Shieru Asakoto Feb 15 '18 at 7:49
1
\$\begingroup\$

Pyt, 11 7 bytes

₋ʁ*0<Ʃ±

Outputs 1 if there is a bump, 0 otherwise

Try it online!

Port of Wheat Wizard's Haskell answer


Old way (11 bytes):

₋±₋Å1≤ĐŁ↔Ʃ=

Try it online!

Returns False if there is a bump, True otherwise

Port of Dennis' Jelly answer

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 37 36 bytes

FreeQ[(d=Differences)@Sign@d@#,-2|2]&

Gives the opposite of the test case answers (False and True reversed). Prepend a ! to switch to the normal form.

OR

Abs@(d=Differences)@Sign@d@#~FreeQ~2&

Also reversed output, so replace FreeQ with MatchQ for normal form.

Explanation: Take the sign of the differences of the sequence. Iff the resulting sequence includes {1,-1} or {-1,1} there is a bump. The absolute value the differences of {1,-1} or {-1,1} is 2 in either case.

Shave off another byte by squaring the final list instead of taking the absolute value:

FreeQ[(d=Differences)@Sign@d@#^2,4]&

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Perl, 35 bytes

Includes +3 for -p

bump.pl:

#!/usr/bin/perl -p
s%\S+ %$a*1*($a=$&-$')%eg;$_=/-/

Run as:

bump.pl <<< "3 1 2"
\$\endgroup\$
1
\$\begingroup\$

Julia 0.6, 57 56 bytes

l->any(p>c<n||p<c>n for(p,c,n)=zip(l,l[2:end],l[3:end]))

Basically just totallyhuman's python answer. -1 byte from user71546

Try it online!

Julia 0.6, 39 bytes

f(x,y,z,a...)=x>y<z||x<y>z||f(y,z,a...)

Lispy recursion style, aka Dennis's python answer. Returns true when a bump exists, otherwise throws an error. This should maybe be 42 bytes since you have to splat it when calling. Eg for a=[1,2,1] you call as f(a...). f(a)=f(a...) would remove that need, but is longer. I need to get better a recursion, and I don't really like writing code that throws an error.

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ seems the space after for is not necessary ;) \$\endgroup\$ – Shieru Asakoto Feb 15 '18 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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