批处理编程竞赛 第2011-001期［Life 游戏］

netbenton

上世纪70年代，一些人曾疯迷于一种被称作“生命(life)游戏”的小游戏，这种游戏相当简单。
假设有一个象棋盘一样的方格网，每个方格中放置一个生命细胞，生命细胞只有两种状态：
“生”或“死”。由英国数学家John Conway确定的游戏规则如下：
   （1）如果一个细胞周围有3个细胞为生（一个细胞周围共有8个细胞），则该细胞为生，
    即该细胞若原先为死，则转为生，若原先为生，则保持不变；
   （2）如果一个细胞周围有2个细胞为生，则该细胞的生死状态保持不变；
   （3）在其它情况下，该细胞为死，即该细胞若原先为生，则转为死，若原先为死，则保持不变。
    依此规则进行迭代变化，使细胞生生死死，会得到一些有趣的结果。该游戏之所以被称为生命游戏，
是因为其简单的游戏规则反映了自然界中这样的生存规律：如果一个生命，其周围的同类生命太少的话，
会因为得不到帮助而死亡，如果太多，则会因为得不到足够的生命资源而死亡。
    用计算机模拟这个生命游戏也相当简单，可以用一个M×N象素的图象来代表M×N个细胞，
其中每一个象素，代表一个细胞，象素为黑色表示细胞为生，象素为白色代表细胞为死。
例如一个图象中几个象素所代表的生命的初始状态如下图所示，依上述规则进行行迭代变化，
则经过1次、2次、3次变化后的情况分别如下图所示：
活：■
死：▓
第 1 代
▓■■■▓▓▓▓
▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓
▓▓■■▓▓▓▓
▓■■■▓▓▓▓
▓▓■▓▓▓▓▓
▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓
第 2 代
▓▓■▓▓▓▓▓
▓▓■▓▓▓▓▓
▓▓▓▓▓▓▓▓
▓■▓■▓▓▓▓
▓■▓▓▓▓▓▓
▓■■■▓▓▓▓
▓▓▓▓▓▓▓▓
▓▓■▓▓▓▓▓
第 3 代
▓■■■▓▓▓▓
▓▓▓▓▓▓▓▓
▓▓■▓▓▓▓▓
▓▓■▓▓▓▓▓
■■▓■▓▓▓▓
▓■■▓▓▓▓▓
▓■▓■▓▓▓▓
▓▓▓▓▓▓▓▓

设定图象中每个象素的初始状态后依据上述的游戏规则演绎生命的变化，由于初始状态和迭代次数不同，
将会得到令人叹服的优美图案。

我认为，其实这是一个让程序员练手的游戏，现出一批处理代码效率比赛题：

  1，格子矩阵大小：25 X 25 初始图如下（第1代）：
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓■■■▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓▓
▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓■■■▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■▓▓■■■▓▓▓▓▓■■▓▓▓▓▓■■■▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓■■■▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓■■▓▓▓▓▓■■▓▓▓▓▓■■
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■▓■■■▓▓▓▓▓■■▓▓▓▓▓■■■▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓

  2，顶边与底边，还有左边与右边，认为是相连接的；
        2.1 补充一点：对角点也认为是相连接的，如图点Ａ，周围的8个点，分别对应对角和对边的位置。
Ｂ■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓ｃｃ
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓■■■▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓▓
▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓■■■▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■▓▓■■■▓▓▓▓▓■■▓▓▓▓▓■■■▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓■■■▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓■■▓▓▓▓▓■■▓▓▓▓▓■■
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■▓■■■▓▓▓▓▓■■▓▓▓▓▓■■■▓▓▓▓
ｄ■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓ｄ
ｄ■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓Ａｄ
　　　　　　　　　　　　　　　　　　　　　　　ｃｃＢ

  3，主程序用批处理完成，可用三方命令。但是用纯其它语言编写的游戏，仅仅还原成可执行文件运行的不算
  4，以算到第100代时所花的时间作为本次比赛标准，
       注意：要把每一代结果都显示出来，
  5， 这是很要效率的，可以先写出一个可行的版本，然后慢慢优化；

  6，请参加的朋友于2011-03-07 到 2011-03-10 上传作品，请以附件形式上传，
并设置阅读权限为240，防止他人抄袭。评比结果最后公布在本楼。

  
    看看谁写的代码速度最快。一个月后（2011-03-13），将给予相应积奖励：
    效率最高的： 100积分 10技术
           第二名：   50积分    5技术
           第三名：   20积分    2技术


