[原创代码] 用 sed 解生命游戏

CrLf

老早就想用正则做这个了，这阵子某两位坛友突然搞起绳命游戏来，那我也折腾折腾紧跟潮流好了
感觉用纯正则可以替代循环，但想过去太繁琐，还是有什么用什么比较实在
为了方便测试所以用了七条 sed，至于怎么合并成一条，有一点大致的思路，不知道可不可行

@echo off
(for %%a in (
	▓■■■▓▓▓▓
	▓▓▓▓▓▓▓▓
	▓▓▓▓▓▓▓▓
	▓▓■■▓▓▓▓
	▓■■■▓▓▓▓
	▓▓■▓▓▓▓▓
	▓▓▓▓▓▓▓▓
	▓▓▓▓▓▓▓▓
) do echo %%a)>a.txt
::生成初始图，任意高宽都可以

:loop

set /a num+=1
title 第 %num% 次循环

sed -r "s/■/1/g;s/▓/0/g" a.txt>b.txt
::第一步，从兼容性和简洁两方面考虑，将字符映射为 0 和 1

sed -r -n "s/(.).*(.)/\2&\1/;H;${g;s/([^\n]+).*\n(.+)/\2\n&\n\1/;p}" b.txt>c.txt
::第二步，根据对边向外扩展

sed -r ":a;s/^(\w)(\w)(\w)(.*)/\2\3\4#\2\1\3/;ta;s/^\w+//" c.txt >d.txt
::第三步，为每列生成其左右列的索引


sed -r -n "H;${g;s/^\n+//g;:b;:a;s/^(\S+)\n(\S+)\n(\S+)\n(.*)/\2\n\3\n\4\n\n\2 \1 \3/;tb;s/^\S+\n(\S+\n)?//;s/\n\n/\n/g;p}" d.txt>e.txt
::第四步，为每行生成其上下行的索引

sed -r -n "/./{:c;s/#(...)(.* )#(...)(.* )#(...)(.*)/\2\4\6@\1\3\5/;tc;s/ //g;p}" e.txt>f.txt
::第五步，连接行列索引

sed -r "s/([01])0+/\1/g;s/@(.)11\>/~\1/g;s/@.111\>/~1/g;s/@[01]+/~0/g;" f.txt>g.txt
::第六步，根据周边八格存活的数量判断当前格的生死

sed "s/~1/■/g;s/~0/▓/g" g.txt>h.txt
::第七步，做第一步的逆操作

cls & type h.txt
echo 任意键查看下一个循环
pause

type h.txt>a.txt
goto :loop
复制代码

--------------------------------------------------------------------
链接：
绳命游戏的介绍和 bat 版：http://bbs.bathome.net/viewthread.php?tid=11049
perl 版：http://bbs.bathome.net/thread-31995-1-1.html
python 版：http://bbs.bathome.net/thread-32111-1-1.html

CrLf

另附改进后的 bat 版生命游戏算法（第 6 版），在原先算法（第 5 版）的基础上提高 25% 效率：

@echo off &setlocal enabledelayedexpansion
echo>计时.txt %time%
for /f "delims==" %%a in ('set') do set %%a=
echo 第1代
for /f "skip=29 useback delims=" %%a in ("%~0") do (
	echo %%a
	set /a "行25+=1"
	set tmp=%%a&set "tmp=!tmp:■=1!"&set tmp=!tmp:▓=0!
	set 行!行25!=!tmp:~-1!!tmp!!tmp:~0,1!
)
set 行27=000000000000000000000000000
for /l %%i in (2 1 100) do (
	echo 第%%i代
	set 行0=!行25!&set 行26=!行1!
	for /l %%Y in (0 1 25) do (
		set tmp=
		set /a y1=%%Y+1,y2=y1+1
		for /f "tokens=1,2" %%a in ("!y1! !y2!") do (
			for /l %%X in (0 1 24) do (
				set /a "xy=(0!行%%Y:~%%X,3!!行%%a:~%%X,3!!行%%b:~%%X,3!&0111101111)%%7,xy=^!(xy-2)*(!行%%a:~%%X,2!&1)+^!(xy-3)"
				set tmp=!tmp!!xy!
			)
		)
		set 行%%Y=!last:~-1!!last!!last:~0,1!
		if !y1! neq 26 set last=!tmp!&set tmp=!tmp:1=■!&echo !tmp:0=▓!
	)
)
echo>>计时.txt %time%
type 计时.txt&pause&exit
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓■■■▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓▓
▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓■■■▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■▓▓■■■▓▓▓▓▓■■▓▓▓▓▓■■■▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓■■■▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓■■▓▓▓▓▓■■▓▓▓▓▓■■
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■▓■■■▓▓▓▓▓■■▓▓▓▓▓■■■▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
复制代码

普大喜奔

牛X 看不懂

Linuxer

太高大上了。。。好难懂。。。

neorobin

回复 2# CrLf

分析一下这里最核心的算法:  8进制, 同余原理 计算邻居数, 逻辑计算

设 3 X 3 方格区域如下

a	b	c
d	e	f
g	h	i

