15
\$\begingroup\$

Most people are familiar with Pascal's triangle.

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

Pascal's triangle is an automaton where the value of a cell is the sum of the cells to the upper left and upper right. Now we are going to define a similar triangle. Instead of just taking the cells to the upper left and the upper right we are going to take all the cells along two infinite lines extending to the upper left and upper right. Just like Pascal's triangle we start with a single 1 padded infinitely by zeros and build downwards from there.

For example to calculate the cell denoted with an x

   1
  1 1
 2 2 2
4 5 5 4
   x

We would sum the following cells

   .
  . .
 2 . 2
. 5 5 .
   x

Making our new cell 14.

Task

Given a row number (n), and distance from the left (r) calculate and output the rth non-zero entry from the left on the nth row. (the equivalent on Pascal's triangle is nCr). You may assume that r is less than n.

This is , the goal is to minimize the number of bytes in your solution.

Test cases

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

Here's the first couple rows in triangle form:

                  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
\$\endgroup\$
  • 5
    \$\begingroup\$ OEIS A035002 \$\endgroup\$ – Leaky Nun Jul 2 '17 at 15:25
  • \$\begingroup\$ Can our submissions use 1-based indexing instead? \$\endgroup\$ – Cows quack Jul 2 '17 at 15:29
  • 9
    \$\begingroup\$ @KritixiLithos Sure. It will make me sad though. \$\endgroup\$ – Sriotchilism O'Zaic Jul 2 '17 at 15:30
8
\$\begingroup\$

Jelly, 18 17 bytes

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

Uses 0-based indexing.

Try it online!

How it works

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.
\$\endgroup\$
5
\$\begingroup\$

Python 3, 72 bytes

1 byte thanks to 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)))

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can rearrange to get this: n>=r>=0and and save a byte \$\endgroup\$ – Cows quack Jul 2 '17 at 15:36
  • \$\begingroup\$ @EinkornEnchanter if n is 0, then it gives 1; otherwise, it gives 0. It is like n and ... or 1, but shorter. \$\endgroup\$ – Leaky Nun Jul 2 '17 at 15:40
  • \$\begingroup\$ I see, nice abuse of broken behavior then, +1. \$\endgroup\$ – Sriotchilism O'Zaic Jul 2 '17 at 15:41
  • \$\begingroup\$ @EinkornEnchanter 0^0 is 1 in most programming languages. \$\endgroup\$ – Arnauld Jul 2 '17 at 17:06
  • \$\begingroup\$ @Arnauld That doesn't make it true ;) \$\endgroup\$ – Sriotchilism O'Zaic Jul 2 '17 at 17:08
3
\$\begingroup\$

ES6, 80 78 bytes

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

In action!

Two bytes thanks to Arnauld.

\$\endgroup\$
  • \$\begingroup\$ You can save 2 bytes by using while(n&&r<n) and while(o*r). \$\endgroup\$ – Arnauld Jul 2 '17 at 17:25
  • 1
    \$\begingroup\$ This answer is perfectly valid. So, whoever downvoted it should definitely provide an explanation... Or can it be one of these weird automatic downvotes from Community? \$\endgroup\$ – Arnauld Jul 2 '17 at 17:35
2
\$\begingroup\$

PHP, 94 bytes

recursive way 0-indexed

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

Try it online!

PHP, 125 bytes

0-indexed

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

Try it online!

PHP>=7.1, 159 bytes

0-indexed for rows over 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];
\$\endgroup\$
1
\$\begingroup\$

Python 3, 61 bytes

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

This returns True for base case (0, 0), which is allowed by default.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ ~n<-r<1 is quite clever, I spent a good 10 minutes trying to golf n>=r>=0. \$\endgroup\$ – Sriotchilism O'Zaic Jul 2 '17 at 23:18
  • 1
    \$\begingroup\$ Not actually shorter, but it saves the space. :) \$\endgroup\$ – Dennis Jul 2 '17 at 23:42
0
\$\begingroup\$

Pascal, 145 bytes

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;

Try it online!

Uses the T(n, r) = T(n-1, r-1) + T(n-1, r) recursion.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.