22
\$\begingroup\$

Challenge

Given a list, determine if grouping the list into runs of increasing and decreasing elements will result in a list of equal-sized lists.

In other words, "turning points" of the list are spaced out evenly.

Example

Here's an example: 0, 3, 7, 5, 2, 3, 6

0, 3, 7 increases, 7, 5, 2 decreases, and 2, 3, 6 increases. Therefore this is truthy.

Another example: 1, 4, 6, 8, 5, 3, 5, 7, 9

1, 4, 6, 8 increases, 8, 5, 3 decreases, and 3, 5, 7, 9 increases. Therefore this is falsy.

Rules and Specifications

  • No adjacent elements will be equal
  • All numbers can be assumed to be within your language's reasonable number range
  • You may assume that all numbers are integers, if it helps you golf your submission
  • This is , so the shortest answer wins
  • Input as a list in any reasonable representation and output as any truthy/falsy value. The two values must be consistent.

Test Cases

Input -> Output
1, 3, 5, 8, 6, 4, 2, 3, 5, 7, 6, 4, 2, 5, 7, 9, 6, 4, 2 -> True
1, 3, 5, 7, 6, 4, 5, 7, 9, 8, 6, 4, 2, 3, 5 -> False
2, 3, 6, 4, 2, 3, 7, 5, 3, 4, 6 -> True
3, 6, 4, 8, 5, 7, 3, 5, 2 -> True
8 -> True
1, 3, 5, 7 -> True
4, 5, 7, 6, 8, 9 -> False
6, 4, 2, 3, 5, 4, 2 -> True
8, 5, 3, 2, 4, 6, 5, 3, 2, 5, 7 -> False

Note: You may not assume that all numbers are single digits (unless that is all your language is capable of handling); the test cases reflect that just because it's easier for me to type the cases this way :P Here are a few test cases with numbers outside of that range:

1, 5, 10, 19, 15, 13, 8, 13, 18, 23, 19, 18, 14 -> True
15, 14, 17, 16, 19, 18 -> True
12, 16, 19, 15, 18, 19 -> False
\$\endgroup\$
4
  • \$\begingroup\$ Will the first run always be increasing, or can the input begin with a decreasing run? \$\endgroup\$
    – Jordan
    Oct 27, 2017 at 17:37
  • \$\begingroup\$ @Jordan Could start off decreasing. I will add a test case for that. \$\endgroup\$
    – hyper-neutrino
    Oct 27, 2017 at 18:07
  • \$\begingroup\$ Are the groups always complete? For example would 1, 2, 3, 2 be valid input, and if so considered true or false? In that in that example the next value being a 1 would make it true, but a 3 would make it false. \$\endgroup\$ Oct 28, 2017 at 13:49
  • 1
    \$\begingroup\$ @TomCarpenter That's considered false. They must be all the same length (and thus all complete). \$\endgroup\$
    – hyper-neutrino
    Oct 28, 2017 at 14:22

26 Answers 26

9
\$\begingroup\$

MATL, 10 9 bytes

dZS&Y'da~

Try it online!

Saved one byte thanks to Luis Mendo!

Explanation:

Assume the input is: [0, 3, 7, 5, 2, 3, 6]:

            % Implicit input:                                [0, 3, 7, 5, 2, 3, 6]
d           % Difference between adjacent elements:          [3, 4, -2, -3,  1,  3]
 ZS         % Sign of the differences:                       [1, 1, -1, -1, 1, 1]
   &Y'      % Length of runs of consecutive elements:        [2, 2, 2]
     d      % Difference between the lengths:                [0, 0]
      a     % Any non-zero elements:                         False
       ~    % Negate, to get a truthy value if all are zero: True
\$\endgroup\$
0
8
\$\begingroup\$

Jelly, 6 bytes

IṠŒgAE

Try it online!

Saved 1 byte thanks to Adnan!

How it works

