Étant donné deux entiers positifs p et q , votre tâche consiste à renvoyer le tableau A créé en appliquant l'algorithme suivant:

1. Commencez avec A = [p, q] et d = 2
2. Pour chaque paire (x, y) de nombres contigus dans A dont la somme est divisible par d , insérez (x + y) / d entre x et y .
3. Si au moins une paire correspondante a été trouvée, incrémentez d et passez à l'étape 2. Dans le cas contraire, arrêt et retour A .

Exemple

Voici le détail du processus pour p = 1 et q = 21 .

  1  21             | Iteration #1: we start with d = 2 and A = [1, 21]
   \/               |               1 + 21  is divisible by 2 -> we insert 11
 22/2=11            |
                    |
  1  11 21          | Iteration #2: d = 3, A = [1, 11, 21]
   \/               |               1 + 11  is divisible by 3 -> we insert 4
 12/3=4             |
                    |
  1 4 11  21        | Iteration #3: d = 4, A = [1, 4, 11, 21]
        \/          |               11 + 21 is divisible by 4 -> we insert 8
      32/4=8        |
                    |
  1    4    11 8 21 | Iteration #4: d = 5, A = [1, 4, 11, 8, 21]
    \/   \/         |               1 + 4   is divisible by 5 -> we insert 1
  5/5=1 15/5=3      |               4 + 11  is divisible by 5 -> we insert 3
                    |
  1 1 4 3 11 8 21   | Iteration #5: d = 6, A = [1, 1, 4, 3, 11, 8, 21]
                    |               no sum of two contiguous numbers is divisible by 6
                    |               -> we stop here

D'où la sortie attendue: [1, 1, 4, 3, 11, 8, 21]

Clarifications et règles

• L'entrée et la sortie peuvent être gérées dans n'importe quel format raisonnable. Les entiers p et q sont garantis supérieurs à 0. Si cela aide, vous pouvez supposer q ≥ p .
• La 2ème étape de l'algorithme ne doit pas être récursivement appliquée aux éléments qui viennent d'être insérés à la même itération. Par exemple, A = [1, 1] et d = 2 devrait conduire à [1, 1, 1] (pas une liste infinie de 1).
• C'est le code-golf , donc la réponse la plus courte en octets l'emporte!

Cas de test

  p |   q | Output
----+-----+-------------------------------------------------------------------------------
  1 |   1 | [1,1,1]
  1 |   2 | [1,2]
  1 |   3 | [1,1,2,3]
  2 |   6 | [2,1,2,1,4,1,2,6]
  3 |  13 | [3,1,8,1,3,1,7,1,2,1,5,1,3,2,13]
  9 |   9 | [9,6,9,6,9]
 60 |  68 | [60,13,1,4,31,2,3,5,2,19,64,7,13,1,2,5,2,27,44,3,4,8,2,1,12,1,5,3,28,2,4,16,1,
    |     |  2,12,1,2,1,10,1,6,68]
144 | 336 | [144,68,3,4,8,1,12,1,4,2,28,13,128,44,17,92,240,58,108,5,17,1,2,5,3,28,3,1,11,
    |     |  60,3,6,2,42,2,4,26,192,54,132,7,1,15,1,3,1,18,1,4,2,30,3,1,12,1,9,78,46,336]

Si vous souhaitez tester votre code sur un cas de test légèrement plus grand, voici la sortie attendue pour:

• p = 12096 (2 ⁶ * 3 ³ * 7)
• q = 24192 (2 ⁷ * 3 ³ * 7)

05AB1E , 28 19 18 octets

[Ðü+NÌ/‚ζ˜ʒ.ï}DŠQ#

Essayez-le en ligne!

eh, peut certainement être amélioré hardcore. travaille toujours pour refactoriser.

Probablement aussi bon que je l'obtiens.

-1 merci à qui d'autre que Emigna! Pour signaler que le swap fonctionnait mieux que les registres.

