Monday Mini-Golf: Une série de courts défis de golf à code , affichés (espérons-le!) Tous les lundis.

Une séquence de type Fibonacci est obtenue en utilisant la même méthode que la célèbre séquence de Fibonacci ; c'est-à-dire que chaque nombre F (n) est trouvé en ajoutant les deux nombres précédents dans la séquence ( F (n) = F (n-1) + F (n-2) ), ou en soustrayant les deux nombres suivants ( F (n) = F (n + 2) - F (n + 1) ). La principale différence est que ces séquences peuvent commencer par deux nombres quelconques. L'indexation zéro de ces séquences est contestable, mais pour l'instant, nous allons utiliser cette règle:

• Le 0ème nombre dans une séquence de type Fibonacci est le dernier nombre qui est plus petit que le nombre précédent.

À titre d'exemple, la séquence de Fibonacci pourrait être écrite ainsi 1, 0, 1, 1, 2, 3, 5..., donc le 0ème numéro de la séquence est le seul 0.

Défi

L'objectif du défi est d'écrire un programme ou une fonction qui accepte trois entiers, dans n'importe quel format:

• A et B , les deux nombres avec lesquels commencer à générer une séquence.
• N , la longueur de la séquence résultante à émettre.

Et sort les N premiers nombres de la séquence, en commençant au 0e.

Détails

• A , B et N peuvent être pris dans n'importe quel ordre et format, tant qu'ils sont visiblement séparés. Si vous utilisez un ordre / format différent, veuillez préciser de quoi il s'agit.
• Vous pouvez supposer que A , B et N sont toujours des entiers positifs.
• Vous pouvez supposer que N n'est pas supérieur à 100 et que la séquence résultante ne contiendra pas x >= 2^31.
• Si A est plus grand que B , alors B est le numéro 0 de la séquence.
• La sortie doit être séparée par des espaces, des virgules et / ou des retours à la ligne.
• Un espace de fin ou une nouvelle ligne est autorisé, mais pas une virgule de fin.

Cas de test

Exemple 1:

8 13 10

En travaillant en arrière 8 13jusqu'à ce que nous trouvions un nombre plus grand que le précédent, nous obtenons 13 8 5 3 2 1 1 0 1. Ainsi, 0est le 0e nombre dans cette séquence. À partir de là, nous imprimons 0et les 9 membres suivants:

0 1 1 2 3 5 8 13 21 34

Exemple 2:

23 37 5

Encore une fois en arrière pour trouver le numéro 0, nous trouvons 37 23 14 9 5 4 1 3. Le 0ème numéro est cette fois 1, donc nous l'imprimons avec les 4 membres suivants:

1 4 5 9 14

Exemple 3:

4 3 8

Avec celui-ci, nous n'avons pas besoin de travailler en arrière pour trouver le numéro 0, car il 3est plus petit que 4:

3 7 10 17 27 44 71 115

Exemple 4:

29 47 11

Résultat:

1 3 4 7 11 18 29 47 76 123 199

Notation

Il s'agit de code-golf , donc le code valide le plus court en octets l'emporte. Tiebreaker revient à une soumission publiée plus tôt. Le gagnant sera choisi lundi 28 septembre prochain. Bonne chance!

Edit: Félicitations à votre gagnant, @Jakube, en utilisant Pyth pour un incroyable 23 octets!

Pyth, 23 octets

AQWgHGA,-HGG)VvwHA,H+GH

Essayez-le en ligne: démonstration ou suite de tests

Style assez inhabituel de programmation Pyth. Parfois, la programmation fonctionnelle a ses inconvénients.

Explication:

AQWgHGA,-HGG)VvwHA,H+GH  Q = input list of the two starting numbers
AQ                       G, H = Q (unpacking Q)
  WgHG                   while H >= G:
      A,-HGG                G, H = [H - G, G]
            )            end while
              vw         read a number from input
             V           for N in range(^):
                H           print H
                 A,H+GH     G, H = [H, G + H]

Rétine , 65 54 octets

+`(1*),\1(1*)
$2,$1
+`(1*)(,1*);1\B
$1$2$2$1;
^1*,|;1
<empty>

