标题: [原创代码] 用 sed 解生命游戏 [打印本页]
作者: CrLf 时间: 2014-9-29 05:50 标题: 用 sed 解生命游戏
本帖最后由 CrLf 于 2014-9-29 06:45 编辑
老早就想用正则做这个了,这阵子某两位坛友突然搞起绳命游戏来,那我也折腾折腾紧跟潮流好了
感觉用纯正则可以替代循环,但想过去太繁琐,还是有什么用什么比较实在
为了方便测试所以用了七条 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 时间: 2014-9-29 06:10
本帖最后由 CrLf 于 2014-9-29 17:26 编辑
另附改进后的 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
- ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
- ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
- ▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓■■■▓
- ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
- ▓■■■▓▓▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓
- ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
- ▓■■■▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓▓
- ▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓■■■▓▓
- ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
- ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
- ▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓
- ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
- ▓■▓▓■■■▓▓▓▓▓■■▓▓▓▓▓■■■▓▓▓
- ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
- ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
- ▓■■■▓▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓
- ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
- ▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓■■■▓▓
- ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
- ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
- ▓■■■▓▓▓▓▓■■▓▓▓▓▓■■▓▓▓▓▓■■
- ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
- ▓■▓■■■▓▓▓▓▓■■▓▓▓▓▓■■■▓▓▓▓
- ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
- ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
复制代码
作者: 普大喜奔 时间: 2014-9-29 08:08
牛X 看不懂
作者: Linuxer 时间: 2014-9-29 12:02
太高大上了。。。好难懂。。。
作者: neorobin 时间: 2014-9-29 15:02
回复 2# CrLf
分析一下这里最核心的算法: 8进制, 同余原理 计算邻居数, 逻辑计算
设 3 X 3 方格区域如下
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 时间: 2014-9-29 15:09
回复 5# neorobin
好专业
作者: 523066680 时间: 2014-9-29 15:11
本帖最后由 523066680 于 2014-9-29 15:21 编辑
回复 2# CrLf
速度很快没说的
提示
'notepad' 不是内部或外部命令,也不是可运行的程序
或批处理文件。
因为
for /f "delims==" %%a in ('set') do set %%a=
作者: CrLf 时间: 2014-9-29 17:25
回复 5# neorobin
赞,殚精竭虑折腾了好久才鼓搞出来,以为再无可改进,结果没想到这里可以用位运算代替乘法和加法,看来需要培养培养位运算的直觉
据我所知,neorobin 和 plp626 大概是论坛里数学最好的吧
如果还有潜伏着其他的陈景润和高斯,就怪我眼瞎好了
5230 和 netbenton 虽也精通特效,但貌似是胜在逻辑而非数学造诣
作者: 523066680 时间: 2014-9-29 18:58
回复 8# CrLf
百度:陶哲轩
作者: neorobin 时间: 2014-9-29 19:23
回复 9# 523066680
美女必须登场, 比楼上 教授哥哥 还年轻两岁哦
欢迎光临 批处理之家 (http://www.bathome.net/) |
Powered by Discuz! 7.2 |