IṠŒgAE  - Full program.

I       - Increments (Deltas).
 Ṡ      - Sign of each. -1 if negative, 0 if null, 1 if positive.
  Œg    - Group runs of adjacent elements.
    A   - Absolute value. Vectorizes. This maps -1 and 1 to the same value.
     E  - Are all equal?

While golfing, I discovered some cool, longer alternatives: IṠŒgL€E, IṠŒrṪ€E (uses run-length-encode instead).

\$\endgroup\$
3
  • \$\begingroup\$ I think IṠŒgḂE should save a byte \$\endgroup\$
    – Adnan
    Oct 26, 2017 at 14:51
  • \$\begingroup\$ @Adnan Can A (absolute value) substitute or is there a trick I don't get regarding ? \$\endgroup\$
    – Mr. Xcoder
    Oct 26, 2017 at 14:54
  • \$\begingroup\$ Any function that unifies 1 and -1 to the same number should suffice \$\endgroup\$
    – Adnan
    Oct 26, 2017 at 14:58
7
\$\begingroup\$

Wolfram Language (Mathematica), 38 bytes

Equal@@(1^Differences@#~SplitBy~Sign)&

Try it online!

Explanation

Equal@@(1^Differences@#~SplitBy~Sign)&  (* Input:                {3, 6, 4, 8, 5, 7, 3, 5, 2} *)

          Differences@#                 (* Take differences:     {3, -2, 4, -3, 2, -4, 2, -3} *)
                       ~SplitBy~Sign    (* Split by sign:        {{3}, {-2}, {4}, {-3}, {2}, {-4}, {2}, {-3}} *)
        1^                              (* Raise to power of 1:  {{1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}} *)
Equal@@                                 (* Check equal:          True *)
\$\endgroup\$
2
  • \$\begingroup\$ Equal@@(1^Split@Sign@Differences@#)& is 2 bytes shorter, and Equal@@Im@Split@Sign@Differences@#& is 1 more byte shorter than that. \$\endgroup\$ Oct 26, 2017 at 22:13
  • \$\begingroup\$ And now that I'm thinking about complex numbers, using Arg instead of Sign saves another byte. \$\endgroup\$ Oct 26, 2017 at 22:27
7
\$\begingroup\$

Octave, 54 50 bytes

@(x)nnz(unique(diff(find([diff(diff(x)>0) 1]))))<2

Try it online!

Explanation

@(x)nnz(unique(diff(find([diff(diff(x)>0) 1]))))<2

@(x)                                                % Define anonymous function    
                               diff(x)              % Deltas (consecutive differences)
                                      >0            % Positive? Gives signs
                          diff(         )           % Deltas between signs
                         [                1]        % Append 1 to "close" last group
                    find(                   )       % Indices of nonzeros
               diff(                         )      % Deltas. Gives group lengths
        unique(                               )     % Remove duplicates
    nnz(                                       )    % Number of nonzeros. Gives length
                                                <2  % If 1 or 0: input is periodic
\$\endgroup\$
6
\$\begingroup\$

R, 36 bytes

function(n)!sd(rle(sign(diff(n)))$l)

diff computes the successive differences, then sign squishes those down to ±1. rle then run-length encodes them. All the elements of this rle should be the same, i.e. the vector has standard deviation zero. ! then produces the correct logical output.

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

05AB1E, 8 7 bytes

¥0.SγaË

Try it online!

-1 thanks to Adnan.

\$\endgroup\$
4
  • \$\begingroup\$ ¥0.SγaË should save a byte \$\endgroup\$
    – Adnan
    Oct 26, 2017 at 14:37
  • \$\begingroup\$ What is a I can't find it in the docs. is_letter(a)??? \$\endgroup\$ Oct 26, 2017 at 14:48
  • \$\begingroup\$ yep, that is correct \$\endgroup\$
    – Adnan
    Oct 26, 2017 at 14:51
  • \$\begingroup\$ @Adnan ahhh... weird idea, good idea. \$\endgroup\$ Oct 26, 2017 at 14:51
5
\$\begingroup\$

C (gcc), 143 140 138 136 135 132 bytes

  • Saved three bytes; using a variable r to store the function's return boolean instead of terminating using return.
  • Saved two bytes; golfing int A[] to int*A (using a pointer instead of an array).
  • Saved two bytes thanks to Steadybox; golfing f(int*A,int a) to f(A,a)int*A;.
  • Saved a byte; golfing if(d!=... to if(d-....
  • Saved three bytes; golfing ;j++...j+1 to ;...++j.
j,d,e,l,m,r;f(A,a)int*A;{for(d=A[0]>A[1],r=1,j=m=l=0;j-~-a;){l++;if(d-(e=A[j]>A[++j]))d=e,j--,r*=l>=(m=!m?l:m),l=0;}r*=-~l==m||m<1;}

Try it online!

Defines a function f which looks at every element in the list but the last and determines this element's relation to the next element in the list. The number of consecutive equal comparisons is stored the first time the relation flips, any runs after the initial run that differ in length to the stored length result in a falsy output. At the end, the second-to-last element's relation to the last element's is looked at so that it matches the rest of the list.

\$\endgroup\$
1
  • \$\begingroup\$ You can use f(A,a)int*A; instead of f(int*A,int a). \$\endgroup\$
    – Steadybox
    Oct 28, 2017 at 13:48
4
\$\begingroup\$

Pyth, 11 bytes

qFlM.g._k.+

Try it here.

\$\endgroup\$
4
\$\begingroup\$

Python 2, 107 105 103 97 96 94 91 bytes

lambda l:len({sum(g)**2for k,g in groupby(map(cmp,l[:-1],l[1:]))})<2
from itertools import*

Try it online!

Python 3, 102 100 97 bytes

lambda l:len({len([*g])for k,g in groupby(x>y for x,y in zip(l,l[1:]))})<2
from itertools import*

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ you can use {...} instead set(...) to save 3 bytes \$\endgroup\$
    – Rod
    Oct 26, 2017 at 14:29
4
\$\begingroup\$

Husk, 7 bytes

EmLġ±Ẋ-

Try it online!

How this works

EmLġ±Ẋ-  ~ Full program.

     Ẋ   ~ Map over pairs of adjacent elements.
      -  ~ With subtraction (this computes the deltas)
   ġ     ~ Group using equality predicate.
    ±    ~ Sign.
 mL      ~ Get the lengths.
E        ~ Are all equal?

Some cute alternatives:

εġLġ±Ẋ-
εüLġ±Ẋ-
\$\endgroup\$
4
\$\begingroup\$

Python 2, 96 bytes

import re
def f(x):exec"x=map(cmp,x[1:],x[:-1]);"*2;re.match('.([^1]*)(-?1, \\1)*9',`x+[9]`)<0<_

Try it online! Output via exit code: crash (1) is falsey, clean exit (0) is truthy.

Python 2, 106 bytes

def f(x):d=map(cmp,x[1:],x[:-1]);l=len(d);s=(d+[0])[0];k=(d+[-s]).index(-s);print((k*[s]+k*[-s])*l)[:l]==d

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ I am not certain, though (...)[:l]<d may be the inverse of (...)[:l]==d. \$\endgroup\$ Oct 26, 2017 at 18:25
4
+250
\$\begingroup\$

Desmos, 82 bytes

f(l)=0^{mod(k/k[1],1).total}
L=D(D(l))
k=[1...L.length][LL=1]
D(l)=sign(l[2...]-l)

Try It On Desmos!

Try It On Desmos! - Prettified

Explanation

D(l)=sign(l[2...]-l): Takes the consecutive differences of the input list l, and takes the sign of the resulting differences.

L=D(D(l)): Applies the function D described above 2 times on l. The first difference will output a list (which I will denote as A) that, for each value of the original list l[i] for some i in the range [1,l.length-1], does the following:

  • If l[i]<l[i+1], A[i] will be 1. In other words, if l increases from l[i] to the next element, then it is denoted in the new list as 1.
  • If l[i]>l[i+1], A[i] will be -1. In other words, if l decreases from l[i] to the next element, then it is denoted in the new list as -1.

Note that we don't have to consider the case where l[i]=l[i+1], because that is guaranteed not to happen as per the specs:

  • No adjacent elements will be equal

The second difference outputs a list (denoted as B below) that does the following for each value in A, A[i], for some i in the range [1,A.length-1] (remember that the first difference is denoted as A):

  • If A[i]=A[i+1], then B[i] will be 0. In terms of l, what this checks for is if l[i], l[i+1], and l[i+2] are all either increasing or decreasing.
  • If A[i]<A[i+1], then B[i] will be 1. In terms of l, what this checks for is if it decreases from l[i] to l[i+1], but increases from l[i+1] to l[i+2]. In other words, this will check for transitions from a decreasing run to an increasing run.
  • Similarly, if A[i]>A[i+1], then B[i] will be -1. In terms of l, what this checks for is if it increases from l[i] to l[i+1], but decreases from l[i+1] to l[i+2]. In other words, this will check for transitions from an increasing run to a decreasing run.

k=[1...L.length][LL=1]: Filters the range [1...L.length] based on whether L*L is 1. This essentially obtains a list of indices at which L is either 1 or -1, and removes the indices where it is 0. What this achieves is that it will find the indices of the "turning points".

f(l)=0^{mod(k/k[1],1).total}: Divides each element of k by the first element k[1], and then takes the fractional part of the resulting quotients.

If the "turning points" are spaced out evenly, then this will result in a list of all 0's. Otherwise, at least one element will be a decimal number.

The total of this list is 0 only if the list only contains 0's, and nothing else. Otherwise, the total will be some number greater than 0. In other words, the total is 0 only if the elements are spaced out equally.

The last part is that, 0^0 is 1, will 0^n for some positive number n is 0. We can take advantage of this by using the total we obtained, and raising 0 to the power of the total. Recall that if the "turning points" are all spaced out evenly, then the total will be 0. This will cause 0^{mod(k/k[1],1).total} to be 1. Otherwise, if they aren't spaced out equally, the total is greater than 0, so 0^{mod(k/k[1],1).total} will be 0.

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

JavaScript (ES6), 81 bytes

This seems too long. I'm probably missing something here... Returns either true or undefined.

f=(a,p=1)=>a.every((n,i)=>!i|!(1/(y=a[i+1]))|!(i%p)^y>n^a[i-1]>n)||a[p]&&f(a,p+1)

Looks for a period 0 < p < a.length such that all direction changes occur every p elements.

Test cases

f=(a,p=1)=>a.every((n,i)=>!i|!(1/(y=a[i+1]))|!(i%p)^y>n^a[i-1]>n)||a[p]&&f(a,p+1)

console.log(f([1, 3, 5, 8, 6, 4, 2, 3, 5, 7, 6, 4, 2, 5, 7, 9, 6, 4, 2])) // -> True
console.log(f([1, 3, 5, 7, 6, 4, 5, 7, 9, 8, 6, 4, 2, 3, 5])) // -> False
console.log(f([2, 3, 6, 4, 2, 3, 7, 5, 3, 4, 6])) // -> True
console.log(f([3, 6, 4, 8, 5, 7, 3, 5, 2])) // -> True
console.log(f([8])) // -> True
console.log(f([1, 3, 5, 7])) // -> True
console.log(f([4, 5, 7, 6, 8, 9])) // -> False
console.log(f([15, 14, 17, 16, 19, 18])) // -> True
console.log(f([19, 15, 14, 17, 18, 17, 16, 19, 20])) // -> True

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

Haskell, 79 78 77 bytes

import Data.List
g s|h:t<-(1<$)<$>group(zipWith(<)s$tail s)=all(==h)t
g _=1<3

Try it online!

Given a list s, zipWith(<)s$tail stests for each element whether it is smaller than its successor, e.g. s=[2,3,6,4,2,3,7,5,3] yields [True,True,False,False,True,True,False,False]. Then group runs of the same elements together: [[True,True],[False,False],[True,True],[False,False]]. To check whether all those lists have the same length, replace their elements with 1 (see this tip) yielding [[1,1],[1,1],[1,1],[1,1]] and check if all elements in the tail t of this list equal the head h: all(==h)t.

This approach does not work for singleton lists, but because those are always true, we can handle them in their own case: g[_]=1<3.

\$\endgroup\$
1
  • \$\begingroup\$ g s=length(nub$map(1<$)$group$zipWith(<)s$tail s)<2 seems to work for 68 bytes. \$\endgroup\$
    – Lynn
    Nov 11, 2020 at 15:31
2
\$\begingroup\$

R, 57 bytes

function(x){d=diff
sum(rle(d(which(!!d(d(x)>0))))$v^0)<2}

Try it online!

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

Japt, 15 bytes

ä- mg ò¦ mÊä¥ e

Try it online!

Explanation

ä- mg ò¦ mÊä¥ e                                                  [0,3,7,5,2,3,6]
ä-                // Difference between neighboring elements     [-3,-4,2,3,-1,-3]
   mg             // Get the sign of each element                [-1,-1,1,1,-1,-1]
      ò¦          // Partition between different elements        [[-1,-1],[1,1],[-1,-1]]
         mÊ       // Get the length of each element              [2,2,2]
           ä¥     // Check for uniqueness                        [true,true]
              e   // Return true if all elements are truthy      true
\$\endgroup\$
2
\$\begingroup\$

Haskell (Lambdabot), 59 bytes

g(map(1<$).group.ap(zipWith(<))tail->h:t)=all(==h)t;g _=1<3

Based on @Laikoni's answer

\$\endgroup\$
2
  • \$\begingroup\$ Nice, I didn't know Lamdabot had ViewPatterns enabled. There is a space missing in g_=1<3. \$\endgroup\$
    – Laikoni
    Oct 30, 2017 at 14:40
  • \$\begingroup\$ @Laikoni Me neither, but I actually went to #haskell and tested it \$\endgroup\$
    – BlackCap
    Oct 30, 2017 at 14:44
2
\$\begingroup\$

Clojure, 70 63 bytes

#(<(count(set(map count(partition-by pos?(map -(rest %)%)))))2)

Returns true or false. The original answer was a bit silly.

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

Java (OpenJDK 8), 437 302 256 188 bytes

a->{int i=0,g=0,x=0,l=0;String d="";for(;i<~-a.length;d+=a[0].compare(a[i+1],a[i++])+1);for(String s:d.split("(?<=(.))(?!\\1)"))if(g++<1)x=s.length();else if(s.length()!=x)l++;return l<1;}

Try it online!

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

Java (OpenJDK 8), 135 bytes

a->{Integer i=0,c,d=0,p=0,r=0;for(;++i<a.length;)d+=(i<2|(c=i.signum(a[i-1]-a[i]))<0?d<0:d>0)?c:p==0|p==-d?c-(p=d):1-(r=1);return r<1;}

Try it online!

Explanations

a->{                    // int array
 Integer i=0,c,d=0,p=0,r=0;
                        // variable definitions, use Integer to abuse static calls
 for(;++i<a.length;)    // Loop from 1 till length - 1
  d+=                   // Change d
   (i<2                 // First iteration?
     |(c=i.signum(a[i-1]-a[i]))<0?d<0:d>0
   )                    // Or do c and d have the same sign?
    ?c                  // then increase the magnitude of d.
    :p==0|p==-d         // else we're in a u-turn. Is it the first? Or is the magnitude the same as previously?
     ?c-(p=d)           // assign the new magnitude with sign to p and reset d to -1 (if was positive) or 1 (if was negative)
     :1-(r=1);          // else just do r=1 (technically: "add 1-1=0 to d" as well)
 return r<1;            // return whether there were wrong amplitudes.
}
\$\endgroup\$
1
\$\begingroup\$

Python 2, 110 99 bytes

-11 bytes thanks to @Lynn

d=input()
exec"d=map(cmp,d[:-1],d[1:]);"*2
x=[i+1for i,e in enumerate(d)if e]
for i in x:i%x[0]>0<q

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ You can save some bytes by computing the double differences as exec"d=map(cmp,d[:-1],d[1:]);"*2 \$\endgroup\$
    – Lynn
    Oct 27, 2017 at 12:58
1
\$\begingroup\$

Ruby, 57 bytes

->a{!a.each_cons(2).chunk{|x,y|x>y}.uniq{|*,x|x.size}[1]}

Try it online!

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

Japt, 9 bytes

Outputs false for truthy and true for falsey.

äÎòÎmÊäÎd

Try it (footer negates the output) or run all test cases

äÎòÎmÊäÎd     :Implicit input of array                                    > [0,3,7,5,2,3,6]
ä             :Consecutive pairs                                          > [[0,3],[3,7],[7,5],[5,2],[2,3],[3,6]]
 Î            :  Reduced by the sign of their differences (1 or -1)       > [-1,-1,1,1,-1,-1]
  ò           :Partition between elements that return true (not zero)
   Î          :  Get the sign of their difference                         > [[-1,-1],[1,1],[-1,-1]]
    m         :Map
     Ê        :  Length                                                   > [2,2,2]
      ä       :Consecutive pairs                                          > [[2,2],[2,2]]
       Î      :  Reduced by the sign of their differences                 > [0,0]
        d     :Any truthy?                                                > false
\$\endgroup\$
1
\$\begingroup\$

Husk, 7 bytes

Λ≡gẊo±-

Try it online!

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

Vyxal, 5 bytes

¯±Ġȧ≈

Try it Online!

Port of Jelly answer.

How?

¯±Ġȧ≈
¯     # Get the deltas (consecutive differences) of input
 ±    # Get the sign (implicit vectorization)
  Ġ   # Group consecutive identical items
   ȧ  # Absolute value (implicit double-vectorization)
    ≈ # All equal?
\$\endgroup\$
1
\$\begingroup\$

Factor, 49 bytes

[ [ trends check-lengths t ] [ tuple? ] recover ]

Try it online!

There is a lot to unpack here. First, Factor (nearly!) has the perfect word for this problem, trends, which splits a sequence into its rising, falling, and stable parts. This question guarantees no two adjacent elements will be equal, so we don't need to worry about receiving any stable trends in the result.

The problem is, for some unfathomable reason, if the sequence has only one trend, trends returns a single trend object instead of a sequence with a single trend object in it. Thus when we attempt to see if the lengths of the trends are all equal, we'll get an error that length can't be applied to a non-sequence if there is only a single trend.

Next, instead of saying something like [ length ] map all-eq?, Factor has a word in its (exposed) compiler named check-lengths that throws an error if the lengths of a sequence are not all equal. So check-lengths is capable of failing in two different ways: either it'll end up calling length on a non-sequence, or it'll throw an error if the lengths of its input are not all the same.

Enter recover, one of Factor's exception handling words. It calls the first quotation (which will simply return t if no errors are encountered) and calls the second quotation with the error on top of the stack if the first quotation encounters an error. Inside this quotation, all we need to do is check whether the error is a tuple or not, because calling length on a non-sequence produces an actual error tuple while check-lengths throws a simple string error if the lengths are unequal.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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