algorithm - pascales - Code-golf: generar el triángulo de pascal

triangulo de pascal historia

Question

Genere una lista de listas (o imprima, no me molesta) un Triángulo de Pascal de tamaño N con la menor cantidad de líneas posibles de código.

Aquí va mi intento (118 caracteres en Python 2.6 usando un truco ):

c,z,k=locals,[0],''_[1]''
p=lambda n:[len(c()[k])and map(sum,zip(z+c()[k][-1],c()[k][-1]+z))or[1]for _ in range(n)]

Explicación:

• El primer elemento de la lista de comprensión (cuando la longitud es 0) es [1]
• los siguientes elementos se obtienen de la siguiente manera:
• toma la lista anterior y crea dos listas, una con un 0 al principio y otra al final.
  • por ejemplo, para el segundo paso, tomamos [1] y hacemos [0,1] y [1,0]
• sumar las dos nuevas listas elemento por elemento
  • por ejemplo, hacemos una nueva lista [(0,1),(1,0)] y mapeamos con suma.
• repite n veces y eso es todo.

uso (con bonita impresión, en realidad fuera del código-golf xD):

result = p(10)
lines = [" ".join(map(str, x)) for x in result]
for i in lines:
    print i.center(max(map(len, lines)))

salida:

             1             
            1 1            
           1 2 1           
          1 3 3 1          
         1 4 6 4 1         
       1 5 10 10 5 1       
      1 6 15 20 15 6 1     
    1 7 21 35 35 21 7 1    
   1 8 28 56 70 56 28 8 1  
1 9 36 84 126 126 84 36 9 1

Answer 1

Python: 75 caracteres

def G(n):R=[[1]];exec"R+=[map(sum,zip(R[-1]+[0],[0]+R[-1]))];"*~-n;return R

Answer 2

69C en C:

f(int*t){int*l=t+*t,*p=t,r=*t,j=0;for(*t=1;l<t+r*r;j=*p++)*l++=j+*p;}

Úselo así:

int main()
{
#define N 10
    int i, j;
    int t[N*N] = {N};

    f(t);

    for (i = 0; i < N; i++)
    {
        for (j = 0; j <= i; j++)
            printf("%d ", t[i*N + j]);
        putchar(''/n'');
    }
    return 0;
}

Answer 3

Escribí esta versión de C ++ hace unos años:

#include <iostream>
int main(int,char**a){for(int b=0,c=0,d=0,e=0,f=0,g=0,h=0,i=0;b<atoi(a[1]);(d|f|h)>1?e*=d>1?--d:1,g*=f>1?--f:1,i*=h>1?--h:1:((std::cout<<(i*g?e/(i*g):1)<<" "?d=b+=c++==b?c=0,std::cout<<std::endl?1:0:0,h=d-(f=c):0),e=d,g=f,i=h));}

Answer 4

Esquema - versión comprimida de 100 caracteres

(define(P h)(define(l i r)(if(> i h)''()(cons r(l(1+ i)(map +(cons 0 r)(append r ''(0))))))(l 1 ''(1)))

Esto es en una forma más legible (269 caracteres):

(define (pascal height) (define (next-row row) (map + (cons 0 row) (append row ''(0)))) (define (iter i row) (if (> i height) ''() (cons row (iter (1+ i) (next-row row))))) (iter 1 ''(1)))

Answer 5

Haskell, 164C con formato:

i l=zipWith(+)(0:l)$l++[0]
fp=map (concatMap$('' '':).show)f$iterate i[1]
c n l=if(length l<n)then c n$'' '':l++" "else l
cl l=map(c(length$last l))l
pt n=cl$take n fp

Sin formato, 52C:

i l=zipWith(+)(0:l)$l++[0]
pt n=take n$iterate i[1]

Una forma más legible de esto:

iterateStep row = zipWith (+) (0:row) (row++[0])
pascalsTriangle n = take n $ iterate iterateStep [1]

-- For the formatted version, we reduce the number of rows at the final step:
formatRow r = concatMap (/l -> '' '':(show l)) r
formattedLines = map formatRow $ iterate iterateStep [1]
centerTo width line =
    if length line < width
        then centerTo width (" " ++ line ++ " ")
        else line
centerLines lines = map (centerTo (length $ last lines)) lines
pascalsTriangle n = centerLines $ take n formattedLines

Y perl, 111C, sin centrar:

$n=<>;$p='' 1 '';for(1..$n){print"$p/n";$x=" ";while($p=~s/^(?= ?/d)(/d* ?)(/d* ?)/$2/){$x.=($1+$2)." ";}$p=$x;}

Answer 6

Lo siguiente es solo una función de Scala que devuelve una List[List[Int]] . No hay impresión bonita ni nada. ¿Alguna mejora sugerida? (Sé que es ineficiente, pero ese no es el principal desafío ahora, ¿verdad?). 145 C.

def p(n: Int)={def h(n:Int):List[Int]=n match{case 1=>1::Nil;case _=>(0::h(n-1) zipAll(h(n-1),0,0)).map{n=>n._1+n._2}};(1 to n).toList.map(h(_))}

O quizás:

def pascal(n: Int) = {
  def helper(n: Int): List[Int] = n match {
    case 1 => 1 :: List()
    case _ => (0 :: helper(n-1) zipAll (helper(n-1),0,0)).map{ n => n._1 + n._2 }
  }
  (1 to n).toList.map(helper(_))
}

(Soy un novato de Scala, así que por favor sé amable conmigo: D)

Answer 7

Mi intento en C ++ (378c). No es tan bueno como el resto de las publicaciones ... pero estoy orgulloso de haber encontrado una solución por mi cuenta =)