终于到公示代码日期了~~~

代码测试环境：
操作系统 WINXP SP3  关闭杀毒软件  不运行任何其它程序
CPU: AMD3200  1G内存DDR677

说明：
    各选手文件夹内的 file.bat 是加入统一的计时后的代码，
选手的原代码为另一个文件，欢迎测试、监督、指正。

公示名次：
获奖名次      选手                大约用时

  第1名       zm900612      00:00:09:65
  第2名       terse              00:00:14:12
  第3名       caruko           00:00:15:43

其它就不公布了，想了解和监督的朋友请下载附件。

按照料 batcher 所说的方法测试代码，排名并没有变化，

公示三天已过，得出本次竞赛最终结果为：

获奖名次      选手                大约用时

  第1名       zm900612      00:00:09:65
  第2名       terse              00:00:14:12
  第3名       caruko           00:00:15:43

[ 本帖最后由 netbenton 于 2011-3-15 19:18 编辑 ]

Gin_Q

# coding=utf-8


# 更新窗口
def upWindow():
    global SHEET
    for i in range(1,WIDTH-1):
        for j in range(1,WIDTH-1):
            print(SHEET[i][j], end='', flush=True)
        print()

# 计算
def death(status, res):
    global SHEET
    global DATA
    global WIDTH
    global A
    global B
    for i in range(1,WIDTH-1):
        for j in range(1,WIDTH-1):
            # 检查
            if SHEET[i][j] == status:
                if check(i,j) in res:
                    DATA.append((i,j))
                    
    # 取出数据
    if status == B: status = A
    elif status == A: status = B
    for n in DATA:
        SHEET[n[0]][n[1]] = status
    DATA.clear()
    upSide()
    upWindow()

    
# 检查周围点活着的数量
def check(x, y):
    global SHEET
    global A
    count = 0
    if SHEET[x-1][y] == A:
        count += 1
    if SHEET[x-1][y-1] == A:
        count += 1
    if SHEET[x-1][y+1] == A:
        count += 1
    if SHEET[x][y+1] == A:
        count += 1
    if SHEET[x][y-1] == A:
        count += 1
    if SHEET[x+1][y-1] == A:    
        count += 1
    if SHEET[x+1][y] == A:    
        count += 1
    if SHEET[x+1][y+1] == A:    
        count += 1
    return count

# 更新表格边框
def upSide():
    global SHEET
    global WIDTH
    # 交换‘四边’数据
    for n in range(1,WIDTH-1):
        SHEET[0][n] = SHEET[WIDTH-2][n]
        SHEET[WIDTH-1][n] = SHEET[1][n]
        SHEET[n][0] = SHEET[n][WIDTH-2]
        SHEET[n][WIDTH-1] = SHEET[n][1]
    # 角落
    SHEET[0][0] = SHEET[WIDTH-2][WIDTH-2]
    SHEET[WIDTH-1][WIDTH-1] = SHEET[1][1]
    SHEET[0][WIDTH-1] = SHEET[WIDTH-2][1]
    SHEET[WIDTH-1][0] = SHEET[1][WIDTH-2]

# main

# 生
A = '■'
# 死
B = '▓'

# 表格宽度
WIDTH = 10
# 表格列表
SHEET = []
# 数据暂存队列
DATA = []
# 初始化数据
for n in range(WIDTH):
    if n in [1,5]:
        SHEET.append([B,B,A,A,A,B,B,B,B,B])
    if n in [0,2,3,7,8]:
        SHEET.append([B,B,B,B,B,B,B,B,B,B])
    if n == 4:
        SHEET.append([B,B,B,A,A,B,B,B,B,B])
    if n == 6:
        SHEET.append([B,B,B,A,B,B,B,B,B,B])
    if n == 9:
        SHEET.append([B,B,A,A,A,B,B,B,B,B])

upWindow()
count = 1
while True:
    print(f'第{count}次繁衍')
    death(B, [3])
    print(f'第{count}次死亡')
    death(A, [0,1,4,5,6,7,8])
    if count >= 6:break
    count += 1
复制代码

这个步骤是先计算生，还是先计算死？
然后当前点 生了（死了）以后，是不是实时更新的呢（会影响下一个点，下一个点将计算前面那个点的状态）？
有些不解！
我计算的结果和给出答案有误！

# 四边是计算的缓存数据，请忽略

▓▓▓▓▓▓▓▓▓▓
▓▓■■■▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓
▓▓▓■■▓▓▓▓▓
▓▓■■■▓▓▓▓▓
▓▓▓■▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓
▓▓■■■▓▓▓▓▓

