Défi

Étant donné une séquence de nombres, créez une fonction qui renvoie les étapes de la séquence.

• Supposons qu'une séquence sera N >= 3
• La séquence répétera les étapes au moins une fois
• La séquence ne contiendra que des nombres naturels
• Votre fonction ou programme doit retourner la séquence d'étapes la plus courte possible

Exemple:

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

Production: [1, 1, 2]

Explication: La séquence initiale va de 1 => 2 (1 step), 2 => 3 (1 step), 3 => 5 (2 steps). Ensuite, il se répète. La sortie est alors[1 step, 1 step, 2 steps] => [1, 1, 2]

Un autre exemple:

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

Production: [3, 1, 1, 1]

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

Cas de test

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

• La longueur d'entrée - 1 est divisible par la longueur de sortie
• Supposons que la séquence va toujours augmenter

C'est le code-golf , donc la réponse la plus courte en octets gagne.

Gelée , 9 7 octets

IsJEƇḢḢ

Essayez-le en ligne!

Comment ça fonctionne

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 octets

Génère une chaîne séparée par des virgules (avec une virgule de début).

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

Essayez-le en ligne!

Ou 56 octets si nous utilisons ,-comme séparateur et nous supposons que la séquence est toujours strictement croissante.

Comment?

Nous convertissons d'abord le tableau d'entrée a [] en une liste de différences consécutives avec:

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

Parce que p est initialement défini sur une valeur non numérique (la fonction de rappel de map () ), la première itération donne NaN .

Exemple:

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

Nous contraignons ensuite le résultat à une chaîne:

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

Enfin, nous recherchons le modèle ¹ le plus court d'entiers séparés par des virgules ( ,\d+) commençant juste après "NaN" et se répétant jusqu'à la fin de la chaîne:

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

_{1: utiliser le non gourmand *?}

Brachylog , 11 octets

s₂ᶠ-ᵐṅᵐ~j₍t

Essayez-le en ligne!

Serait de 5 octets s'il y avait un intégré pour les différences consécutives.

Explication

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 octets

<J.+Qf.<IJT

Essayez-le ici

Explication

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

äa
¯@eUéX}aÄ

Essayez-le

Explication

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

Essayez-le

R , 49 46 octets

Programme complet:

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

Essayez-le en ligne!

R , 72 58 54 octets

Soumission de la fonction d'origine avec tous les cas de test en un seul endroit:

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

Essayez-le en ligne!

Merci à JayCe pour avoir suggéré l'itinéraire complet du programme et -4 octets sur la fonction, et à Giuseppe pour -3.

J , 22 19 octets

3 octets économisés grâce à FrownyFrog!

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

Essayez-le en ligne!

[Essayez-le en ligne!] [TIO-ji2uiwla]

Comment?

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

Enregistré 3 octets grâce à Kevin Cruijssen .

¥.œʒË}нн

Essayez-le en ligne!

05AB1E , 11 octets

āεI¥ô}ʒË}нн

Essayez-le en ligne!

āεI ¥ ô} ʒË} нн Programme complet.
à Plage de longueurs. Appuyez sur [1 ... len (inp)].
 ε} Pour chaque ...
  I ¥ ô ... Coupez les deltas en morceaux de la taille correspondante
      ʒË} Ne gardez que ceux qui ont tous leurs éléments égaux.
         нн Et récupérez d'abord le premier élément du premier.

13 octets

Une alternative mignonne, l'OMI:

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

Essayez-le en ligne!

¥©ηʒ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 octets

Modifier 7 octets enregistrés merci (devinez qui?) Arnauld

Même idée regex qu'Arnauld, mais curieusement si différente dans la mise en œuvre ...

Renvoyer une chaîne avec des étapes séparées par une virgule (et une virgule de début)

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

Tester

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 octets

dt5YLFTF#Xu)

Essayez-le en ligne!

Je viens de découvrir que MATL a une fonction circulante!

Explication

d - Obtenez les différences entre les termes successifs, sous forme de tableau

