Fais de moi une métaséquence

25

Contexte

Pour ce défi, une `` métaséquence '' sera définie comme une séquence de nombres où non seulement les nombres eux-mêmes augmenteront, mais aussi l'incrément, et l'incrément augmentera d'une valeur croissante, etc.

Par exemple, la métaséquence de niveau 3 commencerait comme:

1 2 4 8 15 26 42 64 93 130 176

car:

    1 2 3  4  5  6  7  8   9       >-|
      ↓+↑ = 7                        | Increases by the amount above each time
  1 2 4 7  11 16 22 29 37  46  >-| <-|
                                 | Increases by the amount above each time
1 2 4 8 15 26 42 64 93 130 176 <-|

Défi

Étant donné un entier positif, affichez les vingt premiers éléments de la métaséquence de ce niveau.

Cas de test

Entrée: 3Sortie:[ 1, 2, 4, 8, 15, 26, 42, 64, 93, 130, 176, 232, 299, 378, 470, 576, 697, 834, 988, 1160 ]

Entrée: 1Sortie:[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ]

Entrée: 5Sortie:[ 1, 2, 4, 8, 16, 32, 63, 120, 219, 382, 638, 1024, 1586, 2380, 3473, 4944, 6885, 9402, 12616, 16664 ]

Entrée: 13Sortie:[ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16383, 32752, 65399, 130238, 258096, 507624 ]

Comme vous pouvez vous en rendre compte, les premiers t+1 éléments de chaque séquence de niveau t sont les premiers pouvoirs de 2 ...t+1

Règles

  • Des échappatoires standard s'appliquent
  • Il s'agit de , donc la réponse la plus courte en octets l'emporte
Geza Kerecsenyi
la source
2
Je suppose que vous voulez dire 20 termes, pas des chiffres?
Quintec
4
Soit dit en passant, la métaséquence de niveau trois est OEIS A000125
Incarnation de l'ignorance
6
Vous voudrez peut-être préciser si les solutions doivent fonctionner pour l'entrée 20 ou plus.
FryAmTheEggman
4
Pouvons-nous choisir d'indexer 0 (donc, niveau de sortie 1 pour entrée 0, niveau 2 pour entrée 1, etc.)?
Lynn
1
@ MilkyWay90, ce n'est pas très clair ce que vous voulez dire: 219 (à partir du niveau 5) ne se produit que dans le triangle de Pascal comme et ( 219(2191) . (219218)
Peter Taylor

Réponses:

8

Gelée , 8 7 octets

20ḶcþŻS

Essayez-le en ligne!

   cþ       Table of binom(x,y) where:
20Ḷ           x = [0..19]
     Ż        y = [0..n]    e.g.  n=3 → [[1, 1, 1, 1, 1, 1,  …]
                                         [0, 1, 2, 3, 4, 5,  …]
                                         [0, 0, 1, 3, 6, 10, …]
                                         [0, 0, 0, 1, 4, 10, …]]

      S     Columnwise sum.           →  [1, 2, 4, 8, 15, 26, …]

Cela utilise la perspicacité de @ alephalpha que la

meta-sequencen(i)=k=0n(ik).

Lynn
la source
C'est brutalement succint. Tout simplement génial.
Don Bright
22

Wolfram Language (Mathematica) , 34 octets

