Herausforderung

Erstellen Sie bei einer gegebenen Zahlenfolge eine Funktion, die die Folgenschritte zurückgibt.

• Angenommen, eine Sequenz wäre N >= 3
• Die Sequenz wird die Schritte mindestens einmal wiederholen
• Die Sequenz enthält nur natürliche Zahlen
• Ihre Funktion oder Ihr Programm sollte die kürzestmögliche Folge von Schritten zurückgeben

Beispiel:

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

Ausgabe: [1, 1, 2]

Erläuterung: Die Anfangssequenz geht von aus 1 => 2 (1 step), 2 => 3 (1 step), 3 => 5 (2 steps). Dann wiederholt es sich. Die Ausgabe ist dann[1 step, 1 step, 2 steps] => [1, 1, 2]

Ein anderes Beispiel:

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

Ausgabe: [3, 1, 1, 1]

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

Testfälle

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]

Klarstellungen

• Die Eingabelänge - 1 ist durch die Ausgabelänge teilbar
• Angenommen, die Reihenfolge wird immer größer

Das ist Code-Golf , also gewinnt die kürzeste Antwort in Bytes.

Gelee , 9 7 Bytes

IsJEƇḢḢ

Probieren Sie es online!

Wie es funktioniert

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.

JavaScript (ES6), 58 Byte

Gibt eine durch Kommas getrennte Zeichenfolge aus (mit einem führenden Komma).

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

Probieren Sie es online!

Oder 56 Bytes, wenn wir ,-als Trennzeichen verwenden und davon ausgehen, dass die Reihenfolge immer strikt ansteigt.

Wie?

Wir konvertieren zuerst das Eingabearray a [] in eine Liste aufeinanderfolgender Unterschiede mit:

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

Da p anfänglich auf einen nicht numerischen Wert gesetzt ist (die Rückruffunktion von map () ), ergibt die erste Iteration NaN .

Beispiel:

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

Wir setzen das Ergebnis dann in eine Zeichenkette um:

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

Schließlich suchen wir nach dem kürzesten ^1- Muster von durch Kommas getrennten ganzen Zahlen ( ,\d+), die direkt nach "NaN" beginnen und sich bis zum Ende der Zeichenfolge wiederholen:

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

_{1: mit der nicht gierig *?}

Brachylog , 11 Bytes

s₂ᶠ-ᵐṅᵐ~j₍t

Probieren Sie es online!

Würden 5 Bytes sein, wenn es für aufeinanderfolgende Unterschiede ein eingebautes gäbe.

Erläuterung

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]

Pyth, 11 Bytes

<J.+Qf.<IJT

Probieren Sie es hier aus

Erläuterung

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

Japt , 14 12 Bytes

äa
¯@eUéX}aÄ

Versuch es

Erläuterung

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

Versuch es

R , 49 46 Bytes

Volles Programm:

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

Probieren Sie es online!

R , 72 58 54 Byte

Originale Funktionsübermittlung mit allen Testfällen an einem Ort:

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

Probieren Sie es online!

Vielen Dank an JayCe für den Vorschlag der vollständigen Programmroute und -4 Bytes für die Funktion und an Giuseppe für weitere -3 Bytes.

J , 22 19 Bytes

3 Bytes gespart dank FrownyFrog!

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

Probieren Sie es online!

[Online ausprobieren!] [TIO-ji2uiwla]

Wie?

                 -      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

05AB1E , 8 Bytes

3 Bytes gespart dank Kevin Cruijssen .

¥.œʒË}нн

Probieren Sie es online!

05AB1E , 11 Bytes

āεI¥ô}ʒË}нн

Probieren Sie es online!

āεI ¥ ô} ʒË} нн Volles Programm.
à Längenbereich. Drücken Sie [1 ... len (inp)].
 ε} Für jeden ...
  I ¥ ô ... Schneide die Deltas in Stücke der entsprechenden Größe
      ʒË} Behalte nur diejenigen bei, deren Elemente alle gleich sind.
         Í And Und zuerst das erste Element des ersten abrufen.

13 Bytes

Eine süße Alternative, IMO:

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

Probieren Sie es 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.

Javascript, 49 56 Bytes

Edit 7 Bytes gespeichert danke (raten Sie mal, wer?) Arnauld

Selbe Regex-Idee wie Arnauld, aber seltsamerweise so unterschiedlich in der Umsetzung ...

Rückgabe einer Zeichenfolge mit durch Kommas getrennten Schritten (und einem führenden Komma)

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

Prüfung

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

MATL , 14 13 12 Bytes

dt5YLFTF#Xu)

Probieren Sie es online!

Gerade entdeckt, dass MATL eine Kreislauffunktion hat!

Erläuterung

d - Ermitteln Sie die Unterschiede zwischen aufeinanderfolgenden Begriffen als Array

