代码高尔夫：康威生命游戏

Question

代码高尔夫：康威生命游戏

language-agnosticcode-golfrosetta-stoneconways-game-of-life

76

挑战：编写最短的程序实现 John H. Conway 的生命游戏细胞自动机。[链接] 编辑：经过大约一周的比赛，我选择了一个获胜者：pdehaan，他成功用 Perl 击败了 Matlab 解决方案，仅用一个字符就能实现。

对于那些没有听说过生命游戏的人，你需要拿一个（理想上是无限大的）正方形格子的网格。单元可以是活着的（填充）或死亡的（空的）。我们通过应用以下规则来确定哪些单元在下一个时间步骤中是活着的：

1. 任何只有不到两个活邻居的活细胞都会死亡，就像人口不足一样。 2. 任何有超过三个活邻居的活细胞都会死亡，就像因过度拥挤而死亡一样。 3. 任何有两个或三个活邻居的活细胞将继续生存到下一代。 4. 正好有三个活邻居的死亡细胞成为活细胞，就像通过繁殖一样。

你的程序将读取一个40 x 80字符的ASCII文本文件，该文件指定为命令行参数，并读取要执行的迭代次数（N）。最后，它将输出一个名为out.txt的ASCII文件，其中包含N次迭代后系统的状态。

以下是一个使用相关文件的示例运行： in.txt：

................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
..................................XX............................................
..................................X.............................................
.......................................X........................................
................................XXXXXX.X........................................
................................X...............................................
.................................XX.XX...XX.....................................
..................................X.X....X.X....................................
..................................X.X......X....................................
...................................X.......XX...................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................

迭代100次：

Q:\>life in.txt 100

输出结果 (out.txt)

................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
..................................XX............................................
..................................X.X...........................................
....................................X...........................................
................................XXXXX.XX........................................
................................X.....X.........................................
.................................XX.XX...XX.....................................
..................................X.X....X.X....................................
..................................X.X......X....................................
...................................X.......XX...................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................

规则：

您需要使用文件I/O来读写文件。
您需要接受输入文件和迭代次数作为参数。
您需要按指定格式生成out.txt（如果存在，则覆盖）。
不需要处理棋盘的边缘（环绕、无限网格等）。
编辑：您的输出文件中需要有换行符。

获胜者将由字符计数决定。

祝你好运！

- hb2pencil

22

这是一个非常棒的"代码高尔夫"！我完全相信它应该属于SO。几天前我在APL中发现了一个很棒的实现：http://www.youtube.com/watch?v=a9xAKttWgP4。 - Victor Hurdugaci

这是一个可以接受的想法，但你需要进一步完善它。http://meta.stackexchange.com/questions/24242/acceptable-level-of-code-golf-questions - zaf

4

相对流行度不是评估高尔夫比赛好坏的良好指标。即使perl代码不是最短的，甚至不符合规范，它也经常获得很多投票。你应该依靠字符数进行评估。使用更冗长语言的人仍然可以在他们之间竞争。 - John La Rooy

2

输入文件中有换行符吗？ - Gabe

需要在两个地方加入换行符。我之前应该澄清这一点。 - hb2pencil

显示剩余6条评论

24个回答

33

MATLAB 7.8.0 (R2009a) - 174 171 161 150 138 131 128 124个字符

函数语法：（124个字符）

这是更易读的版本（为了更好的格式化添加了不必要的换行和空格）：

function l(f,N),
  b=char(importdata(f))>46;
  for c=1:N,
    b=~fix(filter2(ones(3),b)-b/2-3);
  end;
  dlmwrite('out.txt',char(b*42+46),'')

以下是如何从MATLAB命令窗口运行程序的方法：

l('in.txt',100)

命令语法：（130个字符）

在谈到使用命令语法调用函数的评论之后，我深入挖掘并发现MATLAB函数实际上可以使用命令行格式被调用（有一些限制）。每天都会学到新东西！

function l(f,N),
  b=char(importdata(f))>46;
  for c=1:eval(N),
    b=~fix(filter2(ones(3),b)-b/2-3);
  end;
  dlmwrite('out.txt',char(b*42+46),'')

以下是如何从MATLAB命令窗口运行程序的方法：