0~Range~19~Binomial~i~Sum~{i,0,#}&

Essayez-le en ligne!

La métaséquence de niveau n est la somme des n+1 premiers éléments de chaque ligne du triangle Pascal.

alephalpha
la source
1
Il y a presque une fonction intégrée pour cela , mais malheureusement, c'est plus long.
Peter Taylor
1
Je ne connais pas assez de WL pour y faire quoi que ce soit d'utile, mais il me semble qu'il pourrait bénéficier de l'identité
T(n,k)={1if k=02T(n,k1)(k1n)otherwise
Peter Taylor
17

Haskell , 34 octets

(iterate(init.scanl(+)1)[1..20]!!)

Utilise des entrées indexées 0 ( f 4renvoie le niveau 5.)

Haskell , 36 octets

f 1=[1..20]
f n=init$scanl(+)1$f$n-1

Essayez-le en ligne! Utilise des entrées indexées 1 ( f 5renvoie le niveau 5.)

Explication

scanl (+) 1est une fonction qui prend des sommes partielles d'une liste, en commençant par (et en ajoutant) 1.

Par exemple: scanl (+) 1 [20,300,4000]égal [1,21,321,4321].

Il s'avère que le niveau n est juste cette fonction appliquée (n1) fois à la liste [1,2,3,] .

(Ou de manière équivalente: n fois à une liste de tous.)

Nous utilisons soit initou [1..20-n]pour tenir compte de l'allongement de la liste en1 chaque application.

Lynn
la source
1
[1..20-n]ne va pas travailler pour n>20
Peter Taylor
take 20.(iterate(scanl(+)1)[1..]!!)ne coûterait qu'un octet de plus pour résoudre ce problème
H.PWiz
1
Votre réponse Pointfree peut être de retour à 34 octets en utilisant votre autre réponse: (iterate(init.scanl(+)1)[1..20]!!).
xnor
7

Brain-Flak , 84 82 octets

<>((()()()()()){}){({}[((()))])}{}<>{({}[(())]<<>{({}<>({}))<>}<>{}{({}<>)<>}>)}<>

Essayez-le en ligne!

Annoté

<>               Switch to the off stack
((()()()()()){}) Push 10
{({}[((()))])}{} Make twice that many 1s
<>               Switch back
{                While ...
({}[(())]<       Subtract one from the input and push 1
<>               Switch
{                For every x on the stack
({}<>({}))<>     Remove x and add it to a copy of the other TOS
}                End loop
<>{}             Remove 1 element to keep it 20
{({}<>)<>}       Copy everything back to the other stack
>)}<>            End scopes and loops

Essayez-le en ligne!

Assistant de blé
la source
3
vous savez que c'est drôle comme c'est plus court que Rust
don bright
7

R , 36 octets

rowSums(outer(0:19,0:scan(),choose))

Essayez-le en ligne!

Merci à @Giuseppe d'avoir suggéré outer.

Ceci est basé sur l' approche @alephalpha décrite

Nick Kennedy
la source
vous pourriez être en mesure d'utiliser Mapau lieu de l'extérieur?
JDL
@JDL Je ne vois pas comment cela fonctionnerait. J'ai besoin de toutes les combinaisons possibles, pas seulement de paires de combinaisons.
Nick Kennedy
5

Python 2 , 69 58 55 octets

Octets enregistrés grâce aux ovs et à Jo King ; aussi, cela fonctionne aussi dans Python 3 maintenant.

m=lambda t:[1+sum(m(t-1)[:n])for n in range(~t and 20)]

Essayez-le en ligne!

Les maths

Soit a(t,n) le terme nth (indexé 0) de la séquence au niveau t . Une petite analyse conduit à la formule de récurrence suivante:

a(t,n)=1+i=0n1a(t1,i)

En travaillant en arrière, nous définissons a(0,n)=1 et a(1,n)=0 pour tout n . Ces définitions simplifieront notre scénario de base.

Le code

Nous définissons une fonction m(t)qui renvoie les 20 premiers éléments de la séquence au niveau t. Si test non négatif, nous utilisons la formule récursive ci-dessus; si tc'est le cas -1, nous renvoyons une liste vide. La liste vide fonctionne comme un cas de base car le résultat de chaque appel récursif est découpé ( [:n]) puis additionné. Découper une liste vide donne une liste vide et additionner une liste vide donne 0. C'est exactement le résultat que nous voulons, car niveau 1 devrait se comporter comme une séquence constante de tous les 0 « s.

m=lambda t:                     # Define a function m(t):
 [          ]                   # List comprehension
     for n in range(         )  # for each n from 0 up to but not including...
                    ~n and 20   # 0 if n is -1, else 20:
  1+sum(          )             # a(t,n) = 1 + sum of
              [:n]              # the first n elements of
        m(t-1)                  # the previous tier (calculated recursively)
DLosc
la source
61 octets en tant que fonction lambda récursive (significativement plus inefficace).
OVS
@ovs Merci! J'ai également trouvé quelques octets supplémentaires en utilisant un cas de base différent.
DLosc
1
(t>=0)*range(20)enregistre un octet, bien qu'il y ait probablement une expression encore plus courte.
xnor
1
if~tsauve deux de plus sur @xnor
Jo King
4

dzaima / APL REPL, 14 octets

(+\1,19↑)⍣⎕⍳20

Essayez-le en ligne!

(+\1,19↑)⍣⎕⍳20
(       )⍣⎕     repeat the function below input times:
 +\               cumulative sum of
   1,             1 prepended to
     19          the first 19 items of the previous iteration
           20  starting with the first 20 integers
dzaima
la source
-1 octets en utilisant dzaima / APL: 1∘,1,
Adám
@ Adám oh duh .. à droite
dzaima
Programme complet à (≢↑(+\1∘,)⍣⎕)20⍴1
17h
14 octets en utilisant le REPL (ajoutez l' -sindicateur).
Erik the Outgolfer
Si vous utilisez le drapeau, la langue devient -s btw (sauf si l' -sindicateur repl?)
ASCII uniquement
3

Pari / GP , 39 octets

n->Vec(sum(i=1,n+1,(1/x-1)^-i)+O(x^21))

Essayez-le en ligne!


Pari / GP , 40 octets

n->Vec((1-(1/x-1)^-n++)/(1-2*x)+O(x^20))

Essayez-le en ligne!


n

i=0nxi(1x)i+1=1(x1x)1+n12X

alephalpha
la source
3

Perl 6 , 34 32 octets

-2 octets grâce à Jo King

{(@,{[\+] 1,|.[^19]}...*)[$_+1]}

Essayez-le en ligne!

Explication

{                              }  # Anonymous block
   ,                ...*  # Construct infinite sequence of sequences
  @  # Start with empty array
    {              }  # Compute next element as
     [\+]     # cumulative sum of
          1,  # one followed by
            |.[^19]  # first 19 elements of previous sequence
 (                      )[$_+1]  # Take (n+1)th element
nwellnhof
la source
29 octets (le $^alieu de $_est nécessaire)
Jo King
1
@JoKing Nice, mais cela suppose que cela $_n'est pas défini lors de l'appel de la fonction. Je préfère les solutions qui ne dépendent pas de l'état des variables globales.
nwellnhof
3

Python 3.8 (pré-version) , 62 octets

f=lambda n:[t:=1]+[t:=t+n for n in(n and f(n-1)[:-1]or[0]*19)]

Essayez-le en ligne!


Explication

f=lambda n:     # funtion takes a single argument
     [t:=1]     # This evaluates to [1] and assigns 1 to t
                # assignment expressions are a new feature of Python 3.8
       +        # concatenated to
     [  ....  ] # list comprehension

# The list comprehesion works together with the
# assignment expression as a scan function:
[t := t+n for n in it]
# This calculates all partial sums of it 
# (plus the initial value of t, which is 1 here)

# The list comprehension iterates
# over the first 19 entries of f(n-1)
# or over a list of zeros for n=0
 for n in (n and f(n-1)[:-1] or [0]*19)
ovs
la source
3

R ( 63 47 octets)

function(n,k=0:19)2^k*pbeta(.5,pmax(k-n,0),n+1)

Démo en ligne . Cela utilise la fonction bêta incomplète régularisée , qui donne la fonction de distribution cumulative d'un binôme, et a donc juste besoin d'un peu de mise à l'échelle pour donner des sommes partielles de lignes du triangle de Pascal.

Octave ( 66 46 octets)

@(n,k=0:19)2.^k.*betainc(.5,max(k-n,1E-9),n+1)

Démo en ligne . Exactement le même concept, mais un peu plus laid parce que betainc, contrairement aux Rpbeta , les deuxième et troisième arguments doivent être supérieurs à zéro.

Un grand merci à Giuseppe de m'avoir aidé à les vectoriser, avec des économies importantes.

Peter Taylor
la source
2

Rubis, 74 octets

a=->b{c=[1];d=0;b==1?c=(1..20).to_a: 19.times{c<<c[d]+(a[b-1])[d];d+=1};c}

Version non golfée:

def seq num
    ary = [1]
    index = 0
    if num == 1
        ary = (1..20).to_a
    else
        19.times{ary << ary[index]+seq(num-1)[index]; index+=1}
    end
    return ary
end

Beaucoup de ressources - la version en ligne ne peut pas calculer la 13e métaséquence.

Essayez-le en ligne

CG One Handed
la source
2

JavaScript (Node.js) , 58 octets

t=>Array(20).fill(t).map(g=(t,i)=>i--*t?g(t,i)+g(t-1,i):1)

Essayez-le en ligne!

g(t,i)={g(t,i1)+g(t1,i1)ifit>01ifit=0
[g(t,0)g(t,19)]

tsh
la source
2

05AB1E , 11 9 octets

20LIF.¥>¨

0 indexé

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

Explication:

20L        # Create a list in the range [1,20]
   IF      # Loop the input amount of times:
         #  Get the cumulative sum of the current list with 0 prepended automatically
       >   #  Increase each value in this list by 1
        ¨  #  Remove the trailing 21th item from the list
           # (after the loop, output the result-list implicitly)
Kevin Cruijssen
la source
1
Bonne utilisation de !
Emigna
2

R , 59 49 octets

f=function(n)`if`(n,Reduce(`+`,f(n-1),1,,T),1:20)

Essayez-le en ligne!

Récursivement Reduceavec +, init=1et accumulation=TRUEpour éviter d'avoir à sous-ensemble. Merci à Criminally Vulgar d' avoir suggéré l'approche récursive!

Giuseppe
la source
tio c'est seulement 39 octets ( en utilisant l' approche binomiale)
Nick Kennedy
@NickKennedy qui est une approche distincte, donc je recommanderais de le poster vous-même, et c'est plus golfeur à utiliser outerque sapplypour 36 octets
Giuseppe
1
La conversion de cette approche en fonction récursive donne 53 octets (je pense que dans les récursifs, nous devons inclure l'affectation? Sinon, 51) TIO
CriminallyVulgar
1
@CriminallyVulgar, nous pouvons atteindre 49 octets :-)
Giuseppe
@ Giuseppe Haha Je savais que c'était jouable au golf, je ne pouvais tout simplement pas le voir! J'ai joué avec cumsumpendant un certain temps pour essayer de le faire fonctionner, mais c'est Reducetellement lisse. Ravi de pouvoir également baisser l'indice de 1, je ne l'ai pas vu dans les commentaires.
CriminallyVulgar
1

JavaScript (ES6),  68  67 octets

f=(n,a=[...f+f])=>n--?f(n,[s=1,...a.map(x=>s-=~--x)]):a.slice(0,20)

Essayez-le en ligne!


JavaScript (ES6), 63 octets

NB: cette version fonctionne pour n20.

f=(n,a=[...Array(20-n)])=>n--?f(n,[s=1,...a.map(x=>s+=x||1)]):a

Essayez-le en ligne!

Arnauld
la source
1

J , 24 octets

<:(1+/\@,])^:[(1+i.20)"_

Essayez-le en ligne!

REMARQUE: Il s'avère que c'est une traduction de la réponse APL de dzaima, bien que je ne l'ai pas remarqué avant d'écrire ceci.

explication

<: (1 +/\@, ])^:[ (1+i.20)"_
<:                           NB. input minus 1 (left input)
                  (1+i.20)"_ NB. 1..20 (right input)
   (         )^:[            NB. apply verb in parens 
                             NB. "left input" times
   (1     , ])               NB. prepend 1 to right input
   (  +/\@   )               NB. and take scan sum
Jonas
la source
1

Rubis, 49 octets

f=->n{n<1?[1]*20:[o=1]+f[n-1][0,19].map{|x|o+=x}}

Définition récursive: le niveau 0 est 1,1,1,1...et chaque niveau suivant est 1 suivi d'une séquence dont les premières différences sont le niveau précédent. De façon ennuyeuse, cela me donnerait 21 valeurs si je ne découpais pas explicitement les 20 premiers; semble qu'il devrait y avoir un moyen de raccourcir cela en évitant cela.

histocrate
la source
tio.run/#ruby pls
ASCII uniquement
également 49
ASCII uniquement
46
uniquement ASCII
1

Rétine , 59 octets

.+
19*$(_,

Remplacez l'entrée par 19 1 s (en unaire). (La 20e valeur est 0 car elle est toujours supprimée lors du premier passage dans la boucle.)

"$+"{`
)`

Répétez la boucle le nombre d'entrées d'origine.

(.+),_*
_,$1

Supprimer le dernier élément et préfixer un 1 .

_+(?<=((_)|,)+)
$#2*

Calculez la somme cumulée.

_+
$.&

Convertissez en décimal.

Essayez-le en ligne!

Neil
la source
1

Rouille , 135 octets

fn t(m:u64)->Vec<u64>{let f=|y|(1..=y).fold(1,|a,n|a*n);(0..20).map(|i| (0..=u64::min(i,m)).fold(0,|a,x|a+f(i)/f(x)/f(i-x))).collect()}

a utilisé l'idée de @alephalpha, comme plusieurs autres. il n'y a pas de factoriel intégré, ce qui prend au moins 36 octets (plus le traitement des négatifs). aucun choix intégré, 16 autres octets. itérateur-> type de vecteur déclaré, 20 octets .. etc etc.

Non golfé sur play.rust-lang.org

Don Bright
la source
1
Il existe une meilleure façon de calculer les coefficients binomiaux pour le même coût, mais qui permet de supprimer min: fn t(m:i64)->Vec<i64>{let b=|n,k|(1..=k).fold(1,|a,j|a*(n-j+1)/j);(0..20).map(|i|(0..=m).fold(0,|a,x|a+b(i,x))).collect()}(122 octets)
Peter Taylor
1
En fait, le binôme peut être inséré: fn t(m:i64)->Vec<i64>{(0..20).map(|i|(0..=m).fold(0,|a,x|a+(1..=x).fold(1,|a,j|a*(i-j+1)/j))).collect()}(104 octets). Ce qui serait bien, c'est de combiner les deux plis, mais je ne sais pas à quel point les tuples sont succincts.
Peter Taylor
1
Assez succinct: fn t(m:i64)->Vec<i64>{(0..20).map(|i|(0..=m).fold((0,1),|a,b|(a.0+a.1,a.1*(b-i)/!b)).0).collect()}(98 octets)
Peter Taylor
c'est incroyable ... j'ai du mal à comprendre comment cela fonctionne mais c'est incroyable.
don bright
Il utilise juste une astuce algébrique:
n!k!(n-k)!=n!(k-1)!(n-(k-1))!×n-k+1k
Peter Taylor
1

R ( 60 59 octets)

function(n)Reduce(function(p,q)2*p-choose(q-1,n),1:19,1,,1)

Démo en ligne

Mise en œuvre simple de l'observation

T (n, k) = 2 T (n-1, k) - binôme (n-1, k). - MF Hasler, 30 mai 2010

à partir de OEIS A008949 . Les arguments pour Reducesont la fonction (évidemment), le tableau sur lequel mapper, la valeur de départ, une valeur fausse (à replier de gauche plutôt que de droite), et une valeur vraie pour accumuler les résultats intermédiaires dans un tableau.

Peter Taylor
la source
1

K (oK) , 17 octets

-1 octet grâce à ngn (passage de l'index 0 à l'index 1)

{x(+\1,19#)/20#1}

Essayez-le en ligne!

1 indexé

K (oK) , 18 octets

{x(+\1,19#)/1+!20}

Essayez-le en ligne!

0 indexé

Galen Ivanov
la source
1
le rendre indexé 1 et enregistrer un octet: 1+!20->20#1
ngn
@ngn Merci, comme toujours il y a quelque chose que j'ai manqué :)
Galen Ivanov
0

Perl 5, 48 octets

$x=1,@A=(1,map$x+=$_,@A[0..18])for 0..$_;$_="@A"

TIO

Nahuel Fouilleul
la source
0

CJam (20 octets)

1aK*{1\{1$+}/;]}q~*p

Démo en ligne . C'est un programme qui prend l'entrée de stdin et imprime sur stdout; pour le même score, un bloc (fonction) anonyme peut être obtenu

{1aK*{1\{1$+}/;]}@*}

Dissection

Cela applique la définition littéralement:

1aK*      e# Start with an array of 20 1s
{         e# Loop:
  1\      e#   Push a 1 before the current list
  {1$+}/  e#   Form partial sums (including that bonus 1)
  ;]      e#   Ditch the last and gather in an array (of length 20)
}
q~*       e# Take input and repeat the loop that many times
p         e# Pretty print
Peter Taylor
la source