t5YL- duplizieren Sie das und rufen Sie dann die Funktion YL('gallery') mit der 5Option ('circulant') auf. Erstellt eine Matrix mit dem angegebenen Vektor als erste Zeile, dann werden aufeinanderfolgende Zeilen mit demselben Vektor zirkular verschoben, bis sie umbrochen werden.

FTF#Xu- Suchen Sie nach eindeutigen Zeilen und ermitteln Sie deren Zeilennummern (nicht sicher, ob dies auf kürzere Weise möglich ist). Wenn sich die Sequenzschritte wiederholen, ist die kreisförmig verschobene Reihe dieselbe wie die erste Reihe, und die nachfolgenden Reihen werden wiederholt. Damit werden die Indizes der ersten Sequenzschritte abgerufen, bevor sie sich wiederholen.

) - Indizieren Sie dies in das ursprüngliche Differenzen-Array, um die Antwort zu erhalten.

Älter:

d`tt@YS-a}@:)

Probieren Sie es online!

(-1 Byte dank Giuseppe)

Erläuterung:

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

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]

Probieren Sie es online!

Zuerst erzeugt die Deltas d , findet dann die erste Präfix p von d , daß bei wiederholten ⌊len (L) / Len (p) ⌋ Ausbeuten mal L , wobei L die Eingangsliste ist.

Rubin , 62 Bytes

Verlässt sich auf die Regex-Logik, die von Arnauld's Antwort übernommen wurde .

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

Probieren Sie es online!

Alternative Ermittlung von Schrittdifferenzen, auch 62 Bytes:

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

Probieren Sie es online!

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*$für die kürzeste wiederholte Teilzeichenfolge aus @Neils Kommentar zur Antwort von @Arnauld auf JavaScript (ES6) .

Probieren Sie es online aus.

Erläuterung:

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

APL + WIN, 39 Bytes

Eingabeaufforderung.

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

Probieren Sie es online! Mit freundlicher Genehmigung von Dyalog Classic

Erläuterung:

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

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)

Probieren Sie es online!

Konstruiere die Unterschiede als d; wenn dwiederholt mit Einheitsgrößen dann d[n:]==d[:-n]; sonst rekursieren.

Retina 0.8.2 , 42 Bytes

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

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

Probieren Sie es online!Link enthält Testfälle. Die Ausgabe enthält das führende Komma. Erläuterung:

\d+
$*

In Unary konvertieren.

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

Berechnen Sie Vorwärtsdifferenzen mit Ausnahme der ersten Zahl, die zurückbleibt.

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

Übereinstimmende sich wiederholende Unterschiede.

1+
$.&

In Dezimalzahl konvertieren.

05AB1E , 14 13 Bytes

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

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Ich weiß, dass es bereits zwei kürzere 05AB1E-Antworten von gibt @ Mr.Xcoder gibt , aber ich wollte diesen alternativen Ansatz mithilfe von Rotation und Gleichheitsprüfung ausprobieren.
Könnte in der Lage sein, ein paar Bytes Golf zu spielen, ohne zu fallenÁ .

-1 Byte nach einem Tipp von @Emigna , um die global_variable-Register zu entfernen (© und 2x ®) und Duplicate ( D) und Triplicate () zu verwenden.Ð stattdessen ) zu verwenden.

Erläuterung:

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

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 ist das Eingabearray.

Stax , 8 6 Bytes

░»F\☺»

Führen Sie es aus und debuggen Sie es

Hier ist eine entpackte kommentierte Version, um zu zeigen, wie es funktioniert.

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

Führen Sie dieses aus

Perl 6 , 57 Bytes

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

Probier es aus

Ausgabe ist durch Leerzeichen getrennt ( "1 1 2")

Erweitert:

{      # 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
}

05AB1E , 9 Bytes

¥©η.ΔÞ®Å?

Erläuterung:

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

¥η.ΔÞ.¥-Ë

Das Gleiche gilt, aber anstatt mit der Liste der Deltas (die gespeichert / wiederhergestellt werden müssen) zu vergleichen, wird .¥(undelta) verwendet und dann mit der (impliziten) Eingabe verglichen.

Probieren Sie es online!

K4 , 30 Bytes

Lösung:

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

Beispiele:

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

Erläuterung:

Scheint heftig für das, was wir zu lösen versuchen. Holen Sie sich die Deltas der Eingabe und erstellen Sie dann Sequenzen und bestimmen Sie die kürzeste, die dazu passt.

(*&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

Wolfram Language (Mathematica) , 26 Byte

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

Probieren Sie es online!

Gibt ein zurück, Sequencedas die Schritte enthält.

+2 Bytes für die ListAusgabe:

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

Probieren Sie es online!

Perl 5 -p , 55 Bytes

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

Probieren Sie es online!

Zahlen werden als durch Leerzeichen getrennte Liste eingegeben. Die Ausgabe erfolgt im selben Format.