编码高尔夫：生成帕斯卡三角形

Question

用尽可能少的代码生成大小为N的 Pascal三角形 的列表（或者打印，我不介意！）

这是我用Python 2.6和一个技巧尝试的结果（只需118个字符）：

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

解释：

• 当长度为0时，列表推导式的第一个元素是[1]
• 下一个元素是通过以下方式获得的：
• 取前一个列表并创建两个新列表，一个在开头填充0，另一个在末尾填充0。
  • 例如，对于第二步，我们取[1]并创建[0,1]和[1,0]
• 逐个元素将两个新列表相加
  • 例如，我们创建一个新列表[(0,1),(1,0)]并使用sum映射。
• 重复n次，完成。

用法（带漂亮打印，实际上是出自Code Golf）：

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

输出：

             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

- fortran

---

如果这个被关闭了，我会投票支持重新开放。我喜欢代码高尔夫，但我不明白为什么有人对它看不惯。请注意，翻译过程中保留原义，使语言更通俗易懂。 - Kenan Banks

也许只是我个人的看法，但是如果你的编程语言无法解析XML文件，我就不会点赞。 - Kenan Banks

@fortran，我对两者都很熟悉。我的意思是，专门用于代码高尔夫的语言，例如K和J，在代码高尔夫问题中获得最多的赞，但你永远不会在其他情况下使用它们。比起20个字符的J解决方案，我更加钦佩一个50个字符的C解决方案。 - Kenan Banks

@Triptych：K和J不是专门用于代码高尔夫的语言。此外，J似乎有用于XML的模块，例如http://www.jsoftware.com/jwiki/Addons/xml/sax。 - Jimmy

@Triptych：那么金融行业一定在进行很多代码高尔夫比赛了：http://kx.com/Customers/end-user-customers.php - earl

Answer 1

K (维基百科)，15个字符：

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

示例输出：

  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)

这也很容易解释：

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

• p是一个接受隐式参数x的函数。

• p将（C）匿名函数（B）展开 x 次（D），起始值为1。

• 这个匿名函数简单地接受一个列表 x，附加0，并通过添加（+）相邻一对的值来返回结果：': '）例如，从(1 2 1) 开始，它将产生（1 2 1 0），然后添加对（1 1+2 2+1 1+0），得到（1 3 3 1）。

---

更新：适用于K4，这可以再减少两个字符。供参考，以下是原始的K3版本：

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

- earl

---

太棒了！我非常怀疑这会有任何比这更短的东西。 - Ionuț G. Stan

Answer 2

J是APL语言家族中的另一种语言，有9个字符：

p=:!/~@i.

这里使用了J语言内置的"combinations"动词。

输出结果：

   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

- earl

---

我想知道消除0所需的工作量。此外，您可能需要转置结果。 - Jimmy

转置很容易，只需在前面加上 |:。在 J 中，大多数情况下你不想摆脱零，但如果你真的想这样做，可以通过以下方式实现：p=:3 :'(1+i.y) ({.])&.> <"1|: !/~i.y'。 - earl

简洁的方法去除前导零并将其漂亮地打印出来：p=:":@(!~i.@>:)"0@i. - ephemient

Answer 3

Haskell，58个字符：

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

输出：

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

更易读：

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

- sth

---

r n=take(n+1)$iterate(\a->zipWith(+)(0:a)$a++[0])[1] 翻译成中文： - ephemient

Answer 4

C语言中的69C：

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

使用方法如下：

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

- caf

---

你在这里作弊！:p 这个函数只计算了一行，你应该包括生成整个三角形的内存（或打印，以任何较短/更容易的方式）的代码在你的字符计数中。 - fortran

嗯？不是这样的，该函数会用整个三角形填充传递给它的数组的左侧。 - caf

Answer 5

F#: 81 chars

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

解释：我懒得像Haskell和K程序员一样聪明，所以我选择了直接的方法：帕斯卡三角形中的每个元素都可以通过行n和列k来唯一标识，其中每个元素的值为n!/(k! (n-k)!)。

- Juliet

Answer 6

Python: 75 characters

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

- Kenan Banks

---

使用单个空格缩进来节省一些字符，很不错。 - Jared Updike

Answer 7

较短的前言版本（112而不是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).

- Jerome

Answer 8

另一个方案（Python）:

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

- Michael Puckett

---

加油，代码高尔夫的目的是使它更加简洁！ 因此，请将函数重命名为类似“p”的内容，并删除额外的缩进（1个空格就足够了），并添加字符计数:p - fortran

Answer 9

PHP 100 characters

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

- user383546

Answer 10

Haskell，164C格式化：

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

没有格式化，52°C：

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

更易读的形式如下：

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

并且，Perl，111C，没有居中：

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

- bdonlan

---

需要 {-# LANGUAGE ParallelListComp #-}，我认为这应该计入你的字符总数...疼。 - ephemient

在命令行上使用“-fglasgow-exts”选项...无论如何，它都可以使用zipWith只需一个额外字符来编写。 - bdonlan

在这种情况下，zipWith(+)(0:l)$l++[0] 可以让您恢复该字符 :) - ephemient