第一次繁衍
▓▓▓■▓▓▓▓▓▓
▓▓■■■▓▓▓▓▓
▓▓▓■▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓
▓▓■■■▓▓▓▓▓
▓▓■■■▓▓▓▓▓
▓▓■■■▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓
▓▓▓■▓▓▓▓▓▓
▓▓■■■▓▓▓▓▓

第一次死亡
▓▓▓■▓▓▓▓▓▓
▓▓■▓■▓▓▓▓▓
▓▓▓■▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓
▓▓■▓■▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓
▓▓■▓■▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓
▓▓▓■▓▓▓▓▓▓
▓▓■▓■▓▓▓▓▓

# 无计算缓存
▓■■■▓▓▓▓
▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓
▓▓■■▓▓▓▓
▓■■■▓▓▓▓
▓▓■▓▓▓▓▓
▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓

第一次繁衍
▓■■■▓▓▓▓
▓▓■▓▓▓▓▓
▓▓▓▓▓▓▓▓
▓■■■▓▓▓▓
▓■■■▓▓▓▓
▓■■■▓▓▓▓
▓▓▓▓▓▓▓▓
▓▓■▓▓▓▓▓

第一次死亡
▓■▓■▓▓▓▓
▓▓■▓▓▓▓▓
▓▓▓▓▓▓▓▓
▓■▓■▓▓▓▓
▓▓▓▓▓▓▓▓
▓■▓■▓▓▓▓
▓▓▓▓▓▓▓▓
▓▓■▓▓▓▓▓

a20150604

John Horton Conway (26 December 1937 – 11 April 2020)

His wife, Diana Conway, said his death, at a nursing home, was caused by Covid-19.

https://www.nytimes.com/2020/04/ ... ad-coronavirus.html

https://en.wikipedia.org/wiki/John_Horton_Conway

netbenton

按照料 batcher 所说的方法测试代码，排名并没有变化，

公示三天已过，得出本次竞赛最终结果为：

获奖名次      选手                大约用时

  第1名       zm900612      00:00:09:65
  第2名       terse              00:00:14:12
  第3名       caruko           00:00:15:43



***  顶楼已经更新  ***

caruko

zm的果然很快啊
其实也知道25行的数据很多地方都是重复的，可以重复利用的地方非常多，然而想高重复利用起来计算的复杂度又变高，效率不一定更好，一直没有更好的解决办法，就那样了。

CrLf

呵呵，果然有前三，不负我多日幸苦。其实也属侥幸，算法效率估计大家差不了多少，速度快慢最终还是取决于整体性能

Batcher

前三名的代码，每运行一个就重启一遍系统，这样得出的时间会不会更公平？

netbenton

参赛代码已经公示在一楼了，

公示两天后，若没有疑义，将兑现相应奖励。

初定获奖名单也已经出来了，欢迎大家的测评、监督、指正。

代码的效率有点出乎意料之外，只是参赛的代码少了点，看来论坛还是不够活跃呀~

希望下次能看到更多的人参与~~~

cutebe

也参加一下，不过挺慢的。

netbenton

今是最后一天上传了，还有参赛作品没上传的朋友，请抓紧时间了。

3月10日 23：59:59 以后上传的作品无效，以贴子最后的修改时间为准。

请再大家要看清楚一楼的参赛代码实现的标准

参赛回贴标题统一为：“参赛贴”
请参赛的朋友以附件形式上传，并设置阅读权限为240

3月11日~3月12日 会将所有参赛代码整理到顶楼，同时给出统一环境下的运行时间，并公示两天，

3月15日前，公布获奖名单。并兑现相应奖励。

CrLf

原来下载自己的附件不受权限约束啊...

CrLf

尽人事，听天命，如此而已。

[ 本帖最后由 zm900612 于 2011-3-10 22:31 编辑 ]

caruko

修改了一下，以前是自己直接按图来赋值，改为读取原始图赋值，这样应该正规公平一些吧。

CrLf

好吧，那我提交最保守的方案好了。本想今天交的，但不巧又想到新算法，嘿嘿

netbenton

zm900612 研究得还真仔细。

当然是要尽量的排除干扰的。

如果真的有两份代码运行时间很相近，只是因为cpu 的不同，或都操作系统的不同，而有先后变化的话，那就在每种环境下都运行一次，以时间之和来定胜负吧

[ 本帖最后由 netbenton 于 2011-3-8 13:44 编辑 ]