t5YL- dupliquez cela, puis appelez la fonction YL('galerie') avec l' 5option ('circulant'). Crée une matrice avec le vecteur donné comme première ligne, puis les lignes successives sont le même vecteur décalé circulairement, jusqu'à ce qu'il s'enroule.

FTF#Xu- Vérifiez les lignes uniques et obtenez leurs numéros de ligne (vous ne savez pas s'il existe un moyen plus court de le faire). Lorsque les étapes de séquence se répètent, la ligne décalée circulairement sera la même que la première ligne et les lignes suivantes seront répétées. Ainsi, cela obtient les indices de la première série d'étapes de séquence avant de commencer à se répéter.

) - indexer en utilisant cela dans le tableau des différences d'origine, pour obtenir la réponse.

Plus âgée:

d`tt@YS-a}@:)

Essayez-le en ligne!

(-1 octet grâce à Giuseppe)

Explication:

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 octets

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]

Essayez-le en ligne!

Génère d' abord les deltas d , puis trouve le premier préfixe p de d qui, répété ⌊len (L) / len (p) ⌋ fois, donne L , où L est la liste d'entrée.

Rubis , 62 octets

S'appuie sur la logique Regex adaptée de la réponse d' Arnauld .

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

Essayez-le en ligne!

Détermination alternative des différences de pas, également 62 octets:

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

Essayez-le en ligne!

Java 10, 104 100 octets

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

Regex ( ?.+?)\1*$pour répéter la plus courte de la sous - chaîne @Neil 's commentaire sur @Arnauld ' JavaScript s (ES6) réponse .

Essayez-le en ligne.

Explication:

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 octets

Demander l'entrée.

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

Essayez-le en ligne! Gracieuseté de Dyalog Classic

Explication:

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 octets

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)

Essayez-le en ligne!

Construisez les différences comme d; si drépète avec la taille de l'unité, nalors d[n:]==d[:-n]; sinon recurse.

Retina 0.8.2 , 42 octets

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

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

Essayez-le en ligne! Le lien inclut des cas de test. La sortie inclut une virgule principale. Explication:

\d+
$*

Convertissez en unaire.

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

Calculez les différences avant, à l'exception du premier nombre, qui est laissé pour compte.

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

Faites correspondre les différences récurrentes.

1+
$.&

Convertissez en décimal.

05AB1E , 14 13 octets

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

Essayez-le en ligne ou vérifiez tous les cas de test .

Je sais qu'il y a déjà deux réponses 05AB1E plus courtes publiées par @ Mr.Xcoder , mais je voulais essayer cette approche alternative en utilisant la rotation et le contrôle d'égalité.
Pourrait être capable de jouer au golf sur quelques octets sans perdreÁ .

-1 octet après une pointe de @Emigna pour supprimer les registres global_variable ( ©et 2x ®) et utiliser un Duplicate ( D) et un Triplicate (Ð ).

Explication:

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

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

x est le tableau d'entrée.

Stax , 8 6 octets

░»F\☺»

Exécuter et déboguer

Voici une version annotée non emballée pour montrer comment cela fonctionne.

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

Exécutez celui-ci

Perl 6 , 57 octets

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

Essaye-le

La sortie est séparée par des espaces ( "1 1 2")

Étendu:

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

¥©η.ΔÞ®Å?

Explication:

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

¥η.ΔÞ.¥-Ë

Même algo, mais au lieu de comparer à la liste des deltas (qui doit être sauvegardée / restaurée), cela utilise .¥(undelta) puis se compare à l'entrée (implicite).

Essayez-le en ligne!

K4 , 30 octets

Solution:

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

Exemples:

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

Explication:

Semble lourd pour ce que nous essayons de résoudre. Obtenez les deltas de l'entrée, puis créez des séquences et déterminez la plus courte qui lui correspond.

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

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

Essayez-le en ligne!

Renvoie un Sequencecontenant les étapes.

+2 octets pour la Listsortie:

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

Essayez-le en ligne!

Perl 5 -p , 55 octets

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

Essayez-le en ligne!

Les nombres sont entrés sous forme de liste séparée par des espaces. La sortie est du même format.