l in.txt 100

额外挑战：可推特GIF制作器 - 136个字符

为了好玩，我想看看能否将输出转储到GIF文件而不是文本文件中，同时仍保持字符计数低于140（即“可推特”）。以下是漂亮格式化的代码：

function l(f,N),
  b=char(importdata(f))>46;
  k=ones(3);
  for c=1:N+1,
    a(:,:,:,c)=kron(b,k);
    b=~fix(filter2(k,b)-b/2-3);
  end;
  imwrite(~a,'out.gif')

尽管IMWRITE默认情况下应该创建一个无限循环的GIF，但我的GIF只循环一次。也许这是MATLAB新版本中修复的一个错误。因此，为了使动画持续时间更长并且演化步骤更容易观察，我将帧延迟保留在默认值（大约半秒左右）。以下是使用Gosper Glider Gun模式的GIF输出：

alt text

改进

更新1： 将矩阵b从逻辑（即"布尔"）类型更改为数字类型以消除一些转换。
更新2： 缩短了加载文件的代码，并使用函数MAGIC作为技巧来减少字符数来创建卷积核。
更新3： 简化索引逻辑，用b/42替换~~b+0，并将'same'替换为's'作为CONV2的参数（令人惊讶的是它仍然有效！）。
更新4： 我想我应该先在网上搜索，因为今年早些时候Loren从The MathWorks博客中谈到了高尔夫和生命游戏。我结合了那里讨论的一些技术，这要求我将b重新更改为逻辑矩阵。
更新5： Aslak Grinsted在上述博客文章中的评论中提出了一种更短的算法，既可以处理逻辑，也可以执行卷积（使用函数FILTER2），因此我“合并”（读作“复制”）了他的建议。;)
更新6： 从初始化b中削减了两个字符，并重组了循环中的逻辑，以节省1个额外的字符。
更新7： Eric Sampson在一封电子邮件中指出，我可以用char替换cell2mat，节省4个字符。谢谢Eric！

- gnovice

30

Ruby 1.9 - 189 178 159 155 153 chars

f,n=$*
c=IO.read f
n.to_i.times{i=0;c=c.chars.map{|v|i+=1
v<?.?v:('...X'+v)[[83,2,-79].map{|j|c[i-j,3]}.to_s.count ?X]||?.}*''}
File.new('out.txt',?w)<<c

编辑： 使用4个字符更少的方式处理换行符。
如果允许在生命细胞到达边缘时覆盖换行符，则可以删除7个字符(v<?.?v:)。

- Mladen Jablanović

我认为你可以通过将第三行替换为v<13?v:l==3||v-l==?T?X:?.}}来减少12个字符。但是我没有安装1.9来测试它。 - AShelly

我认为你不能将一个字符串 v 与一个整数进行比较。 - Mladen Jablanović

尝试使用“v<?.?v:l==3||v.ord-l==84??X:?.}}”来节省7个。 - AShelly

不错，但是当活细胞靠近边缘时，这会覆盖换行符吗？ - AShelly

没错，我不确定这是否符合规则：“这意味着你可以在边缘情况下做任何想做的事情。事物可能会消失、损坏等。”如果@hb2pencil说不行，我将回滚。 - Mladen Jablanović

对我来说听起来不错。最好假设边缘情况会破坏条目，因为每个人在需要时都会处理边缘情况。 - hb2pencil

24

Perl，127 129 135字符

成功去掉了几个字符...

$/=pop;@b=split'',<>;map{$n=-1;@b=map{++$n;/
/?$_:($t=grep/X/,@b[map{$n+$_,$n-$_}1,80..82])==3|$t+/X/==3?X:'.'}@b}1..$/;print@b

- pdehaan

4

这会将内容写入到"out.txt"文件中吗？ - AShelly

2

@b=<>=~/./g 可以节省 3 个字符。 - mob

20

Python - 282个字符

不妨开始行动吧...

import sys
_,I,N=sys.argv;R=range(3e3);B=open(I).read();B=set(k for k in R if'A'<B[k])
for k in R*int(N):
 if k<1:b,B=B,set()
 c=sum(len(set((k+o,k-o))&b)for o in(1,80,81,82))
 if(c==3)+(c==2)*(k in b):B.add(k)