a,b,c,d,e,f,g,h,i  的值均为 0 或者 1, 0abcdefghi 可以构成一个 8 进制数, 换算成十进制就是
0abcdefghi = a*8^8 + b*8^7 + c*8^6 + d*8^5 + e*8^4 + f*8^3 + g*8^2 + h*8^1 + i*8^0
根据同余定理,  8^8, 8^7, ... 8^2, 8 对 7 的余数都是 1, 所以 0abcdefghi %% 7 = (a+b+c+d+e+f+g+h+i) %% 7
a+b+c+d+e+f+g+h+i 的值域为 [0,9], 这是 3 X 3 区域的总人口数, 取余数后有这样一个映射
[0,1,2,3,4,5,6,7,8,9] --> [0,1,2,3,4,5,6,0,1,2]

而如果去掉中间方格 e 时有
(0abcdefghi & 0111101111) %% 7 = (a+b+c+d+f+g+h+i) %% 7
a+b+c+d+f+g+h+i 的值域为 [0,8], 是中间方格的邻居总数, 取余数后有这样一个映射
[0,1,2,3,4,5,6,7,8] --> [0,1,2,3,4,5,6,0,1]

康威生命游戏的规则是 B3/S23, 即在空位置的邻居有 3 个时, 可以在此位置新生;  在某位置有生命 且 周围邻居是 2 或 3 个时, 此位置生命可以继续存活; 其他任何情况下, 一个位置的生命将死亡, 或者保持无生命.
这个规则还可以换成如下两种不同的描述:
A. 当某位置的邻居为 2 个时, 此位置的下一代保持当前状态;  当邻居数为 3 个时, 无论当前状态如何, 下一代一定有生命.
B. 当 3X3 区域的人口总数 < 3 个时, 下一代在中心位置一定没有生命; 当区域人口总数 = 3 个时, 下一代在中心位置一定有生命; 当区域人口总数 = 4 个时, 中心位置保持当前状态; 当人口总数 > 4 个时, 下一代在中心位置一定没有生命.

以下是 描述 A 的伪代码
set /a "n=(0abcdefghi & 0111101111)%%7, next=(^!(n-2) & e) +^!(n-3)"
n=(0abcdefghi & 0111101111) %%7 求得邻居数对 7 的余数, 在描述 A 中, 由于邻居数 [7,8] 和 [0,1] 的结果是一样的(在中心位置下一代都不会有生命),  所以取余映射不会造成错误
next=(^!(n-2) & e) +^!(n-3)  当 n = 2 时, 取 单元格 e 的值;  当 n = 3 时, 得 1; 其他各种情况, 最后均得 0.

以下是 描述 B 的伪代码
set /a "n=0abcdefghi %% 7, next=^!(n-4) & e | ^!(n-3)"
n=0abcdefghi %% 7 求得总人口数对 7 的余数, 在描述 B 中, 由于人口数 [7,8,9] 和 [0,1,2] 的结果是一样的(在中心位置下一代都不会有生命),  所以取余映射不会造成错误
next=^!(n-4) & e | ^!(n-3) 当 n = 4 时, 取单元格 e 的值;  当 n = 3 时, 得 1;  其他各种情况, 最后得 0.

楼主代码中
xy=^!(xy-2)*(!行%%a:~%%X,2!&1)+^!(xy-3)
也可以写成 (   !行%%a:~%%X,2!  有4种情况: 8进制: 00, 01  十进制: 10, 11  )
xy=^!(xy-2) & !行%%a:~%%X,2! | ^!(xy-3)

以下是测试代码

@echo off & setlocal enableDelayedExpansion
mode 80,600
set "A= *"
for %%a in (0 1) do for %%b in (0 1) do for %%c in (0 1) do for %%d in (0 1) do (
        for %%e in (0 1) do for %%f in (0 1) do for %%g in (0 1) do for %%h in (0 1) do for %%i in (0 1) do (
                set "S=%%a%%b%%c%%d!A:~%%e,1!%%f%%g%%h%%i" & set "S=!S:0=_!"
                REM echo !S!
                set /a "popu=0x%%a%%b%%c%%d%%e%%f%%g%%h %% 15 + %%i"
                REM set /a "n=(0%%a%%b%%c%%d%%e%%f%%g%%h%%i & 0111101111) %% 7, n=^!(n-2) * (%%d%%e & 1) + ^!(n-3)"
                REM set /a "n=(0%%a%%b%%c%%d%%e%%f%%g%%h%%i & 0111101111) %% 7, n=^!(n-2) & %%e | ^!(n-3)"

                set /a "n=0%%a%%b%%c%%d%%e%%f%%g%%h%%i %% 7, n=^!(n-4) & %%e | ^!(n-3)"

                if !n!==1 (if %%e==0 (set B_!popu! !S!=1) else set S_!popu! !S!=1) else set "D_!popu! !S!=0"
        )
)
set B_ & set S_ & set D_
pause
复制代码

523066680

回复 5# neorobin


    好专业

523066680

回复 2# CrLf

    速度很快没说的

提示
'notepad' 不是内部或外部命令，也不是可运行的程序
或批处理文件。

因为
for /f "delims==" %%a in ('set') do set %%a=

CrLf

回复 5# neorobin


赞，殚精竭虑折腾了好久才鼓搞出来，以为再无可改进，结果没想到这里可以用位运算代替乘法和加法，看来需要培养培养位运算的直觉
据我所知，neorobin 和 plp626 大概是论坛里数学最好的吧
如果还有潜伏着其他的陈景润和高斯，就怪我眼瞎好了
5230 和 netbenton 虽也精通特效，但貌似是胜在逻辑而非数学造诣

523066680

回复 8# CrLf

     百度：陶哲轩

neorobin

回复 9# 523066680

美女必须登场,   比楼上 教授哥哥 还年轻两岁哦