Uczyń mnie metazwencją

25

tło

W przypadku tego wyzwania „metazwiązka” zostanie zdefiniowana jako ciąg liczb, w którym nie tylko same liczby wzrosną, ale także przyrost, a przyrost wzrośnie o rosnącą wartość itp.

Na przykład metazwistość warstwy 3 zaczyna się jako:

1 2 4 8 15 26 42 64 93 130 176

dlatego:

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

Wyzwanie

Biorąc pod uwagę dodatnią liczbę całkowitą, wypisz pierwsze dwadzieścia elementów metazwiązania tego poziomu.

Przypadki testowe

Wkład: 3 Wyjście:[ 1, 2, 4, 8, 15, 26, 42, 64, 93, 130, 176, 232, 299, 378, 470, 576, 697, 834, 988, 1160 ]

Wkład: 1 Wyjście:[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ]

Wkład: 5 Wyjście:[ 1, 2, 4, 8, 16, 32, 63, 120, 219, 382, 638, 1024, 1586, 2380, 3473, 4944, 6885, 9402, 12616, 16664 ]

Wkład: 13 Wyjście:[ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16383, 32752, 65399, 130238, 258096, 507624 ]

Jak możesz zrozumieć, pierwsze t+1 elementów każdej sekwencji poziomu t to pierwsze t+1 potęgi 2 ...

Zasady

  • Obowiązują standardowe luki
  • To jest , więc wygrywa najkrótsza odpowiedź w bajtach
Geza Kerecsenyi
źródło
2
Zakładam, że masz na myśli 20 terminów, a nie cyfr?
Quintec
4
Nawiasem mówiąc, metazasadność
of Ignorance
6
Możesz wyjaśnić, czy rozwiązania muszą działać dla danych wejściowych 20 lub wyższych.
FryAmTheEggman
4
Czy możemy wybrać indeks 0 (więc poziom wyjściowy 1 dla danych wejściowych 0, poziom 2 dla danych wejściowych 1itp.)?
Lynn
1
@ MilkyWay90, nie jest jasne, co masz na myśli: 219 (od poziomu 5) występuje tylko w trójkącie Pascala jako i ( 219(2191) . (219218)
Peter Taylor

Odpowiedzi:

8

Galaretka , 8 7 bajtów

20ḶcþŻS

Wypróbuj online!

   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, …]

Wykorzystuje to wgląd @ alephalpha, że

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

Lynn
źródło
To jest brutalnie słabe. Po prostu niesamowite.
don bright
22

Wolfram Language (Mathematica) , 34 bajty

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

Wypróbuj online!

Metazwinność poziomu n jest sumą pierwszych n+1 elementów każdego rzędu trójkąta Pascala.

