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.

• AdmBorkBork: Related challenge.
• Giuseppe: I've seen a few challenges you've posted recently with a lot of clarifying comments, and a couple closed as "unclear", and subsequently re-opened after you've made the appropriate edits. Have you considered posting these in the sandbox for a few days/a week? I've enjoyed your challenges since they're quite approachable, but all challenges, no matter how simple or by whom they're posted, can use refinement.
• Luis felipe De jesus Munoz: @Giuseppe Thanks for your suggestions. I have posted some other challenges in the sand box (usually if i don't get the right way to create a challenge with it i delete it). For these challenges I thought they were clear enough and that's why I posted immediately but I will start posting them in the sandbox first. Thanks
• ngm: @LuisMendo Heretic! 0 is a natural number! Billy Joel even had a whole album dedicated to the Peano Man!
• Peter Taylor: @AdmBorkBork, this is more related by virtue of dealing with arbitrary-length operation lists.

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 *?}

• edc65: I'm posting a solution based on the same regex idea, but very different in implementation. Of course I did not look at other solutions before developing mine, and it seems different enough, And maybe it's the first time ever I manage to score better than you here.
• Neil: 53 bytes: /(,.+?)1円*$/.

Answer 3

Brachylog, 11 bytes

s2f-mṅm~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] 
s2f Find all substrings of length 2: [[6,11],[11,13],...,[34,39],[39,41]]
 -m Map subtraction: [-5,-2,-5,-2,-5,-2,-5,-2,-5,-2]
 ṅm 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]

• Rod: Can you negate after the tail, to save a byte?
• Fatalize: @Rod I would still need to map it, so it would be the same length. Negate is a predicate between two numbers, it doesn't vectorize automatically to lists like other languages (otherwise it would not work well with unknown inputs/outputs which are common in declarative programs)

Answer 4

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 5

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

• JayCe: -9 bytes by abusing a built-in and making it a full program The challenge allows a full program.
• Giuseppe: @JayCe don't need a<- here either

Answer 7

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

• FrownyFrog: If you /: instead of #\, you can 0{"1[:~. to save 1 byte.
• FrownyFrog: And "0 1 is "{
• Galen Ivanov: @FrownyFrog Thanks, once again!
• Jonah: this is gorgeous.
• Galen Ivanov: @Jonah Yes, thanks to FrownyFrog!

Answer 8

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.

• Kevin Cruijssen: 8 bytes by using .œ.

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

• Arnauld: Using match was a poor decision of mine. You can outgolf me some more. :-)

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

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

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

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 17

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

• Grimmy: Here's a 9 (separate answer since it's a very different algo, though it does share the ¥η).
• Kevin Cruijssen: @Grimy Are you going through all my 05AB1E answers and golf each of them, haha? ;p Nice answer though (yet again), +1 from me.
• Grimmy: Not all of them, I'm just going through those linked in this post.
• Kevin Cruijssen: @Grimy Ah ok, that makes sense. :)

Answer 18

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.

• Laikoni: Welcome to PPCG and Haskell golfing in particular! You cannot assume the input to be present in a certain variable, though this is easily fixed by prepending f x=. Also the use of inits requires import Data.List, as it is not part of Prelude: Try it online!
• Laikoni: However you can save quite a few bytes: (init x) can just be x because zip truncates automatically if one of the lists is longer than the other one. And for map(uncurry(-))$zip exists an build-in: zipWith(-). Instead of f x=let i=...in you can use a pattern guard: f x|i<-...=.
• Laikoni: Furthermore you can use a list comprehension instead of filter, !!0 instead of head and cycle instead of concat$repeat: Try it online!
• misja111: @Laikoni Thanks a lot for your improvements! You are right, my code needs a function declaration and an import for Data.List.inits. But I was wondering, should that be added to the length of the code? I'm asking because some of the other code samples rely on some extra code as well.
• Laikoni: Yes, it is general consensus that those bytes are included in the score. We have a guide to golfing rules in Haskell which covers most of these cases.

Answer 19

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 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ドル
}

• Jo King: The whole first part can be ~(.skip Z-$_)

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

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 23

Husk, 12 bytes

←ḟΛ=Um`CẊ≠0N

Try it online! or Verify all test cases

Answer 24

Wolfram Language (Mathematica), (削除) 26 (削除ここまで) 23 bytes

FindRepeat@*Differences

Try it online!

Answer 25

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