Zróbmy trójkąt

15

Większość ludzi zna trójkąt Pascala.

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

Trójkąt Pascala to automat, w którym wartość komórki jest sumą komórek w lewym górnym i prawym górnym rogu. Teraz zdefiniujemy podobny trójkąt. Zamiast po prostu przenieść komórki w lewy górny róg i prawy górny róg, bierzemy wszystkie komórki wzdłuż dwóch nieskończonych linii rozciągających się w lewy górny i prawy górny róg. Podobnie jak trójkąt Pascala zaczynamy od pojedynczego 1wypełnionego nieskończenie zerami i stamtąd budujemy w dół.

Na przykład, aby obliczyć komórkę oznaczoną za pomocą x

   1
  1 1
 2 2 2
4 5 5 4
   x

Zsumowalibyśmy następujące komórki

   .
  . .
 2 . 2
. 5 5 .
   x

Tworzenie naszej nowej komórki 14 .

Zadanie

Biorąc pod uwagę numer wiersza ( n ) i odległość od lewej ( r ) oblicz i wyślij r -ty niezerowy wpis z lewej strony w n- tym rzędzie. (odpowiednikiem trójkąta Pascala jest nCr ). Możesz założyć, że r jest mniejsze niż n .

To jest , celem jest zminimalizowanie liczby bajtów w twoim rozwiązaniu.

Przypadki testowe

0,0 -> 1
1,0 -> 1
2,0 -> 2
4,2 -> 14
6,3 -> 106

Oto kilka pierwszych rzędów w kształcie trójkąta:

                  1
                1   1
              2   2   2
            4   5   5   4
          8  12  14  12   8
       16  28  37  37  28  16
     32  64  94  106 94  64  32
   64  144 232 289 289 232 144 64
 128 320 560 760 838 760 560 320 128
Post Rock Garf Hunter
źródło
5
OEIS A035002
Leaky Nun
Czy zamiast tego nasze zgłoszenia mogą korzystać z indeksowania 1?
Kritixi Lithos
9
@KritixiLithos Sure. To mnie zasmuci.
Post Rock Garf Hunter

Odpowiedzi:

8

Galaretka , 18 17 bajtów

SṚ0;+Sṭ
1WWÇ⁸¡ṪṙḢ

Wykorzystuje indeksowanie 0.

Wypróbuj online!

Jak to działa

1WWÇ⁸¡ṪṙḢ  Main link. Arguments: n, r

1          Set the return value to 1.
 W         Wrap; yield [1].
  W        Wrap; yield [[1]].
           This is the triangle with one row.
   Ç⁸¡     Call the helper link n times.
           Each iteration adds one row to the triangle.
      Ṫ    Tail; take the last array, i.e., the row n of the triangle.
       ṙ   Rotate row n r units to the left.
        Ḣ  Head; take the first element, i.e., entry r of row n.


SṚ0;+Sṭ    Helper link. Argument: T (triangle)

S          Take the column-wise sums, i.e., sum the ascending diagonals of the 
           centered triangle, left to right.
 Ṛ         Reverse the array of sums. The result is equal to the sums of the 
           descending diagonals of the centered triangle, also left to right.
  0;       Prepend a 0. This is required because the first element of the next row 
           doesn't have a descending diagonal.
     S     Take the column-wise sum of T.
    +      Add the ascending to the descending diagonals.
Dennis
źródło
5

Python 3 , 72 bajty

1 bajt dzięki Kritixi Lithos.

f=lambda n,r:n>=r>=0and(0**n or sum(f(i,r)+f(i,r+i-n)for i in range(n)))

Wypróbuj online!

Leaky Nun
źródło
1
Możesz zmienić to ustawienie: n>=r>=0andi zapisać bajt
Kritixi Lithos
@EinkornEnchanter jeśli nwynosi 0, to daje 1; w przeciwnym razie daje 0. Jest jak n and ... or 1, ale krótszy.
Leaky Nun
Rozumiem, to miłe nadużycie złamanego zachowania, +1.
Post Rock Garf Hunter
@EinkornEnchanter 0^0jest 1 w większości języków programowania .
Arnauld
@Arnauld To nie oznacza, że ​​to prawda;)
Post Rock Garf Hunter,
3

ES6, 80 78 bajtów

p=(n,r,c=0)=>n?(o=>{while(n&&r<n)c+=p(--n,r);while(o*r)c+=p(--o,--r)})(n)||c:1

W akcji!

Dwa bajty dzięki Arnauldowi.

2ndAttmt
źródło
Możesz zapisać 2 bajty za pomocą while(n&&r<n)i while(o*r).
Arnauld
1
Ta odpowiedź jest całkowicie poprawna. Ktokolwiek więc to ocenił, zdecydowanie powinien wyjaśnić ... Czy może to być jeden z tych dziwnych automatycznych głosów od społeczności?
Arnauld
2

PHP , 94 bajty

sposób rekurencyjny indeksowany 0

function f($r,$c){for($s=$r|$c?$r<0?0:!$t=1:1;$t&&$r;)$s+=f($r-=1,$c)+f($r,$c-++$i);return$s;}

Wypróbuj online!

PHP , 125 bajtów

0-indeksowane

for(;$r<=$argv[1];$r++)for($z++,$c=~0;++$c<$z;$v+=$l)$x[$c]+=$t[+$r][$c]=$l=($v=&$y[$r-$c])+$x[$c]?:1;echo$t[$r-1][$argv[2]];

Wypróbuj online!

PHP> = 7.1, 159 bajtów

Indeksowane 0 dla wierszy powyżej 50

for([,$m,$n]=$argv;$r<=$m;$r++)for($z++,$c=0;$c<$z;$v=bcadd($v,$l),$x[$c]=bcadd($x[$c],$l),$c++)$t[+$r][$c]=$l=bcadd(($v=&$y[$r-$c]),$x[$c])?:1;echo$t[$m][$n];
Jörg Hülsermann
źródło
1

Python 3 , 61 bajtów

f=lambda n,r:sum(f(k,r)+f(k,r+k-n)for k in range(n))or~n<-r<1

Zwraca wartość True dla przypadku podstawowego (0, 0) , co jest domyślnie dozwolone .

Wypróbuj online!

Dennis
źródło
~n<-r<1jest całkiem sprytny, spędziłem dobre 10 minut próbując grać w golfa n>=r>=0.
Post Rock Garf Hunter
1
Właściwie nie krótszy, ale oszczędza miejsce. :)
Dennis
0

Pascal , 145 bajtów

function f(n,k:integer):integer;var i,r:integer;begin r:=1-Ord((k<0)or(k>n));if n>0 then r:=0;for i:=1 to n do r:=r+f(n-i,k-i)+f(n-i,k);f:=r;end;

Wypróbuj online!

Wykorzystuje T(n, r) = T(n-1, r-1) + T(n-1, r)rekurencję.

Uriel
źródło