Hagamos un triangulo

15

La mayoría de las personas están familiarizadas con el triángulo de Pascal.

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

El triángulo de Pascal es un autómata donde el valor de una celda es la suma de las celdas en la esquina superior izquierda y superior derecha. Ahora vamos a definir un triángulo similar. En lugar de simplemente llevar las celdas a la esquina superior izquierda y a la derecha superior, vamos a tomar todas las celdas a lo largo de dos líneas infinitas que se extienden a la esquina superior izquierda y superior derecha. Al igual que el triángulo de Pascal, comenzamos con un solo 1relleno infinito de ceros y desde allí construimos hacia abajo.

Por ejemplo, para calcular la celda indicada con un x

   1
  1 1
 2 2 2
4 5 5 4
   x

Sumaríamos las siguientes celdas

   .
  . .
 2 . 2
. 5 5 .
   x

Haciendo nuestra nueva celda 14.

Tarea

Dado un número de fila ( n ), y la distancia desde la izquierda ( r Calcular) y la salida de la r º no cero de entrada de la izquierda en el n º fila. (el equivalente en el triángulo de Pascal es nCr ). Puede suponer que r es menor que n .

Este es el , el objetivo es minimizar el número de bytes en su solución.

Casos de prueba

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

Aquí están las primeras dos filas en forma de triángulo:

                  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
fuente
55
OEIS A035002
Leaky Nun
¿Pueden nuestras presentaciones usar indexación basada en 1?
Kritixi Lithos
99
@KritixiLithos Claro. Sin embargo, me pondrá triste.
Post Rock Garf Hunter

Respuestas:

8

Jalea , 18 17 bytes

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

Utiliza indexación basada en 0.

Pruébalo en línea!

Cómo funciona

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

Python 3 , 72 bytes

1 byte gracias a 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)))

Pruébalo en línea!

Monja permeable
fuente
1
Puede reorganizar para obtener esto: n>=r>=0andy guardar un byte
Kritixi Lithos
@EinkornEnchanter si nes 0, entonces da 1; de lo contrario, da 0. Es como n and ... or 1, pero más corto.
Leaky Nun
Ya veo, buen abuso de comportamiento roto, +1.
Post Rock Garf Hunter
@EinkornEnchanter 0^0está 1 en la mayoría de los lenguajes de programación .
Arnauld
@Arnauld Eso no lo hace realidad;)
Post Rock Garf Hunter
3

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

¡En acción!

Dos bytes gracias a Arnauld.

2ndAttmt
fuente
Puede guardar 2 bytes usando while(n&&r<n)y while(o*r).
Arnauld
1
Esta respuesta es perfectamente válida. Entonces, quien lo rechazó definitivamente debería proporcionar una explicación ... ¿O puede ser uno de estos extraños votos negativos automáticos de la Comunidad?
Arnauld
2

PHP , 94 bytes

manera recursiva indexada 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;}

Pruébalo en línea!

PHP , 125 bytes

0 indexado

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

Pruébalo en línea!

PHP> = 7.1, 159 bytes

0 indexado para filas de más de 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
fuente
1

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

Esto devuelve True para el caso base (0, 0) , que está permitido por defecto .

Pruébalo en línea!

Dennis
fuente
~n<-r<1es bastante inteligente, pasé unos buenos 10 minutos intentando jugar al golf n>=r>=0.
Post Rock Garf Hunter
1
En realidad no es más corto, pero ahorra espacio. :)
Dennis
0

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;

Pruébalo en línea!

Utiliza la T(n, r) = T(n-1, r-1) + T(n-1, r)recursividad.

Uriel
fuente