open('out.txt','w').write(''.join('.X\n'[(k in B)-(k%81<1)]for k in R))

- John La Rooy

1

但是2.7（和3.x）接受用于集合推导的括号，因此set（...）可以替换为{...}，将range（3e3）替换为range（3000）可以减少2个字符。 - Don O'Donnell

20

Python 2.x - 210/234个字符

好吧，210个字符的代码有点作弊。

#coding:l1
exec'xÚ=ŽA\nÂ@E÷sŠº1ƒÆscS‰ØL™Æª··âî¿GÈÿÜ´1iÖ½;Sçu.~H®J×Þ-‰Ñ%ª.wê,šÖ§J®dê˜²>cÉZË¢Vä€»Eîa¿,vKAËÀåÌƒ<»Gce‚ÿ‡ábUt¹)G%£êŠ…óbÒüíÚ¯GÔ/n×Xši&Ä‡:})äðtÏÄJÎòDˆÐÿG¶'.decode('zip')

你可能无法复制并粘贴此代码并使其正常运行。它应该是Latin-1（ISO-8859-1）格式，但我认为在某个地方被扭曲成了Windows-1252格式。另外，你的浏览器可能吞噬了一些非ASCII字符。

因此，如果它不能正常工作，你可以使用普通的7位字符生成文件。

s = """
23 63 6F 64 69 6E 67 3A 6C 31 0A 65 78 65 63 27 78 DA 3D 8E 41 5C 6E C2
40 0C 45 F7 73 8A BA 31 13 AD 83 15 11 11 C6 73 08 63 17 05 53 89 D8 4C
99 C6 AA B7 B7 AD E2 EE BF 47 C8 FF DC B4 31 69 D6 BD 3B 53 E7 75 2E 7E
48 AE 4A D7 DE 90 8F 2D 89 AD D1 25 AA 2E 77 16 EA 2C 9A D6 A7 4A AE 64
EA 98 B2 3E 63 C9 5A CB A2 56 10 0F E4 03 80 BB 45 16 0B EE 04 61 BF 2C
76 0B 4B 41 CB C0 E5 CC 83 03 3C 1E BB 47 63 65 82 FF 87 E1 62 55 1C 74
B9 29 47 25 A3 EA 03 0F 8A 07 85 F3 62 D2 FC ED DA AF 11 47 D4 2F 6E D7
58 9A 69 26 C4 87 3A 7D 29 E4 F0 04 74 CF C4 4A 16 CE F2 1B 44 88 1F D0
FF 47 B6 27 2E 64 65 63 6F 64 65 28 27 7A 69 70 27 29
"""

with open('life.py', 'wb') as f:
    f.write(''.join(chr(int(i, 16)) for i in s.split()))

这将得到一个有效的210字符Python源文件。我所做的只是在原始Python源代码上使用了Zip压缩。真正的技巧是在结果字符串中使用了非ASCII字符。它仍然是有效的代码，只是有点麻烦。

未压缩版本包括234个字符，我认为这还是很可观的。

import sys
f,f,n=sys.argv
e=open(f).readlines()
p=range
for v in p(int(n)):e=[''.join('.X'[8+16*(e[t][i]!='.')>>sum(n!='.'for v in e[t-1:t+2]for n in v[i-1:i+2])&1]for i in p(80))for t in p(40)]
open('out.txt','w').write('\n'.join(e))

非常抱歉需要横向滚动条才能查看，但是上面的所有换行都是必需的，我已将它们计算为一个字符。

我不建议阅读代码压缩后的版本。变量名是随机选择的，以实现最佳压缩效果。是的，我很认真。下面是更好格式化和注释的版本:

# get command-line arguments: infile and count
import sys
ignored, infile, count = sys.argv

# read the input into a list (each input line is a string in the list)
data = open(infile).readlines()