int* pt(int n)
{
  int s=n*(n+1)/2;
  int* t=new int[s];

  for(int i=0;i<n;++i)
    for(int j=0;j<=i;++j)
      t[i*n+j] = (!j || j==i) ? 1 : t[(i-1)*n+(j-1)] + t[(i-1)*n+j];
  return t;
}

int main()
{
  int n,*t;
  std::cin>>n;
  t=pt(n);

  for(int i=0;i<n;++i)
  {
    for(int j=0;j<=i;j++)
      std::cout<<t[i*n+j]<<'' '';
    std::cout<<"/n";
  }
}

Answer 8

Otra solución de Python , que podría ser mucho más corta si las funciones incorporadas tuvieran nombres más cortos ... 106 caracteres.

from itertools import*
r=range
p=lambda n:[[len(list(combinations(r(i),j)))for j in r(i+1)]for i in r(n)]

Answer 9

Otro intento, en prolog (estoy practicando xD), no demasiado corto, solo 164c:

s([],[],[]).
s([H|T],[J|U],[K|V]):-s(T,U,V),K is H+J.
l([1],0).
l(P,N):-M is N-1,l(A,M),append(A,[0],B),s(B,[0|A],P).
p([],-1).
p([H|T],N):-M is N-1,l(H,N),p(T,M).

explicación:

• s = suma el elemento de lista por elemento
• l = la enésima fila del triángulo
• p = todo el triángulo de tamaño N

Answer 10

PHP, 115 caracteres

$t[][]=1;
for($i=1;$i<$n;++$i){
$t[$i][0]=1;
for($j=1;$j<$i;++$j)$t[$i][$j]=$t[$i-1][$j-1]+$t[$i-1][$j];
$t[$i][$i]=1;}

Si no le importa si print_r () muestra la matriz de salida en el orden correcto, puede afeitarla a 113 caracteres como

$t[][]=1;
for($i=1;$i<$n;++$i){
$t[$i][0]=$t[$i][$i]=1;
for($j=1;$j<$i;++$j)$t[$i][$j]=$t[$i-1][$j-1]+$t[$i-1][$j];}

Answer 11

Perl, 63 caracteres:

