Get the sequence steps

Question

Challenge

Given a sequence of numbers, create a function which returns the sequence steps.

• Assume a sequence will be N >= 3
• Sequence will repeat it steps at least once
• Sequence will only contain natural numbers
• Your function or program should return the shortest possible sequence of steps

Example:

Input: [1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17]

Output: [1, 1, 2]

Explanation: The initial sequence goes from 1 => 2 (1 step), 2 => 3 (1 step), 3 => 5 (2 steps). Then it repeats. The output then is [1 step, 1 step, 2 steps] => [1, 1, 2]

Another example:

Input: [2, 5, 6, 7, 8, 11, 12, 13, 14, 17, 18, 19, 20]

Output: [3, 1, 1, 1]

[2, 5, 6, 7, 8, 11, 12, 13, 14, 17, 18, 19, 20]
 \  /\ /\ /\ / 
  3   1  1  1  Then it repeats...

Test Cases

Input: [1, 4, 8, 9, 10, 13, 17, 18, 19, 22, 26, 27, 28] => Output: [3,4,1,1]

Input: [6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41] => Output: [5,2]

Input: [2, 6, 10, 13, 17, 21, 25, 28, 32, 36, 40, 43, 47] => Output: [4,4,3,4]

Input: [5, 6, 7] => Output: [1]

---

Clarifications

• The input length - 1 is divisible by the output length
• Assume sequence will always going to be increasing

---

This is code-golf, so the shortest answer in bytes win.

Answer 1

Jelly, 9 7 bytes

IsJEƇḢḢ

Try it online!

How it works

IsJEƇḢḢ  Main link. Argument: A (array)

I        Increment; compute D, the array of A's forward differences.
  J      Indices; yield [1, ..., len(A)].
 s       Split D into chunks of length k, for each k in [1, ..., len(A)].
   EƇ    Comb equal; keep only partitions of identical chunks.
     Ḣ   Head; extract the first matching parititon.
      Ḣ  Head; extract the first chunk.

Answer 2

JavaScript (ES6), 58 bytes

Outputs a comma-separated string (with a leading comma).

a=>(a.map(p=x=>-(p-(p=x)))+'').match(/N((,\d+)*?)\1*$/)[1]

Try it online!

Or 56 bytes if we use ,- as the separator and we assume that the sequence is always strictly increasing.

How?

We first convert the input array a[ ] to a list of consecutive differences with:

a.map(p = x => -(p - (p = x)))

Because p is initially set to a non-numeric value (the callback function of map()), the first iteration yields NaN.

Example:

[6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41]
[ NaN, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2 ]

We then coerce the result to a string:

"NaN,5,2,5,2,5,2,5,2,5,2"

Finally, we look for the shortest¹ pattern of comma-separated integers (,\d+) starting right after "NaN" and repeating till the end of the string:

match(/N((,\d+)*?)\1*$/)

_{1: using the non-greedy *?}

Answer 3

Brachylog, 11 bytes

s₂ᶠ-ᵐṅᵐ~j₍t

Try it online!

Would be 5 bytes if there was a built-in for consecutive differences.

Explanation

Example input: [6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41] 

s₂ᶠ             Find all substrings of length 2: [[6,11],[11,13],…,[34,39],[39,41]]
   -ᵐ           Map subtraction: [-5,-2,-5,-2,-5,-2,-5,-2,-5,-2]
     ṅᵐ         Map negate: [5,2,5,2,5,2,5,2,5,2]
       ~j₍      Anti-juxtapose the list of differences; the shortest repeated list is found
                  first, with the biggest number of repetitions: [5,[5,2]]
            t   Tail: [5,2]

Answer 4

Japt, 14 12 bytes

äa
¯@eUéX}aÄ

Try it

---

Explanation

              :Implicit input of array U
äa            :Consecutive absolute differences
\n            :Reassign to U
 @    }aÄ     :Return the first positive integer X that returns true
   UéX        :  Rotate U right X times
  e           :  Check equality with U
¯             :Slice U to that element

---

Original

äa
@eUîX}a@¯XÄ

Try it

Answer 5

Pyth, 11 bytes

<J.+Qf.<IJT

Try it here

Explanation