alephalpha
źródło
1
Jest do tego prawie wbudowany , ale niestety jest dłuższy.
Peter Taylor
1
Nie wiem wystarczająco dużo WL, aby zrobić coś użytecznego, ale wydaje mi się, że może skorzystać z tożsamości
T(n,k)={1if k=02T(n,k1)(k1n)otherwise
Peter Taylor
17

Haskell , 34 bajty

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

Wykorzystuje wejścia indeksowane 0 ( f 4zwraca poziom 5)

Haskell , 36 bajtów

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

Wypróbuj online! Wykorzystuje dane 1-indeksowane ( f 5zwraca poziom 5)

Wyjaśnienie

scanl (+) 1jest funkcją, która pobiera częściowe sumy listy, zaczynając od (i poprzedzając) 1.

Na przykład: scanl (+) 1 [20,300,4000]równa się [1,21,321,4321].

Okazuje się, że poziom n to właśnie ta funkcja stosowana (n1) razy do listy [1,2,3,] .

(Lub równoważnie: n razy do listy wszystkich.)

Używamy albo, initalbo, [1..20-n]aby uwzględnić, że lista staje się dłuższa o 1 każdej aplikacji.

Lynn
źródło
1
[1..20-n]nie będzie pracować dla n>20
Peter Taylor
take 20.(iterate(scanl(+)1)[1..]!!)kosztuje to tylko bajt więcej, aby to naprawić
H.PWiz
1
Twój pointfree odpowiedź może być z powrotem do 34 bajtów z wykorzystaniem drugą odpowiedź: (iterate(init.scanl(+)1)[1..20]!!).
xnor
7

Brain-Flak , 84 82 bajtów

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

Wypróbuj online!

Adnotacja

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

Wypróbuj online!

Kreator pszenicy
źródło
3
wiesz, jak zabawne jest to, że jest krótszy niż Rust
don bright
7

R , 36 bajtów

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

Wypróbuj online!

Dzięki @Giuseppe za sugestie outer.

Jest to oparte na opisanym podejściu @alephalpha

Nick Kennedy
źródło
możesz być w stanie użyć Mapzamiast zewnętrznego?
JDL
@JDL Nie widzę, jak by to działało. Potrzebuję każdej możliwej kombinacji, nie tylko par kombinacji.
Nick Kennedy
5

Python 2 , 69 58 55 bajtów

Oszczędność bajtów dzięki ovs i Jo Kingowi ; działa również w Pythonie 3.

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

Wypróbuj online!

Matematyka

Niech ( t , n ) jest z n t h termin (0 indeksowane) sekwencji w warstwie t . Mała analiza prowadzi do następującej formuły powtarzalności:a(t,n)ntht

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

Praca tyłu określamy a(0,n)=1 i a(1,n)=0 dla wszystkich n . Te definicje uprości nasz podstawowy przypadek.

Kod

Definiujemy funkcję, m(t)która zwraca pierwsze 20 elementów sekwencji na poziomie t. Jeśli tjest to nieujemne, używamy powyższej formuły rekurencyjnej; jeśli ttak -1, zwracamy pustą listę. Pusta lista działa jako przypadek podstawowy, ponieważ wynik każdego wywołania rekurencyjnego jest krojony ( [:n]), a następnie sumowany. Wycinanie pustej listy daje pustą listę, a sumowanie pustej listy daje 0. To dokładnie taki wynik chcemy, ponieważ kondygnacji 1 powinien zachowywać się jak sekwencji stałej wszystkich 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
źródło
61 bajtów jako rekurencyjna funkcja lambda (znacznie bardziej nieefektywna).
ovs
@ovs Thanks! Znalazłem jeszcze kilka bajtów, używając także innej skrzynki bazowej.
DLosc
1
(t>=0)*range(20)oszczędza bajt, chociaż prawdopodobnie jest jeszcze krótszy wyraz.
xnor
1
if~toszczędza jeszcze dwa w @xnor
Jo King
4

dzaima / APL REPL, 14 bajtów

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

Wypróbuj online!

(+\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
źródło
-1 bajt przy użyciu dzaima / APL: 1∘,1,
Adám
@ Adám oh duh .. prawo
dzaima
Pełny program o 17:(≢↑(+\1∘,)⍣⎕)20⍴1
Adám
14 bajtów przy użyciu REPL (dodaj -sflagę).
Erik the Outgolfer
Jeśli użyjesz flagi, język -szmieni się na btw (chyba że -sjest to repl flag?)
tylko ASCII
3

Pari / GP , 39 bajtów

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

Wypróbuj online!


Pari / GP , 40 bajtów

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

Wypróbuj online!


Funkcja generowania warstwy n metazwiązanie to:

ja=0nxja(1-x)ja+1=1-(x1-x)1+n1-2)x

alephalpha
źródło
3

Perl 6 , 34 32 bajty

-2 bajty dzięki Jo King

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

Wypróbuj online!

Wyjaśnienie

{                              }  # 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
źródło
29 bajtów ( $^azamiast $_jest konieczne)
Jo King
1
@JoKing Nice, ale zakłada się, że $_jest niezdefiniowany podczas wywoływania funkcji. Wolę rozwiązania, które nie zależą od stanu zmiennych globalnych.
nwellnhof
3

Python 3.8 (wersja wstępna) , 62 bajty

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

Wypróbuj online!


Wyjaśnienie

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
źródło
3

R ( 63 47 bajtów)

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

Demo online . Wykorzystuje to znormalizowaną niekompletną funkcję beta, which gives the cumulative distribution function of a binomial, and hence just needs a bit of scaling to give partial sums of rows of Pascal's triangle.

Oktawa ( 66 46 bajtów)

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

Demo online . Dokładnie ta sama koncepcja, ale nieco brzydsza, ponieważ betaincw przeciwieństwie do R pbeta, drugi i trzeci argument muszą być większe od zera.

Ogromne podziękowania dla Giuseppe za pomoc w ich wektoryzacji, przy znacznych oszczędnościach.

Peter Taylor
źródło
2

Rubinowy, 74 bajty

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}

Wersja bez golfa:

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

Dość intensywnie wykorzystujący zasoby - wersja online nie może obliczyć 13-tej częstotliwości.

Wypróbuj online

CG Jedną ręką
źródło
2

JavaScript (Node.js) , 58 bajtów

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

Wypróbuj online!

Zapisanie następującej rekurencyjnej formuły na podstawie opisanego opisu jest trywialne