# loop the number of times requested on the command line
for loop in range(int(count)):
    # this monstrosity applies the rules for each iteration, replacing
    # the cell data with the next generation
    data = [''.join(

                # choose the next generation's cell from '.' for
                # dead, or 'X' for alive
                '.X'[

                    # here, we build a simple bitmask that implements
                    # the generational rules.  A bit from this integer
                    # will be chosen by the count of live cells in
                    # the 3x3 grid surrounding the current cell.
                    #
                    # if the current cell is dead, this bitmask will
                    # be 8 (0b0000001000).  Since only bit 3 is set,
                    # the next-generation cell will only be alive if
                    # there are exactly 3 living neighbors in this
                    # generation.
                    #
                    # if the current cell is alive, the bitmask will
                    # be 24 (8 + 16, 0b0000011000).  Since both bits
                    # 3 and 4 are set, this cell will survive if there
                    # are either 3 or 4 living cells in its neighborhood,
                    # including itself
                    8 + 16 * (data[y][x] != '.')

                    # shift the relevant bit into position
                    >>

                    # by the count of living cells in the 3x3 grid
                    sum(character != '.' # booleans will convert to 0 or 1
                        for row in data[y - 1 : y + 2]
                        for character in row[x - 1 : x + 2]
                    )

                    # select the relevant bit
                    & 1
                ]

               # for each column and row
                for x in range(80)
            )
            for y in range(40)
    ]

# write the results out
open('out.txt','w').write('\n'.join(data))

对于Python爱好者，抱歉使用了类C语言的括号格式，但我想让每个括号的结尾更清晰明了。

- P Daddy

将open(f).readlines()替换为list(open(f))。这样做等效且比原来短6个字符，可以通过缩小和压缩来实现，压缩后长度减少3个字节，如果在EOF处加上EOL，则长度会奇妙地减少4个字符，压缩后长度为206（带有EOL）和228（不带EOL）。 - Chris Morgan

14

Haskell - 284 272 232字符

import System
main=do f:n:_<-getArgs;s<-readFile f;writeFile"out.txt"$t s$read n
p '\n'_='\n'
p 'X'2='X'
p _ 3='X'
p _ _='.'
t r 0=r
t r n=t[p(r!!m)$sum[1|d<-1:[80..82],s<-[1,-1],-m<=d*s,m+d*s<3240,'X'==r!!(m+d*s)]|m<-[0..3239]]$n-1

- Alexander Konstantinov

10

F#, 496

我可以把这个代码压缩得更小，但我喜欢它现在的样子，因为它依然大致相符并且易读。

open System.IO
let mutable a:_[,]=null
let N y x=
 [-1,-1;-1,0;-1,1;0,-1;0,1;1,-1;1,0;1,1]
 |>Seq.sumBy(fun(i,j)->try if a.[y+i,x+j]='X' then 1 else 0 with _->0)
[<EntryPoint>]
let M(r)=
 let b=File.ReadAllLines(r.[0])
 a<-Array2D.init 40 80(fun y x->b.[y].[x])
 for i=1 to int r.[1] do 
  a<-Array2D.init 40 80(fun y x->
   match N y x with|3->'X'|2 when a.[y,x]='X'->'X'|_->'.')
 File.WriteAllLines("out.txt",Array.init 40(fun y->
  System.String(Array.init 80(fun x->a.[y,x]))))
 0

编辑

428

根据请求，这是我的下一次尝试：

open System
let mutable a,k=null,Array2D.init 40 80
[<EntryPoint>]
let M r=
 a<-k(fun y x->IO.File.ReadAllLines(r.[0]).[y].[x])
 for i=1 to int r.[1] do a<-k(fun y x->match Seq.sumBy(fun(i,j)->try if a.[y+i,x+j]='X'then 1 else 0 with _->0)[-1,-1;-1,0;-1,1;0,-1;0,1;1,-1;1,0;1,1]with|3->'X'|2 when a.[y,x]='X'->'X'|_->'.')
 IO.File.WriteAllLines("out.txt",Array.init 40(fun y->String(Array.init 80(fun x->a.[y,x]))))
 0

通过一些基本的高尔夫技巧，我成功地减少了14%。但是我感觉使用二维数组/字符串数组比使用一维数组要慢，不过我现在不想转换。注意我优雅地读取文件3200次以初始化我的数组 :)

- Brian

请大幅缩减它，我很好奇！ - Landei

10