<J.+Qf.<IJT
 J.+Q          Call the sequence of differences in the input J.
     f         Find the first positive integer T...
      .<IJT    ... where rotating J by T doesn't change it.
<J             Take that many elements of J.

Answer 6

R, 49 46 bytes

Full program:

d=diff(scan());while(any((s=d[1:T])-d))T=T+1;s

Try it online!

R, 72 58 54 bytes

Original function submission with all test cases in one place:

function(a,d=diff(a)){while(any((s=d[1:T])-d))T=T+1;s}

Try it online!

Thanks to JayCe for suggesting the full program route and -4 bytes on the function, and to Giuseppe for further -3.

Answer 7

05AB1E, 8 bytes

Saved 3 bytes thanks to Kevin Cruijssen.

¥.œʒË}нн

Try it online!

---

05AB1E, 11 bytes

āεI¥ô}ʒË}нн

Try it online!

āεI¥ô}ʒË}нн   Full program.
ā             Length range. Push [1 ... len(inp)].
 ε   }        For each...
  I¥ô         ... Chop the deltas into pieces of the corresponding size
      ʒË}     Keep only those that have all their elements equal.
         нн   And first retrieve the first element of the first one.

---

13 bytes

A cute alternative, IMO:

¥©ηʒDg®ôÙ˜Q}н

Try it online!

¥©ηʒDg®ôÙ˜Q}н   Full program.
¥               Push the deltas.
 ©              Copy them to the register.
  ηʒ       }    And filter the prefixes by...
    D     Q     ... Is the prefix itself equal to...
     g®ô        ... The deltas, split into chunks of its length...
        Ù˜      ... Deduplicated and flattened?
            н   Head.

Answer 8

J, 22 19 bytes

3 bytes saved thanks to FrownyFrog!

0{"1[:~./:|."{}.-}:

Try it online!

[Try it online!][TIO-ji2uiwla]

How?

                 -      find the successive differences by subtracting 
                  }:    the list with last element dropped
               }.       from the list with the first element dropped 
           |."{         rotate the list of differences
         /:             0..length-1 times (the input graded up)
     [:~.               remove duplicating rows
 0{"1                   take the first element of each row

Answer 9

Javascript, 49 56 bytes

Edit 7 bytes saved thanks (guess who?) Arnauld

Same regex idea as Arnauld, but curiously so different in implementation ...

Returning a string with steps comma separated (and a leading comma)

p=>/N(.+?)\1+$/.exec(p.map(p=v=>[v-p,p=v][0]))[1]

Test

var F=
p=>/N(.+?)\1+$/.exec(p.map(p=v=>[v-p,p=v][0]))[1]

;[[1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17]
,[1, 4, 8, 9, 10, 13, 17, 18, 19, 22, 26, 27, 28]
,[6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41] 
,[2, 6, 10, 13, 17, 21, 25, 28, 32, 36, 40, 43, 47]
,[5, 6, 7]]
.forEach(x=>console.log(x + ' -> ' + F(x)))

Answer 10

MATL, 14 13 12 bytes

dt5YLFTF#Xu)

Try it online!

Just discovered that MATL does have a circulant function!

Explanation

d - Get the differences between successive terms, as an array

t5YL - duplicate that, then call the YL ('gallery') function with 5 ('circulant') option. Creates a matrix with the given vector as first row, then successive rows are the same vector shifted circularly, until it wraps around.

FTF#Xu - Check for unique rows and get their row numbers (not sure if there's a shorter way of doing this). When sequence steps repeat, the circularly shifted row will be the same as the first row, and the subsequent rows will be repeats. So this gets the indices of the first run of sequence steps before they start repeating.

) - index using that into the original differences array, to get the answer.

---

Older:

d`tt@YS-a}@:)

Try it online!

(-1 byte thanks to Giuseppe)

Explanation:

d   % Get the differences between successive terms, as an array
`   % Start do-while loop
  tt  % duplicate the difference array twice
  @   % push the current loop index value
  YS  % circularly shift the difference array by that amount
  -   % subtract the shifted diffs from the original diffs
  a   % see if the subtraction resulted in any non-zeros
    % if it did, shifted differences were not equal to original differences, so continue loop 
}@ % if it didn't, then get loop index
:) % get the differences upto the loop index, before they started repeating
   % implicit loop end