g(t,i)={g(t,i1)+g(t1,i1)ifit>01ifit=0
And you just need to generate an Array of 20 elements with [g(t,0)g(t,19)]

tsh
źródło
2

05AB1E, 11 9 bytes

20LIF.¥>¨

0-indexed

Try it online or verify all test cases.

Explanation:

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
źródło
1
Nice use of !
Emigna
2

R, 59 49 bytes

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

Try it online!

Recursively Reduce with +, init=1 and accumulation=TRUE to avoid having to subset. Thanks to Criminally Vulgar for suggesting the recursive approach!

Giuseppe
źródło
tio this is only 39 bytes (using binomial approach)
Nick Kennedy
@NickKennedy that's a separate approach, so I'd recommend posting it yourself, and it's golfier to use outer than sapply for 36 bytes
Giuseppe
1
Converting this approach to a recursive function gives 53 bytes (I think in recursives we need to include the assignment? If not, 51) TIO
CriminallyVulgar
1
@CriminallyVulgar we can get to 49 bytes :-)
Giuseppe
@Giuseppe Haha I knew it was golfable, just couldn't see it! I messed with cumsum for a while to try and make it work, but that Reduce is so slick. Nice to be able to drop the index by 1 as well, didn't see that in the comments.
CriminallyVulgar
1

JavaScript (ES6),  68  67 bytes

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

Try it online!


JavaScript (ES6), 63 bytes

NB: this version works for n20.

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

Try it online!

Arnauld
źródło
1

J, 24 bytes

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

Try it online!

NOTE: Turns out this is a translation of dzaima's APL answer, though I actually didn't notice it before writing this.

explanation

<: (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
Jonah
źródło
1

Ruby, 49 bytes

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

Recursive definition: Tier 0 is 1,1,1,1... and each subsequent tier is 1 followed by a sequence whose first differences are the previous tier. Annoyingly this would give me 21 values if I didn't explicitly slice out the first 20; seems like there should be a way to shorten this by avoiding that.

histocrat
źródło
tio.run/#ruby pls
ASCII-only
also 49
ASCII-only
46
ASCII-only
1

Retina, 59 bytes

.+
19*$(_,

Replace the input with 19 1s (in unary). (The 20th value is 0 because it always gets deleted by the first pass through the loop.)

"$+"{`
)`

Repeat the loop the original input number of times.

(.+),_*
_,$1

Remove the last element and prefix a 1.

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

Calculate the cumulative sum.

_+
$.&

Convert to decimal.

Try it online!

Neil
źródło
1

Rust, 135 bytes

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

used @alephalpha 's idea, like several others. there is no builtin factorial so that takes up at least 36 bytes, (plus dealing with negatives). no builtin choose, another 16 bytes. iterator->declared vector type, 20 bytes.. etc etc.

Ungolfed at play.rust-lang.org

don bright
źródło
1
There's a better way to calculate binomial coefficients for the same cost but which allows removing the 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 bytes)
Peter Taylor
1
In fact, the binomial can be inlined: 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 bytes). What would be nice is to combine the two folds, but I'm not sure how succinct tuples are.
Peter Taylor
1
Succinct enough: 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 bytes)
Peter Taylor
thats amazing... i struggle to even understand how it works but its amazing.
don bright
It just uses one algebraic trick:
n!k!(nk)!=n!(k1)!(n(k1))!×nk+1k
Peter Taylor
1

R (60 59 bytes)

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

Online demo

Straightforward implementation of the observation

T(n,k) = 2 T(n-1,k) - binomial(n-1,k). - M. F. Hasler, May 30 2010

from OEIS A008949. The arguments to Reduce are the function (obviously), the array over which to map, the starting value, a falsy value (to fold from the left rather than the right), and a truthy value to accumulate the intermediate results in an array.

Peter Taylor
źródło
1

K (oK), 17 bytes

-1 byte thanks to ngn (switching from 0-indexed to 1-indexed)

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

Try it online!

1-indexed

K (oK), 18 bytes

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

Try it online!

0-indexed

Galen Ivanov
źródło
1
make it 1-indexed and save a byte: 1+!20 -> 20#1
ngn
@ngn Thanks, as always there's something I've missed :)
Galen Ivanov
0

Perl 5, 48 bytes

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

TIO

Nahuel Fouilleul
źródło
0

Japt, 15 bytes

0-indexed; replace h with p for 1-indexed.

ÈîXi1 å+}gNh20õ

Try it

Shaggy
źródło
0

CJam (20 bytes)

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

Online demo. This is a program which takes input from stdin and prints to stdout; for the same score an anonymous block (function) can be obtained as

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

Dissection

This applies the definition literally:

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
źródło