Ruby 1.8: ~~178~~ 175个字符

f,n=$*;b=IO.read f
n.to_i.times{s=b.dup
s.size.times{|i|t=([82,1,-80].map{|o|b[i-o,3]||''}*'').count 'X'
s[i]=t==3||b[i]-t==?T??X:?.if s[i]>13};b=s}
File.new('out.txt','w')<<b

换行符很重要（尽管所有的都可以被分号替代。）

编辑：已解决换行问题，并删除了3个字符。

- AShelly

输出文件中的行似乎没有被分隔开。 - Mladen Jablanović

它们不是 - 但它们在我的80个字符控制台上显示得很完美。 - AShelly

你需要有换行符；很抱歉没有明确指出。 - hb2pencil

10

Java, 346

更新1：删除了内部if语句和更多的丑陋代码。
更新2：修复了一个漏洞并增加了一个字符。
更新3：使用更多的内存和数组，同时忽略一些边界问题。可能可以节省一些字符。
更新4：节省了几个字符。感谢BalusC。
更新5：进行了一些小改动，使其低于400，并让它变得更加丑陋。
更新6：现在代码被硬编码了，可以一次性读取确切的数量。再加上一些节省。
更新7：将写入文件的操作连接起来以节省一个字符。还有一些奇怪的细节。

只是玩弄BalusC的解决方案。由于声望有限，因此我无法将任何东西添加为评论。

class M{public static void main(String[]a)throws Exception{int t=3240,j=t,i=new Integer(a[1])*t+t;char[]b=new char[i+t],p={1,80,81,82};for(new java.io.FileReader(a[0]).read(b,t,t);j<i;){char c=b[j],l=0;for(int n:p)l+=b[j+n]/88+b[j-n]/88;b[j+++t]=c>10?(l==3|l+c==90?88:'.'):c;}new java.io.FileWriter("out.txt").append(new String(b,j,t)).close();}}

更易读的版本：

class M{
 public static void main(String[]a)throws Exception{
  int t=3240,j=t,i=new Integer(a[1])*t+t;
  char[]b=new char[i+t],p={1,80,81,82};
  for(new java.io.FileReader(a[0]).read(b,t,t);j<i;){
    char c=b[j],l=0;
    for(int n:p)l+=b[j+n]/88+b[j-n]/88;
    b[j+++t]=c>10?(l==3|l+c==90?88:'.'):c;
  }
  new java.io.FileWriter("out.txt").append(new String(b,j,t)).close();
 }
}

- Molehill

使用字符串（String）而不是字符数组（char[]）会更加耗费资源，但在代码高尔夫中这并不重要！干得好 :) - BalusC

请注意，总文件/字符长度不是2754个字符。 - BalusC

@BallusC 谢谢，我成功地只复制了34行而不是全部40行！ - Molehill

这确实是一个真正的内存占用巨兽！顺便说一句，在 new char[i--*t] 里面可以使用 --i，而 b[l++]+=(char)j 可以简化为 b[l++]=(char)j。这样能再节省3个字符。 - BalusC

顺便问一下，你为什么删除了 &n+j<s？当输入文件真正达到 3240 个字符时，这会导致 AIOBE。更多的优化：看看我如何将文件读入 char[]，你的可以被替换为 while(l<t)b[l++]=(char)r.read();，可以节省 4 个字符。 - BalusC

它不应该有任何越界，因为它只会读取缓冲区下一次迭代的部分。感谢额外的提示。 - Molehill

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dr. belisarius · Accepted Answer

Mathematica - 151个字符

    a = {2, 2, 2};
    s = Export["out.txt", 
        CellularAutomaton[{224, {2, {a, {2, 1, 2}, a}}, {1,1}}, 
                (ReadList[#1, Byte, RecordLists → 2>1] - 46)/ 42, #2][[#2]]
       /. {0 → ".", 1 → "X"}, "Table"] &

为了方便阅读，添加了空格

通过以下方式调用:

    s["c:\life.txt", 100]

动画：

alt text

您还可以获得随时间变化的平均人口图表：

alt text

从维基百科了解如何生成滑翔机的好模式。

据我所知，Mathematica 使用元胞自动机使用第30号规则生成随机数.