Answer 11

Java 10, 104 100 bytes

a->{var t="";for(int i=a.length;i-->1;t+=a[i]-a[i-1]+" ");return t.replaceAll("( ?.+?)\\1*$","$1");}

Regex ( ?.+?)\1*$ for shortest repeating substring from @Neil's comment on @Arnauld's JavaScript (ES6) answer.

Try it online.

Explanation:

a->{                        // Method with integer-array parameter and String return-type
  var t="";                 //  Temp-String, starting empty
  for(int i=a.length;i-->1; //  Loop backward over the input-array, skipping the first item
    t+=a[i]-a[i-1]          //   Calculate the difference between two adjacent items
       +" ");               //   And append this with a space to the temp-String
  return t.replaceAll("( ?.+?)\\1*$", 
                            //  Find the shortest repeating substring
                     "$1");}//  And only keep one such substring

Answer 12

Ruby, 62 bytes

Relies on Regex logic adapted from Arnauld's answer.

->a{i=-2;a.map{|x|(i+=1)>=0?x-a[i]:0}*?,=~/((,\d+)*?)\1*$/;$1}

Try it online!

Alternative determination of step differences, also 62 bytes:

->a{[0,*a.each_cons(2).map{|x,y|y-x}]*?,=~/((,\d+)*?)\1*$/;$1}

Try it online!

Answer 13

Python 2, 101 bytes

def f(l):d=[y-x for x,y in zip(l,l[1:])];g=len(l);print[d[:k]for k in range(1,g+1)if g/k*d[:k]==d][0]

Try it online!

First generates the deltas d, then finds the first prefix p of d that when repeated ⌊len(L) / len(p)⌋ times yields L, where L is the input list.

Answer 14

APL+WIN, 39 bytes

Prompt for input.

(↑((⍴v)=+/¨(⊂v)=(⍳⍴v)⌽¨⊂v)/⍳⍴v)↑v←-2-/⎕

Try it online! Courtesy of Dyalog Classic

Explanation:

v←-2-/⎕ Prompt for input and take successive differences

(⍳⍴v)⌽¨⊂v create a nested vector ans sequentially rotate by one to length of v

+/¨(⊂v)= compare to original v and sum positions where there is match

(⍴v)= identify where all elements match