Ici, <empty>représente une ligne de fin vide. Exécutez le code en tant que fichier unique avec l' -sindicateur.

Le format d'entrée est

A,B;N

où les nombres sont représentés en unaire . La sortie est une liste séparée par des virgules, également en unaire. Par exemple:

8 13 10

serait

11111111,1111111111111;1111111111

et rendement

,1,1,11,111,11111,11111111,1111111111111,111111111111111111111,1111111111111111111111111111111111

Explication

+`(1*),\1(1*)
$2,$1

Tout d'abord, nous réduisons Aet Bau 0ème et -1ème élément. Le +dit à Retina de continuer à répéter cette substitution d'expression régulière jusqu'à ce que l'expression régulière cesse de correspondre ou que la substitution ne modifie pas la chaîne. Le regex capture Adans le groupe 1 avec (1*), puis s'assure qu'il Best au moins aussi grand que Alors de la capture B-Aavec \1(1*)dans le groupe 2. Cela garantit que cette boucle se termine une fois A>B.

La substitution se transforme simplement A,Ben B-A,Adéfinissant la correspondance sur $2,$1.

+`(1*)(,1*);1\B
$1$2$2$1;

Maintenant, nous avons déjà le premier numéro de la sortie requise dans la chaîne (ainsi que celui précédent, dont nous devrons nous débarrasser plus tard). Cette substitution ajoute maintenant un autre nombre comme la somme des deux derniers nombres tout en prenant un 1de N. Parce que nous avons déjà un numéro, nous voulons que cela se produise uniquement N-1. Nous faisons cela en veillant à ce \Bqu'il y ait encore au moins ;11à la fin de la chaîne. Si nous appelons les deux dernières valeurs de la séquence Cet D, alors l'expression rationnelle capture Cdans le groupe 1 et ,Ddans le groupe deux. Nous les réécrivons avec $1$2. Ensuite, nous écrivons également $2$1ce qui se traduit par ,D+C. Notez que nous ne réécrivons pas le single 1dans lequel nous avons fait correspondreN, le décrémentant ainsi.

^1*,|;1
<empty>

Enfin, il faut se débarrasser de l' élément -1er de la séquence, ainsi les restes ;1de N, que nous faisons tout simplement en faisant correspondre soit de ceux -ci et de le remplacer par la chaîne vide.

Python 2, 93 87 67 61 60 octets

i,j,l=input()
while j/i:i,j=j-i,i
exec"i,j=j,i+j;print i;"*l

Obtient l'entrée (sous forme de liste python littérale [8,10,13])

Élabore le 0e mandat

Imprime ensuite la séquence des ajouts jusqu'à ce que la longueur soit atteinte

CJam, 26 23 octets

Merci à Dennis d'avoir économisé 3 octets.

q~{_@\-_g)}g\@{_@+_p}*t

Prend les entrées dans l'ordre N B A(séparées par tout type d'espace blanc). Imprime le résultat sous forme de liste séparée par des sauts de ligne et se termine par une erreur .

Testez-le ici.

Explication

Cela va encore plus loin lors de la recherche du 0ème élément. Autrement dit, il se termine une fois que l'une des valeurs est négative.

q~      e# Read and evaluate input, pushing N, B and A on the stack.
{       e# do while...
  _@\-  e#   B, A = A, B-A
  _W>   e#   Check if A is still non-negative.
}g
\@      e# Reorder N B A into A B N.
{       e# Run the following N times...
  _@+   e#   A, B = B, A+B
  _p    e#   Print B.
}*
t       e# The last A, B are still on the stack. We remove them by trying to
        e# execute a ternary operator: it pops the first two values but then
        e# terminates the program with an error, because there is no third value.

Labyrinthe , 58 54 49 46 44 octets

Merci à Sp3000 d'avoir suggéré l'utilisation de la négation au niveau du bit, ce qui a permis d'économiser deux octets.

??#"{=
  ;  -
