19
\$\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\$
  • \$\begingroup\$ Will the first run always be increasing, or can the input begin with a decreasing run? \$\endgroup\$ – Jordan Oct 27 '17 at 17:37
  • \$\begingroup\$ @Jordan Could start off decreasing. I will add a test case for that. \$\endgroup\$ – HyperNeutrino Oct 27 '17 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\$ – Tom Carpenter Oct 28 '17 at 13:49
  • 1
    \$\begingroup\$ @TomCarpenter That's considered false. They must be all the same length (and thus all complete). \$\endgroup\$ – HyperNeutrino Oct 28 '17 at 14:22

21 Answers 21

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\$
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\$
  • \$\begingroup\$ I think IṠŒgḂE should save a byte \$\endgroup\$ – Adnan Oct 26 '17 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 '17 at 14:54
  • \$\begingroup\$ Any function that unifies 1 and -1 to the same number should suffice \$\endgroup\$ – Adnan Oct 26 '17 at 14:58
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\$

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\$
  • \$\begingroup\$ Equal@@(1^Split@Sign@Differences@#)& is 2 bytes shorter, and Equal@@Im@Split@Sign@Differences@#& is 1 more byte shorter than that. \$\endgroup\$ – Misha Lavrov Oct 26 '17 at 22:13
  • \$\begingroup\$ And now that I'm thinking about complex numbers, using Arg instead of Sign saves another byte. \$\endgroup\$ – Misha Lavrov Oct 26 '17 at 22:27
5
\$\begingroup\$

05AB1E, 8 7 bytes

¥0.SγaË

Try it online!

-1 thanks to Adnan.

\$\endgroup\$
  • \$\begingroup\$ ¥0.SγaË should save a byte \$\endgroup\$ – Adnan Oct 26 '17 at 14:37
  • \$\begingroup\$ What is a I can't find it in the docs. is_letter(a)??? \$\endgroup\$ – Magic Octopus Urn Oct 26 '17 at 14:48
  • \$\begingroup\$ yep, that is correct \$\endgroup\$ – Adnan Oct 26 '17 at 14:51
  • \$\begingroup\$ @Adnan ahhh... weird idea, good idea. \$\endgroup\$ – Magic Octopus Urn Oct 26 '17 at 14:51
4
\$\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\$
  • \$\begingroup\$ You can use f(A,a)int*A; instead of f(int*A,int a). \$\endgroup\$ – Steadybox Oct 28 '17 at 13:48
3
\$\begingroup\$

Pyth, 11 bytes

qFlM.g._k.+

Try it here.

\$\endgroup\$
3
\$\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\$
  • \$\begingroup\$ you can use {...} instead set(...) to save 3 bytes \$\endgroup\$ – Rod Oct 26 '17 at 14:29
3
\$\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\$
2
\$\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\$
2
\$\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\$
  • \$\begingroup\$ I am not certain, though (...)[:l]<d may be the inverse of (...)[:l]==d. \$\endgroup\$ – Jonathan Frech Oct 26 '17 at 18:25
2
\$\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\$

R, 57 bytes

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

Try it online!

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

Clojure, 70 bytes

#({0 1 1 1}(count(set(map count(partition-by pos?(map -(rest %)%))))))

Returns 1 as truthy and nil (AKA null) as falsy.

\$\endgroup\$
0
\$\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\$
0
\$\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\$
  • \$\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 '17 at 12:58
0
\$\begingroup\$

Ruby, 57 bytes

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

Try it online!

\$\endgroup\$

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.