(↑(....) identify number of rotations giving a first complete match

(↑(...)↑v take first number of elements from above from v as repeated sequence

Answer 15

Python 2, 86 85 bytes

def f(a,n=1):d=[y-x for x,y in zip(a,a[1:])];return d[:-n]==d[n:]and d[:n]or f(a,n+1)

Try it online!

Construct the differences as d; if d repeats with unit size n then d[n:]==d[:-n]; else recurse.

Answer 16

Stax, 8 6 bytes

░»F\☺»

Run and debug it

Here's an unpacked annotated version to show how it works.

:-  pairwise differences
:(  all leftward rotations of array
u   keep only unique rotations
mh  output the first element from each unique rotation

Run this one

Answer 17

Retina 0.8.2, 42 bytes

\d+
$*
(?<=(1+),)\1

1+(.+?)\1*$
$1
1+
$.&

Try it online! Link includes test cases. Output includes leading comma. Explanation:

\d+
$*

Convert to unary.

(?<=(1+),)\1

Compute forward differences, except for the first number, which gets left behind.

1+(.+?)\1*$
$1

Match repeating differences.

1+
$.&

Convert to decimal.

Answer 18

05AB1E, 14 13 bytes

¥DηvÐNƒÁ}QD—#

Try it online or verify all test cases.

I know there are already two shorter 05AB1E answers posted by @Mr.Xcoder, but I wanted to try this alternative approach using rotation and equality check.
Might be able to golf it down a few bytes without dropping Á.

-1 byte after a tip of @Emigna to remove the global_variable registers (© and 2x ®) and use a Duplicate (D) and a Triplicate (Ð) instead.

Explanation:

¥             # Calculate the deltas of the input-array
              #  i.e. [1,2,3,5,6,7,9] → [1,1,2,1,1,2]
 D            # Duplicate it
  η           # Push all its prefixes
              #  [1,1,2,1,1,2] → [[1],[1,1],[1,1,2],[1,1,2,1],[1,1,2,1,1],[1,1,2,1,1,2]]
v             # For-each over these prefixes
 Ð            #  Triplicate the (duplicated) deltas-list
  NƒÁ}        #  Rotate the deltas-list N+1 amount of times,
              #  where N is the prefix index (== prefix_length-1)
              #   i.e. [1,1,2] and [1,1,2,1,1,2] (rotate 3 times) → [1,1,2,1,1,2]
      Q       #  If the rotated deltas and initial deltas are equal
              #   [1,1,2,1,1,2] and [1,1,2,1,1,2] → 1
       D—#    #  Print the current prefix-list, and stop the for-each loop

Answer 19

Haskell, 107 bytes

let i=map(uncurry(-))$zip(tail x)(init x)in head$filter(\s->take(length i)(concat$repeat s)==i)(tail$inits i)

x is the input array.

Answer 20

Perl 6, 57 bytes

{~(.rotor(2=>-1).map:{.[1]-.[0]})~~/^(.+?){}" $0"+$/;~$0}

Test it

Output is space separated ("1 1 2")

Expanded:

{      # bare block lambda with implicit parameter $_

  ~(   # stringify (space separated)

    .rotor( 2 => -1 )     # from the input take 2 backup 1, repeat
    .map: { .[1] - .[0] } # subtract each pair to find the differences
  )

  ~~   # smartmatch

  /    # regex

    ^  # beginning of string

    ( .+? ) # match at least one character, but as few as possible
    {}      # make sure $0 is set (probably a compiler bug)
    " $0"+  # match $0 one or more times (with a leading space)

    $  # end of string
  /;

  ~$0  # return the stringified $0
}

Answer 21

05AB1E, 9 bytes

¥©η.ΔÞ®Å?

Explanation:

          # take input implicitly
¥         # deltas, eg [4, 5, 7, 8, 10] -> [1, 2, 1, 2]
 ©        # save this to the global register
  η       # prefixes, eg [1, 2, 1, 2] -> [[1], [1, 2], ...]
   .Δ     # find the first one such that
     Þ    # cycled infinitely, eg [1, 2] -> [1, 2, 1, 2, ...]
       Å? # starts with
      ®   # the global register
          # and implicitly print the found element

Alternative 9-byte:

¥η.ΔÞ.¥-Ë

Same algo, but instead of comparing to the list of deltas (which needs to be saved/restored), this uses .¥ (undelta) then compares to the (implicit) input.

Try it online!

Answer 22

K4, 30 bytes

Solution:

(*&d~/:c#'(!c:#d)#\:d)#d:1_-':

Examples:

q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':2, 5, 6, 7, 8, 11, 12, 13, 14, 17, 18, 19, 20
3 1 1 1
q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17
1 1 2
q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':1, 4, 8, 9, 10, 13, 17, 18, 19, 22, 26, 27, 28
3 4 1 1
q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41
5 2
q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':2, 6, 10, 13, 17, 21, 25, 28, 32, 36, 40, 43, 47
4 4 3 4
q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':5 6 7
,1

Explanation:

Seems hefty for what we're trying to solve. Get the deltas of the input and then build sequences and determine the shortest one that matches it.

(*&d~/:c#'(!c:#d)#\:d)#d:1_-': / the solution
                           -': / deltas 
                         1_    / drop first
                       d:      / save as d
                      #        / take (#) from
(                    )         / do this together
                 #\:d          / take (#) each-left (\:) from d
          (     )              / do this together
              #d               / count length of d
            c:                 / save as c
           !                   / range 0..c-1
       c#'                     / take c copies of each
   d~/:                        / d equal (~) to each right (/:)
  &                            / where true
 *                             / first one

Answer 23

Perl 5 -p, 55 bytes

s/\d+ (?=(\d+))/($1-$&).$"/ge;s/\d+$//;s/^(.+?)\1*$/$1/

Try it online!

Numbers are input as a space separated list. Output is the same format.

Answer 24

Wolfram Language (Mathematica), 26 bytes

Differences@#/.{a__..}->a&

Try it online!

Returns a Sequence containing the steps.

---

+2 bytes for List output:

Differences@#/.{a__..}->{a}&

Try it online!