@"~~:}
~""
?
"}}:=
(   +
{{\!:

Le format d'entrée est B A N. Le résultat est une liste séparée par des sauts de ligne.

Explication

(Légèrement dépassé. L'idée de base est toujours la même, mais la disposition du code est différente maintenant.)

Cela utilise la même idée que ma réponse CJam (donc les crédits vont toujours à Dennis): lors du retour en arrière de la séquence, nous ne nous arrêtons pas jusqu'à ce que nous obtenions une valeur négative (ce qui nous laisse avec les éléments -1er et -2nd de la séquence). Ensuite, nous commençons à les ajouter avant d' imprimer la première valeur.

Cela utilise quelques astuces de golf astucieuses dans le Labyrinthe. Passons en revue le code dans les sections:

?"
}

L'IP commence à ?droite (qui lit A). Sur le "(un no-op), il frappe une impasse, donc il se retourne, exécutant à ?nouveau (lecture B). Enfin, }passe Bà la pile auxiliaire. L'impasse sauve un octet sur les naïfs

?
?
}

Maintenant la boucle qui trouve le début de la séquence:

)(:{
"  -
" "`?...
=}""

Le )((incrément-décrément) est un no-op, mais il est nécessaire de s'assurer que le haut de la pile est positif sur la jonction (de sorte que l'IP tourne vers l'est). :doublons A, {se déplace BRetour à la pile principale, -calcule A-B. Ce que nous voulons vraiment B-A, c'est que `la valeur est annulée.

Il s'agit maintenant d'une jonction à quatre voies. Pour les résultats négatifs, l'IP prend un virage à gauche vers le ?, lisant Net se déplaçant vers la partie suivante du programme. Si le résultat est nul, l'IP continue de se déplacer vers le sud, prend un virage dans le coin et reste dans la boucle. Si le résultat est positif, l'IP prend un virage à droite (ouest), tourne dans le coin et prend un autre virage à droite (ouest à nouveau) afin qu'il reste également dans la boucle. Je pense que cela pourrait devenir un modèle courant pour distinguer les valeurs négatives des valeurs non négatives (ou positives des valeurs non positives):

                v
                "
               """>negative
non-negative <"""

Au moins, je n'ai pas encore pu trouver une disposition plus compacte / utile pour ce cas.

Quoi qu'il en soit, alors qu'elle An'est pas négative, la boucle continue, }se déplace Avers la pile auxiliaire et =échange Aet B.

Une fois Aest négatif, ?lit Net nous entrons dans la deuxième boucle:

 }:=+:
 }   !
?"({{\

Nous savons que Nc'est positif, nous pouvons donc compter sur l'IP en tournant à gauche (nord). Le corps de la boucle est maintenant simplement:

}}:=+:!\{{(

En mots: se déplace à la fois Net Asur la pile auxiliaire. Dupliquez B, échangez la copie avec Aet ajoutez Aà l'autre copie de B. Dupliquez-le à nouveau pour imprimer la valeur actuelle de B. Imprimez une nouvelle ligne. Déplacer Bet Nrevenir à la pile principale et décrémenter N.

Bien que Npositif, l'IP prendra un virage à droite (nord) en continuant la boucle. Une fois qu'il Natteint zéro, le code se termine de manière plutôt fantaisiste:

L'IP continue d'avancer tout droit (ouest). Le ?tente de lire un autre entier, mais nous avons déjà atteint EOF, il pousse donc à la 0place. `essaie de nier cela, mais c'est toujours zéro. Ainsi, l'IP se déplace toujours vers l'ouest, prend un virage dans le coin, puis continue de se déplacer vers le bas sur le @qui termine le programme.

Je me demande si je pourrais placer le @dans une position encore moins chère (il coûte actuellement 3 espaces blancs) en transformant les trois "autour du `no-op composé (comme )(), mais je n'ai pas encore pu faire fonctionner cela.

C, 105 102 100 octets

main(a,b,n,t){for(scanf("%d%d%d",&a,&b,&n);t=b-a,t>=0;a=t)b=a;for(;n--;b=t)t=a+b,printf("%d ",a=b);}

Merci à @ C0deH4cker d'avoir joué au golf sur 2 octets!

Essayez-le en ligne sur Ideone .

Matlab / Octave, 115 125 bytes

function x=f(x,n)
while x(2)>=x(1)
x=[abs(x(1)-x(2)) x];end
x=x([2 1]);for k=1:n-1
x=[x(1)+x(2) x];end
x=x(n:-1:1);

La fonction doit être appelée comme f([8 13],10).

Exemple (Matlab):

>> f([8 13],10)
ans =
     0     1     1     2     3     5     8    13    21    34

Ou essayez-le en ligne (Octave) .

Haskell, 67 65 56 octets

a#b|a>b=b:scanl(+)(a+b)(a#b)|1>0=(b-a)#a
n%a=take n.(a#)

Merci à @nimi pour ses suggestions

Ceci définit une fonction d'infixation ternaire %, qui est invoquée au format (n%a)b, par exemple:

> (10%8)13
[0,1,1,2,3,5,8,13,21,34]

Explication

La fonction de infix binaire #, définie sur la première ligne, prend en deux entiers aet bet renvoie l'infini séquence de type Fibonacci où aet bse produit comme éléments consécutifs.

a#b                                       -- Define a#b:
   |a>b=                                  -- if a>b, then a#b is
        b:                                -- the sequence that starts with b and
          scanl(+)     (a#b)              -- continues with the sums of prefixes of a#b
                  (a+b)                   -- plus the additional term a+b;
                            |1>0=(b-a)#a  -- otherwise, it's (b-a)#a.

La fonction %prend simplement les premiers néléments de a#b.

> <>, 33 31 + 1 pour -v = 32 octets

&:{:@(?v:}-$&
-1;!?:&<$+{oan::$&

L'entrée doit être poussée sur la pile en utilisant -v car l'analyse des nombres décimaux n'est pas triviale dans> <>.

Explication:

Je représenterai la pile après chaque (groupe de) opération. Il commence par [F (n), F (n + 1), N]

Les premières lignes descendent la série jusqu'à son 0ème terme:

& removes N from the stack to put it into a register. [F(n), F(n+1)]
:{:@ move the stack and duplicate items to get [F(n+1), F(n), F(n+1), F(n)]
(?v compares the two top items of the stack and branch to the second line if F(n+1) < F(n) [F(n+1), F(n)]
:} move the stack and duplicate its top to get [F(n), F(n+1), F(n)]
- substracts the two top items and put the result on top of the stack [F(n), F(n+1) - F(n)]
$ switchs the top two values of the stack. [F(n+1) - F(n), F(n)]
& retrieve the value from the register. iteration complete, since [F(n+1) - F(n), F(n), N] can also be read as [F(n-1), F(n), N]

La deuxième ligne monte la série jusqu'à ce qu'elle ait imprimé N termes:

< changes the code pointer direction to the left [F(0), F(-1)]
& retrieves the stored value back from the stack [F(0), F(-1), N]
:?!; copies N to compare it to 0, stops if it is [F(0), F(-1), N]
1- decreases it [F(0), F(-1), N-1]
& stores it back [F(0), F(-1)]
$:: makes the stack [F(-1), F(0), F(0), F(0)]
n{ prints the top of the stack then left shifts it [F(0), F(0), F(-1)]
ao displays a line feed (ascii character 0x0a) [F(0), F(0), F(-1)]
+ adds the two top values [F(0), F(-1) + F(0)]
$ switch the two top values. iteration complete since [F(-1) + F(0), F(0)] which can be read as [F(1), F(0)]

Java, 113 78 76 octets

Nous remercions ETHproduction d'avoir fourni l'algorithme que j'utilise dans cette réponse.

(a,b,n)->{for(;a<=b;b-=a)a=b-a;for(;n-->0;b+=a,a=b-a)System.out.println(b);}

Essayez ici .

Explication:

(a,b,n)->{
    for (;a<=b;b=b-a)a=b-a;  //Compute previous terms while a <= b
    for (;n-->0;b=a+b,a=b-a) //Compute and print next terms while n > 0
    System.out.println(b);   //Print term
}

Approche originale, 113 93 octets

Semble plus golfique;)

String a(int a,int b,int n){return n<0?a+" "+a(b,a+b,n+1):n>0?a>b?a(b,a+b,-n):a(b-a,a,n):"";}

Essayez-le ici .

Explication:

String a(int a, int b, int n){
    return 
    n < 0 ?                           //If n < 0
        a + " " + a(b, a + b, n + 1)  //Return a + next terms and increment n.
    :                                 //Else
        n > 0 ?                       //If n > 0
            a > b ?                   //If a > b
                a(b, a + b, -n)       //Negate n and return terms.
            :                         //If a <= b
                a(b - a, a, n)        //Generate previous term.
        :                             //If n == 0
            ""                        //Return nothing.
    ;
}

Javascript (ES6), 83 73 63 octets

Cela aurait pu être joué au maximum. Nous verrons.

(a,b,n)=>{while(a<=b)b-=a=b-a;for(;n--;console.log(a=b-a))b+=a}

Non golfé:

function f(a,b,n) {
  // repeat until we find the 0th item...
  while (a <= b) {  // if a = 5, b = 8:
    a = b - a;      // a = (8 - 5) = 3
    b = b - a;      // b = (8 - 3) = 5
  }
  // repeat n times...
  while (n-- > 0) { // if a = 5, b = 8:
    b += a;         // b = (8 + 5) = 13
    a = b - a;      // a = (13 - 5) = 8
    console.log(a); // print out each item
  }
}

Mathematica 112

Va-t-il finir par jouer au golf

z[a_, b_, n_] := (
  f[0] := Min[a, b];
  f[1] := Max[a, b];
  f[x_] := f[x - 1] + f[x - 2];
  f /@ Range[n]
  )

CJam, 40 octets

l~:A;{_@_@)<}{_@\-\}w\{A(:A0>}{_p_@+}w\;

Pas de bébé. Il s'agit de mon premier programme CJam, donc je suis fier que cela fonctionne.

Il prend la saisie sous la même forme que dans les exemples.

J'ai maintenant vu que je pouvais le réduire à 33 octets en utilisant la { ... }*construction.

l~:A;{_@_@)<}{_@-z\}w\A{_p_@+}*;;

Et je pourrais même le réduire d'une unité de plus en utilisant l'opérateur ternaire pour nettoyer la pile et produire une erreur.

Rubis, 141 octets

def u a,b,n,z=""
n<1 ? z.chop : u(b,a+b,n-1,z+"#{a} ")
end 
def d a,b,z=0
a.abs>b ? z : d(b-a,a,[a,b]) 
end 
def f a,b,n
x,y=d a,b 
u x,y,n
end 

Exécution

La fonction f produit la sortie souhaitée, les noms d'arguments correspondent aux noms de variables de la question

f(8,13,10) # returns => "0 1 1 2 3 5 8 13 21 34"

Rien d'intelligent:

• La fonction u ( up ) calcule n éléments dans la séquence fibonacci commençant par a, b en utilisant la récursivité
• La fonction d ( bas ) trouve le 0ème et le 1er élément à partir de deux éléments finaux utilisant la récursivité
• La fonction f ( fibonacci ) met les deux ensemble

Mathematica, 59 octets

If[#>#2,LinearRecurrence[{1,1},#2+{0,#},#3],#0[#2-#,#,#3]]&

Rubis, 81 75 73

a,b,n=23,37,5;while(c=b-a)<a;b,a=a,c;end;p a;[*2..n].map{b=c+a;c,a=a,b;p b}

Raccourci de 6 octets lors du remplacement de for-loop par range.map

a,b,n=23,37,5;while(c=b-a)<a;b,a=a,c;end;p a;[*2..n].map{p b=c+a;c,a=a,b}

Enregistré encore 2 octets en déplaçant l'instruction d'impression

Pyke, 24 octets (non concurrent)

DA/IDA-],X_r)QVDsRe
R]);

Essayez-le ici!

Gelée , 14 octets

Ḋ;_/Ɗ>/¿+⁹С/Ṗ

Essayez-le en ligne!

Lisp commun, 91 octets

(lambda(a b n)(do((x a(- y x))(y b x))((> x y)(dotimes(k n)(print y)(psetf y(+ y x)x y)))))

Essayez-le en ligne!