17
\$\begingroup\$

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 , so the shortest answer in bytes win.

\$\endgroup\$
  • \$\begingroup\$ Related challenge. \$\endgroup\$ – AdmBorkBork Jun 5 '18 at 13:45
  • 6
    \$\begingroup\$ 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. \$\endgroup\$ – Giuseppe Jun 5 '18 at 14:13
  • 2
    \$\begingroup\$ @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 \$\endgroup\$ – Luis felipe De jesus Munoz Jun 5 '18 at 14:15
  • 2
    \$\begingroup\$ @LuisMendo Heretic! 0 is a natural number! Billy Joel even had a whole album dedicated to the Peano Man! \$\endgroup\$ – ngm Jun 5 '18 at 15:46
  • 1
    \$\begingroup\$ @AdmBorkBork, this is more related by virtue of dealing with arbitrary-length operation lists. \$\endgroup\$ – Peter Taylor Jun 6 '18 at 6:29

24 Answers 24

10
\$\begingroup\$

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.
\$\endgroup\$
9
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – edc65 Jun 6 '18 at 7:28
  • 1
    \$\begingroup\$ 53 bytes: /(,.+?)\1*$/. \$\endgroup\$ – Neil Jun 6 '18 at 9:54
6
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ Can you negate after the tail, to save a byte? \$\endgroup\$ – Rod Jun 5 '18 at 14:08
  • \$\begingroup\$ @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) \$\endgroup\$ – Fatalize Jun 5 '18 at 14:10
5
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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

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

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.

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

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
\$\endgroup\$
  • \$\begingroup\$ If you /: instead of #\, you can 0{"1[:~. to save 1 byte. \$\endgroup\$ – FrownyFrog Jun 6 '18 at 9:24
  • \$\begingroup\$ And "0 1 is "{ \$\endgroup\$ – FrownyFrog Jun 6 '18 at 9:26
  • \$\begingroup\$ @FrownyFrog Thanks, once again! \$\endgroup\$ – Galen Ivanov Jun 6 '18 at 10:48
  • 1
    \$\begingroup\$ this is gorgeous. \$\endgroup\$ – Jonah Jun 7 '18 at 4:19
  • \$\begingroup\$ @Jonah Yes, thanks to FrownyFrog! \$\endgroup\$ – Galen Ivanov Jun 7 '18 at 6:14
4
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Using match was a poor decision of mine. You can outgolf me some more. :-) \$\endgroup\$ – Arnauld Jun 6 '18 at 7:49
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

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

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!

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

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

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

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.

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

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Here's a 9 (separate answer since it's a very different algo, though it does share the ¥η). \$\endgroup\$ – Grimy May 7 at 15:47
  • \$\begingroup\$ @Grimy Are you going through all my 05AB1E answers and golf each of them, haha? ;p Nice answer though (yet again), +1 from me. \$\endgroup\$ – Kevin Cruijssen May 7 at 16:02
  • 1
    \$\begingroup\$ Not all of them, I'm just going through those linked in this post. \$\endgroup\$ – Grimy May 7 at 16:08
  • \$\begingroup\$ @Grimy Ah ok, that makes sense. :) \$\endgroup\$ – Kevin Cruijssen May 7 at 16:13
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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! \$\endgroup\$ – Laikoni Jun 6 '18 at 16:24
  • \$\begingroup\$ 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<-...=. \$\endgroup\$ – Laikoni Jun 6 '18 at 16:31
  • \$\begingroup\$ Furthermore you can use a list comprehension instead of filter, !!0 instead of head and cycle instead of concat$repeat: Try it online! \$\endgroup\$ – Laikoni Jun 6 '18 at 17:43
  • \$\begingroup\$ @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. \$\endgroup\$ – misja111 Jun 7 '18 at 18:09
  • \$\begingroup\$ 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. \$\endgroup\$ – Laikoni Jun 7 '18 at 18:38
1
\$\begingroup\$

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

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

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
}
\$\endgroup\$
  • \$\begingroup\$ The whole first part can be ~(.skip Z-$_) \$\endgroup\$ – Jo King May 8 at 4:30
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

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