[                   // Infinite loop.
 Ð                  // Triplicate [p, ..., q]
  U                 // Pop 1 of 3 copies into register X.
   ü+               // Pairwise addition.
     NÌ/            // Divide by current iteration + 2 (which is d).
        ‚           // Group original [p, ..., q] with pairwise additives.
         ζ˜         // Transpose together and flatten.
           ʒ.ï}     // Filter out non-integer entities (includes the space added by zip).
               DXQ  // Dupe result, see if equal to original.
                  # // If new array is original array, nothing happened, quit & return.

Débogage du vidage pour [p,q] = [1,3]:

Full program: [ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
current >> [  ||  stack: []
ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
Full program: ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
current >> Ð  ||  stack: []
current >> U  ||  stack: [[1, 3], [1, 3], [1, 3]]
current >> ü  ||  stack: [[1, 3], [1, 3]]
Full program: +
current >> +  ||  stack: [1, 3]
stack > [4]
current >> N  ||  stack: [[1, 3], [4]]
current >> Ì  ||  stack: [[1, 3], [4], 0]
current >> /  ||  stack: [[1, 3], [4], 2]
current >> ‚  ||  stack: [[1, 3], [2.0]]
current >> ζ  ||  stack: [[[1, 3], [2.0]]]
current >> ˜  ||  stack: [[[1, 2.0], [3, ' ']]]
current >> ʒ  ||  stack: [[1, 2.0, 3, ' ']]
Filter: .ï
Full program: .ï
current >> .  ||  stack: [1]
stack > [1]
Full program: .ï
current >> .  ||  stack: [2.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [3]
stack > [1]
Full program: .ï
current >> .  ||  stack: [' ']
invalid literal for int() with base 10: ' '
stack > []
current >> D  ||  stack: [[1, 2.0, 3]]
current >> X  ||  stack: [[1, 2.0, 3], [1, 2.0, 3]]
current >> Q  ||  stack: [[1, 2.0, 3], [1, 2.0, 3], [1, 3]]
current >> #  ||  stack: [[1, 2.0, 3], 0]
stack > [[1, 2.0, 3]]
Full program: ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
current >> Ð  ||  stack: [[1, 2.0, 3]]
current >> U  ||  stack: [[1, 2.0, 3], [1, 2.0, 3], [1, 2.0, 3]]
current >> ü  ||  stack: [[1, 2.0, 3], [1, 2.0, 3]]
Full program: +
current >> +  ||  stack: [1, 2.0]
stack > [3.0]
Full program: +
current >> +  ||  stack: [3.0, 2.0, 3]
stack > [3.0, 5.0]
current >> N  ||  stack: [[1, 2.0, 3], [3.0, 5.0]]
current >> Ì  ||  stack: [[1, 2.0, 3], [3.0, 5.0], 1]
current >> /  ||  stack: [[1, 2.0, 3], [3.0, 5.0], 3]
current >> ‚  ||  stack: [[1, 2.0, 3], [1.0, 1.6666666666666667]]
current >> ζ  ||  stack: [[[1, 2.0, 3], [1.0, 1.6666666666666667]]]
current >> ˜  ||  stack: [[[1, 1.0], [2.0, 1.6666666666666667], [3, ' ']]]
current >> ʒ  ||  stack: [[1, 1.0, 2.0, 1.6666666666666667, 3, ' ']]
Filter: .ï
Full program: .ï
current >> .  ||  stack: [1]
stack > [1]
Full program: .ï
current >> .  ||  stack: [1.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [2.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [1.6666666666666667]
stack > [0]
Full program: .ï
current >> .  ||  stack: [3]
stack > [1]
Full program: .ï
current >> .  ||  stack: [' ']
invalid literal for int() with base 10: ' '
stack > []
current >> D  ||  stack: [[1, 1.0, 2.0, 3]]
current >> X  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
current >> Q  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3], [1, 2.0, 3]]
current >> #  ||  stack: [[1, 1.0, 2.0, 3], 0]
stack > [[1, 1.0, 2.0, 3]]
Full program: ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
current >> Ð  ||  stack: [[1, 1.0, 2.0, 3]]
current >> U  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
current >> ü  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
Full program: +
current >> +  ||  stack: [1, 1.0]
stack > [2.0]
Full program: +
current >> +  ||  stack: [2.0, 1.0, 2.0]
stack > [2.0, 3.0]
Full program: +
current >> +  ||  stack: [2.0, 3.0, 2.0, 3]
stack > [2.0, 3.0, 5.0]
current >> N  ||  stack: [[1, 1.0, 2.0, 3], [2.0, 3.0, 5.0]]
current >> Ì  ||  stack: [[1, 1.0, 2.0, 3], [2.0, 3.0, 5.0], 2]
current >> /  ||  stack: [[1, 1.0, 2.0, 3], [2.0, 3.0, 5.0], 4]
current >> ‚  ||  stack: [[1, 1.0, 2.0, 3], [0.5, 0.75, 1.25]]
current >> ζ  ||  stack: [[[1, 1.0, 2.0, 3], [0.5, 0.75, 1.25]]]
current >> ˜  ||  stack: [[[1, 0.5], [1.0, 0.75], [2.0, 1.25], [3, ' ']]]
current >> ʒ  ||  stack: [[1, 0.5, 1.0, 0.75, 2.0, 1.25, 3, ' ']]
Filter: .ï
Full program: .ï
current >> .  ||  stack: [1]
stack > [1]
Full program: .ï
current >> .  ||  stack: [0.5]
stack > [0]
Full program: .ï
current >> .  ||  stack: [1.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [0.75]
stack > [0]
Full program: .ï
current >> .  ||  stack: [2.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [1.25]
stack > [0]
Full program: .ï
current >> .  ||  stack: [3]
stack > [1]
Full program: .ï
current >> .  ||  stack: [' ']
invalid literal for int() with base 10: ' '
stack > []
current >> D  ||  stack: [[1, 1.0, 2.0, 3]]
current >> X  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
current >> Q  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
current >> #  ||  stack: [[1, 1.0, 2.0, 3], 1]
[1, 1.0, 2.0, 3]
stack > [[1, 1.0, 2.0, 3]]

Essayez-le en ligne avec débogage!

Mathematica, 72 64 59 58 octets

(d=2;#//.x_:>Riffle[x,(x+{##2,}&@@x)/d++]~Cases~_Integer)&

Essayez-le en ligne!

Comment ça marche

Nous prenons l'entrée comme une liste {p,q}. L'étape d'itération est reformulée comme suit:

1. Insérer (a+b)/dentre tous les deux éléments aet b: (x+{##2,}&@@x)calcule la séquence de a+b, avec un a+Nullà la fin. Nous divisons par det Riffleinsérons chacun (a+b)/dentre aet b. Incrément d.
2. Sélectionnez les Integeréléments de la liste résultante. (Cela supprime également le Nullintroduit par {##2,}.)

Ceci est répété jusqu'à ce que le résultat ne change pas (ce qui ne peut arriver que parce que nous avons supprimé tous les nouveaux éléments, car aucun d'entre eux n'était un entier).

-8 octets grâce à @MartinEnder d'utiliser //.au lieu de FixedPoint(et de prendre l'entrée comme une liste).

-6 de plus parce ListConvolveque ce n'est pas si bien

Ruby , 80 octets

->a,d=2{*b=a[0];a.each_cons 2{|x,y|z=x+y;b+=z%d>0?[y]:[z/d,y]};b==a ?a:f[b,d+1]}

Essayez-le en ligne!

Fonction récursive fprenant l'entrée comme tableau [p, q].

Haskell, 85 81 octets

(a:b:c)#d=a:[div(a+b)d|mod(a+b)d<1]++(b:c)#d
l#d=l
l%d|l==l#d=l|e<-d+1=l#d%e
(%2)

Essayez-le en ligne!

L'entrée est considérée comme une liste, par exemple [1,2].

Edit: -4 octets grâce à @Laikoni.

Python 2 , 112 110 108 105 103 octets

^{-2 octets grâce à Jonathan Frech
-5 octets grâce à Erik l'Outgolfer}

y=input()
x=d=1
while x!=y:
 d+=1;x=y;y=x[:1]
 for a,b in zip(x,x[1:]):c=a+b;y+=[c/d,b][c%d>0:]
print x

Essayez-le en ligne!

Python 2 , 98 octets

f=lambda A,B=0,d=2:A*(A==B)or f(sum([[(l+r)/d,r][(l+r)%d>0:]for l,r in zip(A,A[1:])],A[:1]),A,d+1)

Invoquer en tant que f([p,q]). Essayez-le en ligne!

Jonathan Allan a économisé 12 octets. Merci ~!

Explication

fest une fonction récursive: f(A, B, d)évalue à f(next_A, A, d+1), sauf A == B, auquel cas elle retourne A. (Ceci est géré par A*(A==B)or …: si A ≠ B, A*(A==B)est la liste vide, qui est faux-y, donc la …partie est évaluée; si A = B alors A*(A==B)est A, qui est non vide et donc véridique, et elle est retournée.)

next_A est calculé comme:

sum([[(l+r)/d,r][(l+r)%d>0:]for l,r in zip(A,A[1:])],A[:1])

Ceci est mieux expliqué par l'exemple. Quand d = 5 et par exemple A = [1, 4, 11, 8, 21]:

  sum([[(l+r)/d,r][(l+r)%d>0:]for l,r in zip(A,A[1:])],A[:1])
= sum([[(1+4)/d, 4], [(4+11)/d, 11], [8], [21]], [1])
= [1] + [1, 4] + [3, 11] + [8] + [21]
= [1, 1, 4, 3, 11, 8, 21]

Python 2 , 111 octets

A=input()
m=d=1
while m:
 m=o=0;d+=1
 while A[o+1:]:
	o+=1;s=A[o-1]+A[o]
	if s%d<1:A[o:o]=s/d,;m=1;o+=1
print A

Essayez-le en ligne!

-8 grâce à Rod .
-2 merci à Lynn .

Husk , 22 octets

→UG`λf£NΣẊṠeo/⁰+:.)⁰tN

Prend une liste à 2 éléments, retourne une liste d'entiers et de flottants. Essayez-le en ligne!

Explication

→UG`λf£NΣẊṠeo/⁰+:.)⁰tN  Input is a list L.
  G                 tN  Cumulative reduce over the list [2,3,4..
                   ⁰    with initial value L
   `λ             )     using flipped version of this function:
     f£NΣẊṠeo/⁰+:.       Arguments are a list, say K=[1,3,3], and a number, say d=4.
                :.       Prepend 0.5: [0.5,1,2,3]
         Ẋ               For each adjacent pair,
               +         take their sum,
            o/⁰          divide by d,
          Ṡe             and pair it with the right number in the pair: [[0.375,1],[1.0,3],[1.5,3]]
        Σ                Concatenate: [0.375,1,1.0,3,1.5,3]
     f£N                 Remove non-integers: [1,1.0,3,3]
                        Now we have an infinite list of L threaded through 2,3,4.. using the expansion operation.
 U                      Take longest prefix of unique elements,
→                       then last element of that.

Perl 5 , 92 + 1 ( -a) = 93 octets

do{$c=0;@n=shift@F;$.++;push@n,($t=$_+$n[-1])%$.?$_:($c=$t/$.,$_)for@F;@F=@n}while$c;say"@F"

Essayez-le en ligne!

Rétine , 111 octets

\d+
$*1;
^
11@
{+`(1+); (1+);
$1; $1$2 $2;
(?<=(?=(1+)).*) (\1)+ 
 a$#2$*1; 
 1+ 
 
.*a
1$&
)`a

1+@

1+
$.&
;

Essayez-le en ligne!

Prend l'entrée comme des nombres séparés par des espaces. Naïvement suit l'algorithme donné, avec la seule technique notable étant d'utiliser un symbole marqueur a, pour noter quand l'un des nombres a été conservé. Ceci est utilisé pour travailler avec les capacités de bouclage quelque peu limitées de Retina, qui vous permettent uniquement de boucler jusqu'à ce qu'un ensemble d'étages n'apporte aucun changement global à l'entrée de ces étages.

Explication:

Cela utilisera le même exemple que dans la question.

\d+
$*1;

Nous changeons le tableau de nombres en entrée en un tableau unaire séparé par des points-virgules, nous aurions donc:

1; 111111111111111111111;

^
11@

Mettez ddans notre code au début, en nous donnant:

11@1; 111111111111111111111;

{+`(1+); (1+);
$1; $1$2 $2;

C'est un peu plus compliqué. {démarre un groupe d'étapes qui seront exécutées jusqu'à ce qu'elles atteignent un point fixe. Ensuite, +indique que cette étape elle-même doit être exécutée jusqu'à un point fixe. Cette étape ajoute chaque paire de nombres adjacents mais les insère sans le point-virgule supplémentaire. Maintenant, nous aurions:

11@1; 1111111111111111111111 111111111111111111111;

(?<=(?=(1+)).*) (\1)+ 
 a$#2$*1;

L'autre étape délicate, celle-ci accumule notre diviseur dans le premier groupe de capture et remplace n'importe quel nombre de notre liste sans point-virgule de fin avec ce nombre divisé par d. Nous ajoutons également un début aà ces nombres, pour indiquer que quelque chose a été conservé, ainsi que ;pour indiquer qu'il doit faire partie de façon permanente du tableau. Maintenant, nous aurions:

11@1; a11111111111; 111111111111111111111;

 1+ 

Cela supprime les nombres qui n'étaient pas divisibles par dni dans le tableau avant ce tour. Cela ne change rien à notre exemple.

.*a
1&$

Cela correspond avec avidité du début de la chaîne à la dernière lettre ade l'entrée. Cela signifie qu'il peut y avoir au plus un match. Si nous avons apporté des modifications, nous en ajoutons une d, sinon la laissant la même afin que nous puissions quitter la boucle.

111@1; a11111111111; 111111111111111111111;

)`a

Le )ferme la boucle commencée par {(ne le remettez pas en question!) Et sinon cette étape supprime simplement les marqueurs que nous avons posés plus tôt. Comme c'est la fin de la boucle, nous répéterions les étapes ci-dessus plusieurs fois, mais je vais juste continuer comme si j'avais oublié la boucle, car cela rend l'exemple plus continu.

111@1; 11111111111; 111111111111111111111;

1+@

Cette étape supprime de notre sortie:

1; 11111111111; 111111111111111111111;

1+
$.&

Cette étape remplace les nombres unaires par des nombres décimaux:

1; 11; 21;

;

La dernière étape se débarrasse des points-virgules:

1 11 21

Évidemment, sauter la boucle nous donne un résultat incorrect ici, mais j'espère que ce n'est pas trop déroutant.

JavaScript (ES6), 89 87 82 octets

Merci @Arnauld pour -2 octets et pour avoir aidé à économiser 5 octets supplémentaires.

f=(a,d=2,r)=>a.map(v=>b.push(v,...(v+=a[++i])%d<1?[r=v/d]:[]),b=i=[])|r?f(b,d+1):a

Prend entrée sous forme de tableau: f([p,q]).

Cas de test

f=(a,d=2,r)=>a.map(v=>b.push(v,...(v+=a[++i])%d<1?[r=v/d]:[]),b=i=[])|r?f(b,d+1):a

;[[1,1],[1,2],[1,3],[2,6],[3,13],[9,9],[60,68],[144,336],[12096,24192]]
.forEach(test=>O.innerText+=JSON.stringify(test)+" -> "+JSON.stringify(f(test))+"\n")

<pre id=O></pre>

Röda , 90 octets

f a,d=2{A=[a()|slide 2|[_,(_1+_)/d]if[(_1+_2)%d=0]else[_1]]+a[-1]f A,d=d+1 if[a!=A]else A}

Essayez-le en ligne!

Java 8, 180 octets

import java.util.*;p->q->{List<Integer>r=new Stack();r.add(p);r.add(q);for(int d=1,f=d,i;f==d++;)for(i=1;i<r.size();i++)if((q=r.get(i)+r.get(i-1))%d<1)r.add(i++,q/(f=d));return r;}

Explication:

Essayez-le ici.

import java.util.*;           // Required import for List and Stack

p->q->{                       // Method with two integer parameters and List return-type
  List<Integer>r=new Stack(); //  Result-list
  r.add(p);r.add(q);          //  Add the two input-integers to the List
  for(int d=1,                //  Divisible integer (starting at 1)
          f=d,                //  Temp integer (starting at `d` / also 1)
          i;                  //  Index-integer
      f==d++;)                //  Loop (1) as long as `f` and `d` are equal
                              //  (and raise `d` by 1 so it starts at 2 inside the loop)
    for(i=1;                  //   Reset index-integer to 1
        i<r.size();i++)       //   Inner loop (2) over the List
      if((q=r.get(i)+r.get(i-1)) 
                              //    If the current + previous items (stored in `q`)
         %d<1)                //    are divisible by `d`:
        r.add(i++,q/(f=d));   //     Insert `q` divided by `d` to the List at index `i`
                              //     (and raise `i` by 1 and set `f` to `d` in the process)
                              //   End of inner loop (2) (implicit / single-line body)
                              //  End of loop (1) (implicit / single-line body)
  return r;                   //  Return the result-List
}                             // End of method

C #, 280 octets

using System.Linq;class A{static void Main(string[] p){var l=new System.Collections.Generic.List<int>(p.Select(int.Parse));int r,d=2,c;do{c=0;for(int i=1;i<l.Count;++i){if((r=l[i-1]+l[i])%d==0){l.Insert(i++,r/d);++c;}}++d;}while(c>0);l.ForEach(v=>System.Console.Write((v+" ")));}}

Première tentative de code golf, qui est tout le programme. Essaye-le

Tentative 2, 159 octets

Enlever l'échafaudage, car la tâche consiste à fournir une fonction qui peut prendre une paire de nombres (un tableau fonctionne) et renvoie un tableau. Étant donné qu'un Func <int [], int []> F peut être utilisé pour satisfaire les exigences, il suffit de définir F :

F=v=>{var l=new List<int>(v);int i,r,d=2,c;do{c=0;for(i=1;i<l.Count;++i){if((r=l[i-1]+l[i])%d==0){l.Insert(i++,r/d);++c;}}++d;}while(c>0);return l.ToArray();};

Testez le programme complet ici

Cela peut être plus petit si une liste générique est considérée comme une sortie valide (supprimez le .ToArray () pour économiser 10 octets).

Si l'entrée peut également être modifiée, le fait de passer un List <int> au lieu d'un tableau supprime la nécessité d'initialiser la sortie (sort à 126 octets).

Pour aller plus loin, il n'est pas vraiment nécessaire d'avoir une valeur de retour dans ce cas. L'utilisation d'une action à la place supprime les 9 octets utilisés par l'instruction return.

Gelée , 19 octets

®‘©‘÷@+2\⁸żFfṀR$µÐL

Essayez-le en ligne!