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 elementów każdej sekwencji poziomu to pierwsze potęgi 2 ...
Zasady
- Obowiązują standardowe luki
- To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach
źródło
0
, poziom 2 dla danych wejściowych1
itp.)?Odpowiedzi:
Galaretka ,
87 bajtówWypróbuj online!
Wykorzystuje to wgląd @ alephalpha, żemeta-sequencen(i)=∑k=0n(ik).
źródło
Wolfram Language (Mathematica) , 34 bajty
Wypróbuj online!
Metazwinność poziomun jest sumą pierwszych n+1 elementów każdego rzędu trójkąta Pascala.
źródło
Haskell , 34 bajty
Wykorzystuje wejścia indeksowane 0 (
f 4
zwraca poziom 5)Haskell , 36 bajtów
Wypróbuj online! Wykorzystuje dane 1-indeksowane (
f 5
zwraca poziom 5)Wyjaśnienie
scanl (+) 1
jest funkcją, która pobiera częściowe sumy listy, zaczynając od (i poprzedzając)1
.Okazuje się, że poziomn to właśnie ta funkcja stosowana (n−1) razy do listy [1,2,3,…] .
(Lub równoważnie:n razy do listy wszystkich.)
Używamy albo,1 każdej aplikacji.
init
albo,[1..20-n]
aby uwzględnić, że lista staje się dłuższa oźródło
[1..20-n]
nie będzie pracować dlatake 20.(iterate(scanl(+)1)[1..]!!)
kosztuje to tylko bajt więcej, aby to naprawić(iterate(init.scanl(+)1)[1..20]!!)
.Brain-Flak ,
8482 bajtówWypróbuj online!
Adnotacja
Wypróbuj online!
źródło
R , 36 bajtów
Wypróbuj online!
Dzięki @Giuseppe za sugestie
outer
.Jest to oparte na opisanym podejściu @alephalpha
źródło
Map
zamiast zewnętrznego?Python 2 ,
695855 bajtówOszczędność bajtów dzięki ovs i Jo Kingowi ; działa również w Pythonie 3.
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) nth t
Praca tyłu określamya(0,n)=1 i a(−1,n)=0 dla wszystkich n . Te definicje uprości nasz podstawowy przypadek.
Kod
Definiujemy funkcję,−1 powinien zachowywać się jak sekwencji stałej wszystkich 0 „s.
m(t)
która zwraca pierwsze 20 elementów sekwencji na poziomiet
. Jeślit
jest to nieujemne, używamy powyższej formuły rekurencyjnej; jeślit
tak-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 daje0
. To dokładnie taki wynik chcemy, ponieważ kondygnacjiźródło
(t>=0)*range(20)
oszczędza bajt, chociaż prawdopodobnie jest jeszcze krótszy wyraz.if~t
oszczędza jeszcze dwa w @xnordzaima / APL REPL, 14 bajtów
Wypróbuj online!
źródło
1∘,
→1,
(≢↑(+\1∘,)⍣⎕)20⍴1
-s
flagę).-s
zmieni się na btw (chyba że-s
jest to repl flag?)Pari / GP , 39 bajtów
Wypróbuj online!
Pari / GP , 40 bajtów
Wypróbuj online!
Funkcja generowania warstwyn metazwiązanie to:
źródło
Perl 6 ,
3432 bajty-2 bajty dzięki Jo King
Wypróbuj online!
Wyjaśnienie
źródło
$^a
zamiast$_
jest konieczne)$_
jest niezdefiniowany podczas wywoływania funkcji. Wolę rozwiązania, które nie zależą od stanu zmiennych globalnych.Python 3.8 (wersja wstępna) , 62 bajty
Wypróbuj online!
Wyjaśnienie
źródło
R (
6347 bajtów)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 (
6646 bajtów)Demo online . Dokładnie ta sama koncepcja, ale nieco brzydsza, ponieważ
betainc
w przeciwieństwie do Rpbeta
, 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.
źródło
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:
Dość intensywnie wykorzystujący zasoby - wersja online nie może obliczyć 13-tej częstotliwości.
Wypróbuj online
źródło
Wolfram Language (Mathematica) , 42 bajty
Wypróbuj online!
źródło
JavaScript (Node.js) , 58 bajtów
Wypróbuj online!
Zapisanie następującej rekurencyjnej formuły na podstawie opisanego opisu jest trywialnesol( t , i ) = { g( t , i - 1 ) + g( t - 1 , i - 1 )1Jeślii⋅t>0ifi⋅t=0
And you just need to generate an Array of 20 elements with [g(t,0)…g(t,19)]
źródło
05AB1E,
119 bytes0-indexed
Try it online or verify all test cases.
Explanation:
źródło
.¥
!R,
5949 bytesTry it online!
Recursively
Reduce
with+
,init=1
andaccumulation=TRUE
to avoid having to subset. Thanks to Criminally Vulgar for suggesting the recursive approach!źródło
outer
thansapply
for 36 bytescumsum
for a while to try and make it work, but thatReduce
is so slick. Nice to be able to drop the index by 1 as well, didn't see that in the comments.JavaScript (ES6),
6867 bytesTry it online!
JavaScript (ES6), 63 bytes
NB: this version works forn≤20 .
Try it online!
źródło
J, 24 bytes
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
źródło
Ruby, 49 bytes
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.źródło
Retina, 59 bytes
Replace the input with 19
1
s (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.
Remove the last element and prefix a
1
.Calculate the cumulative sum.
Convert to decimal.
Try it online!
źródło
C# (Visual C# Interactive Compiler), 120 bytes
Try it online!
Based off of alephalpha's formula.
źródło
Rust, 135 bytes
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
źródło
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)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.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)R (
6059 bytes)Online demo
Straightforward implementation of the observation
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.źródło
K (oK), 17 bytes
-1 byte thanks to ngn (switching from 0-indexed to 1-indexed)
Try it online!
1-indexed
K (oK), 18 bytes
Try it online!
0-indexed
źródło
1+!20
->20#1
Jelly, 10 bytes
Try it online!
0-indexed.
źródło
Perl 5, 48 bytes
TIO
źródło
Japt, 15 bytes
0-indexed; replace
h
withp
for 1-indexed.Try it
źródło
CJam (20 bytes)
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
Dissection
This applies the definition literally:
źródło