Does it oscillate periodically?

19

1

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

HyperNeutrino

Posted 2017-10-26T13:35:20.863

Reputation: 26 575

Will the first run always be increasing, or can the input begin with a decreasing run? – Jordan – 2017-10-27T17:37:52.700

@Jordan Could start off decreasing. I will add a test case for that. – HyperNeutrino – 2017-10-27T18:07:28.043

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. – Tom Carpenter – 2017-10-28T13:49:58.447

1@TomCarpenter That's considered false. They must be all the same length (and thus all complete). – HyperNeutrino – 2017-10-28T14:22:32.250

Answers

9

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

Stewie Griffin

Posted 2017-10-26T13:35:20.863

Reputation: 43 471

8

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

Mr. Xcoder

Posted 2017-10-26T13:35:20.863

Reputation: 39 774

I think IṠŒgḂE should save a byte – Adnan – 2017-10-26T14:51:04.227

@Adnan Can A (absolute value) substitute Ḃ or is there a trick I don't get regarding Ḃ? – Mr. Xcoder – 2017-10-26T14:54:40.327

Any function that unifies 1 and -1 to the same number should suffice – Adnan – 2017-10-26T14:58:39.960

7

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

Luis Mendo

Posted 2017-10-26T13:35:20.863

Reputation: 87 464

6

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

JungHwan Min

Posted 2017-10-26T13:35:20.863

Reputation: 13 290

Equal@@(1^Split@Sign@Differences@#)& is 2 bytes shorter, and Equal@@Im@Split@Sign@Differences@#& is 1 more byte shorter than that. – Misha Lavrov – 2017-10-26T22:13:23.683

And now that I'm thinking about complex numbers, using Arg instead of Sign saves another byte. – Misha Lavrov – 2017-10-26T22:27:46.857

5

05AB1E, 8 7 bytes

¥0.SγaË

Try it online!

-1 thanks to Adnan.

Magic Octopus Urn

Posted 2017-10-26T13:35:20.863

Reputation: 19 422

¥0.SγaË should save a byte – Adnan – 2017-10-26T14:37:17.310

What is a I can't find it in the docs. is_letter(a)??? – Magic Octopus Urn – 2017-10-26T14:48:59.447

yep, that is correct – Adnan – 2017-10-26T14:51:25.780

@Adnan ahhh... weird idea, good idea. – Magic Octopus Urn – 2017-10-26T14:51:52.277

4

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.

Jonathan Frech

Posted 2017-10-26T13:35:20.863

Reputation: 6 681

You can use f(A,a)int*A; instead of f(int*A,int a). – Steadybox – 2017-10-28T13:48:59.457

3

Pyth, 11 bytes

qFlM.g._k.+

Try it here.

Erik the Outgolfer

Posted 2017-10-26T13:35:20.863

Reputation: 38 134

3

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!

TFeld

Posted 2017-10-26T13:35:20.863

Reputation: 19 246

you can use {...} instead set(...) to save 3 bytes – Rod – 2017-10-26T14:29:48.637

3

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ġ±Ẋ-

Mr. Xcoder

Posted 2017-10-26T13:35:20.863

Reputation: 39 774

2

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

Arnauld

Posted 2017-10-26T13:35:20.863

Reputation: 111 334

2

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!

Lynn

Posted 2017-10-26T13:35:20.863

Reputation: 55 648

I am not certain, though (...)[:l]<d may be the inverse of (...)[:l]==d. – Jonathan Frech – 2017-10-26T18:25:18.067

2

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.

Laikoni

Posted 2017-10-26T13:35:20.863

Reputation: 23 676

1

R, 57 bytes

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

Try it online!

NofP

Posted 2017-10-26T13:35:20.863

Reputation: 754

1

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

Oliver

Posted 2017-10-26T13:35:20.863

Reputation: 7 160

1

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.

JDL

Posted 2017-10-26T13:35:20.863

Reputation: 1 135

1

Haskell (Lambdabot), 59 bytes

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

Based on @Laikoni's answer

BlackCap

Posted 2017-10-26T13:35:20.863

Reputation: 3 576

Nice, I didn't know Lamdabot had ViewPatterns enabled. There is a space missing in g_=1<3. – Laikoni – 2017-10-30T14:40:16.693

@Laikoni Me neither, but I actually went to #haskell and tested it – BlackCap – 2017-10-30T14:44:02.827

0

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!

ovs

Posted 2017-10-26T13:35:20.863

Reputation: 21 408

You can save some bytes by computing the double differences as exec"d=map(cmp,d[:-1],d[1:]);"*2

– Lynn – 2017-10-27T12:58:26.237

0

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!

Roberto Graham

Posted 2017-10-26T13:35:20.863

Reputation: 1 305

0

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

Olivier Grégoire

Posted 2017-10-26T13:35:20.863

Reputation: 10 647

0

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.

NikoNyrh

Posted 2017-10-26T13:35:20.863

Reputation: 2 361

0

Ruby, 57 bytes

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

Try it online!

Jordan

Posted 2017-10-26T13:35:20.863

Reputation: 5 001

Asked: 2017-10-26T13:35:20.863

Viewed: 2 580 times

Active: 2017-10-30T14:46:18.380