for(0..9){push@z,1;say"@z";@z=(1,map{$z[$_-1]+$z[$_]}(1..$#z))}

Answer 12

Ruby, 83c:

def p(n);n>0?(m=p(n-1);k=m.last;m+[([0]+k).zip(k+[0]).map{|x|x[0]+x[1]}]):[[1]];end

prueba:

irb(main):001:0> def p(n);n>0?(m=p(n-1);k=m.last;m+[([0]+k).zip(k+[0]).map{|x|x[0]+x[1]}]):[[1]];end
=> nil
irb(main):002:0> p(5)
=> [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]
irb(main):003:0> 

Answer 13

VBA, 122 caracteres:

Sub p(n)
For r = 1 To n
l = "1"
v = 1
For c = 1 To r - 1
v = v / c * (r - c)
l = l & " " & v
Next
Debug.Print l
Next
End Sub

Answer 14

Versión de prólogo más corta (112 en lugar de 164):

n([X],[X]).
n([H,I|T],[A|B]):-n([I|T],B),A is H+I.
p(0,[[1]]):-!.
p(N,[R,S|T]):-O is N-1,p(O,[S|T]),n([0|S],R).

Answer 15

Viejo hilo, pero escribí esto en respuesta a un desafío en otro foro de hoy:

def pascals_triangle(n):
    x=[[1]]
    for i in range(n-1):
        x.append([sum(i) for i in zip([0]+x[-1],x[-1]+[0])])
    return x

for x in pascals_triangle(5):
    print(''{0:^16}''.format(x))

      [1]       
     [1, 1]     
   [1, 2, 1]    
  [1, 3, 3, 1]  
[1, 4, 6, 4, 1]

Answer 16

otra puñalada (pitón):

def pascals_triangle(n):
    x=[[1]]
    for i in range(n-1):
        x.append(list(map(sum,zip([0]+x[-1],x[-1]+[0]))))
    return x

Answer 17

una versión de Perl (139 caracteres sin shebang)

@p = (1,1);
while ($#p < 20) {
    @q =();
    $z = 0;
    push @p, 0;
    foreach (@p) {
        push @q, $_+$z;
        $z = $_
    }
    @p = @q;
    print "@p/n";
}

la salida comienza desde 1 2 1

Answer 18

F# : 81 caracteres

let f=bigint.Factorial
let p x=[for n in 0I..x->[for k in 0I..n->f n/f k/f(n-k)]]

Explicación: Soy demasiado perezoso para ser tan listo como los programadores Haskell y K, así que tomé la ruta directa: cada elemento en el triángulo de Pascal se puede identificar de manera única usando una fila ny col k, donde el valor de cada elemento es n!/(k! (nk)!

Answer 19

K ( Wikipedia ), 15 caracteres:

p:{x{+'':x,0}/1}

Ejemplo de salida:

  p 10
(1
 1 1
 1 2 1
 1 3 3 1
 1 4 6 4 1
 1 5 10 10 5 1
 1 6 15 20 15 6 1
 1 7 21 35 35 21 7 1
 1 8 28 56 70 56 28 8 1
 1 9 36 84 126 126 84 36 9 1
 1 10 45 120 210 252 210 120 45 10 1)

También se explica fácilmente:

p:{x {+'':x,0} / 1}
   ^ ^------^ ^ ^
   A    B     C D

• p es una función que toma un parámetro implícito x .

• p despliega (C) una función anónima (B) x veces (A) comenzando en 1 (D).

• La función anónima simplemente toma una lista x , agrega 0 y devuelve un resultado agregando ( + ) cada par adyacente ( '': de valores: por ejemplo, comenzando con (1 2 1) , producirá (1 2 1 0) , agregue pares (1 1+2 2+1 1+0) , dando (1 3 3 1) .

Actualización: Adaptado a K4, que reduce otros dos caracteres. Como referencia, aquí está la versión original de K3:

p:{x{+'':0,x,0}/1}

Answer 20

J , otro idioma en la familia APL, 9 caracteres:

p=:!/~@i.

Esto usa el verbo "combinaciones" incorporado de J.

Salida:

   p 10
1 1 1 1 1  1  1  1  1   1
0 1 2 3 4  5  6  7  8   9
0 0 1 3 6 10 15 21 28  36
0 0 0 1 4 10 20 35 56  84
0 0 0 0 1  5 15 35 70 126
0 0 0 0 0  1  6 21 56 126
0 0 0 0 0  0  1  7 28  84
0 0 0 0 0  0  0  1  8  36
0 0 0 0 0  0  0  0  1   9
0 0 0 0 0  0  0  0  0   1

Answer 21

Haskell , 58 caracteres:

r 0=[1]
r(n+1)=zipWith(+)(0:r n)$r n++[0]
p n=map r[0..n]

Salida:

*Main> p 5
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]

Más legible

-- # row 0 is just [1]
row 0     = [1]
-- # row (n+1) is calculated from the previous row
row (n+1) = zipWith (+) ([0] ++ row n) (row n ++ [0])
-- # use that for a list of the first n+1 rows
pascal n  = map row [0..n]

Answer 22

PHP 100 caracteres

$v[]=1;while($a<34){echo join(" ",$v)."/n";$a++;for($k=0;$k<=$a;$k++)$t[$k]=$v[$k-1]+$v[$k];$v=$t;}

Answer 23

VBA / VB6 (392 caracteres con formato)

Public Function PascalsTriangle(ByVal pRows As Integer)

Dim iRow As Integer
Dim iCol As Integer
Dim lValue As Long
Dim sLine As String

  For iRow = 1 To pRows
    sLine = ""
    For iCol = 1 To iRow
      If iCol = 1 Then
        lValue = 1
      Else
        lValue = lValue * (iRow - iCol + 1) / (iCol - 1)
      End If
      sLine = sLine & " " & lValue
    Next
    Debug.Print sLine
  Next

End Function