Board logo

标题: [原创代码] 用 sed 解生命游戏 [打印本页]

作者: CrLf    时间: 2014-9-29 05:50     标题: 用 sed 解生命游戏

本帖最后由 CrLf 于 2014-9-29 06:45 编辑

老早就想用正则做这个了,这阵子某两位坛友突然搞起绳命游戏来,那我也折腾折腾紧跟潮流好了
感觉用纯正则可以替代循环,但想过去太繁琐,还是有什么用什么比较实在
为了方便测试所以用了七条 sed,至于怎么合并成一条,有一点大致的思路,不知道可不可行
  1. @echo off
  2. (for %%a in (
  3. ▓■■■▓▓▓▓
  4. ▓▓▓▓▓▓▓▓
  5. ▓▓▓▓▓▓▓▓
  6. ▓▓■■▓▓▓▓
  7. ▓■■■▓▓▓▓
  8. ▓▓■▓▓▓▓▓
  9. ▓▓▓▓▓▓▓▓
  10. ▓▓▓▓▓▓▓▓
  11. ) do echo %%a)>a.txt
  12. ::生成初始图,任意高宽都可以
  13. :loop
  14. set /a num+=1
  15. title 第 %num% 次循环
  16. sed -r "s/■/1/g;s/▓/0/g" a.txt>b.txt
  17. ::第一步,从兼容性和简洁两方面考虑,将字符映射为 0 和 1
  18. sed -r -n "s/(.).*(.)/\2&\1/;H;${g;s/([^\n]+).*\n(.+)/\2\n&\n\1/;p}" b.txt>c.txt
  19. ::第二步,根据对边向外扩展
  20. sed -r ":a;s/^(\w)(\w)(\w)(.*)/\2\3\4#\2\1\3/;ta;s/^\w+//" c.txt >d.txt
  21. ::第三步,为每列生成其左右列的索引
  22. 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
  23. ::第四步,为每行生成其上下行的索引
  24. sed -r -n "/./{:c;s/#(...)(.* )#(...)(.* )#(...)(.*)/\2\4\6@\1\3\5/;tc;s/ //g;p}" e.txt>f.txt
  25. ::第五步,连接行列索引
  26. sed -r "s/([01])0+/\1/g;s/@(.)11\>/~\1/g;s/@.111\>/~1/g;s/@[01]+/~0/g;" f.txt>g.txt
  27. ::第六步,根据周边八格存活的数量判断当前格的生死
  28. sed "s/~1/■/g;s/~0/▓/g" g.txt>h.txt
  29. ::第七步,做第一步的逆操作
  30. cls & type h.txt
  31. echo 任意键查看下一个循环
  32. pause
  33. type h.txt>a.txt
  34. 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% 效率:
  1. @echo off &setlocal enabledelayedexpansion
  2. echo>计时.txt %time%
  3. for /f "delims==" %%a in ('set') do set %%a=
  4. echo 第1代
  5. for /f "skip=29 useback delims=" %%a in ("%~0") do (
  6. echo %%a
  7. set /a "行25+=1"
  8. set tmp=%%a&set "tmp=!tmp:■=1!"&set tmp=!tmp:▓=0!
  9. set 行!行25!=!tmp:~-1!!tmp!!tmp:~0,1!
  10. )
  11. set 行27=000000000000000000000000000
  12. for /l %%i in (2 1 100) do (
  13. echo 第%%i代
  14. set 行0=!行25!&set 行26=!行1!
  15. for /l %%Y in (0 1 25) do (
  16. set tmp=
  17. set /a y1=%%Y+1,y2=y1+1
  18. for /f "tokens=1,2" %%a in ("!y1! !y2!") do (
  19. for /l %%X in (0 1 24) do (
  20. set /a "xy=(0!行%%Y:~%%X,3!!行%%a:~%%X,3!!行%%b:~%%X,3!&0111101111)%%7,xy=^!(xy-2)*(!行%%a:~%%X,2!&1)+^!(xy-3)"
  21. set tmp=!tmp!!xy!
  22. )
  23. )
  24. set 行%%Y=!last:~-1!!last!!last:~0,1!
  25. if !y1! neq 26 set last=!tmp!&set tmp=!tmp:1=■!&echo !tmp:0=▓!
  26. )
  27. )
  28. echo>>计时.txt %time%
  29. type 计时.txt&pause&exit
  30. ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
  31. ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
  32. ▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓■■■▓
  33. ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
  34. ▓■■■▓▓▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓
  35. ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
  36. ▓■■■▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓▓
  37. ▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓■■■▓▓
  38. ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
  39. ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
  40. ▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓
  41. ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
  42. ▓■▓▓■■■▓▓▓▓▓■■▓▓▓▓▓■■■▓▓▓
  43. ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
  44. ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
  45. ▓■■■▓▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓
  46. ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
  47. ▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓▓■■■▓▓
  48. ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
  49. ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
  50. ▓■■■▓▓▓▓▓■■▓▓▓▓▓■■▓▓▓▓▓■■
  51. ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
  52. ▓■▓■■■▓▓▓▓▓■■▓▓▓▓▓■■■▓▓▓▓
  53. ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
  54. ▓■■■▓▓▓▓▓■■■▓▓▓▓▓■■■▓▓▓▓▓
复制代码

作者: 普大喜奔    时间: 2014-9-29 08:08

牛X 看不懂
作者: Linuxer    时间: 2014-9-29 12:02

太高大上了。。。好难懂。。。
作者: neorobin    时间: 2014-9-29 15:02

回复 2# CrLf

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

设 3 X 3 方格区域如下
ab 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)

以下是测试代码
  1. @echo off & setlocal enableDelayedExpansion
  2. mode 80,600
  3. set "A= *"
  4. for %%a in (0 1) do for %%b in (0 1) do for %%c in (0 1) do for %%d in (0 1) do (
  5.         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 (
  6.                 set "S=%%a%%b%%c%%d!A:~%%e,1!%%f%%g%%h%%i" & set "S=!S:0=_!"
  7.                 REM echo !S!
  8.                 set /a "popu=0x%%a%%b%%c%%d%%e%%f%%g%%h %% 15 + %%i"
  9.                 REM set /a "n=(0%%a%%b%%c%%d%%e%%f%%g%%h%%i & 0111101111) %% 7, n=^!(n-2) * (%%d%%e & 1) + ^!(n-3)"
  10.                 REM set /a "n=(0%%a%%b%%c%%d%%e%%f%%g%%h%%i & 0111101111) %% 7, n=^!(n-2) & %%e | ^!(n-3)"
  11.                 set /a "n=0%%a%%b%%c%%d%%e%%f%%g%%h%%i %% 7, n=^!(n-4) & %%e | ^!(n-3)"
  12.                 if !n!==1 (if %%e==0 (set B_!popu! !S!=1) else set S_!popu! !S!=1) else set "D_!popu! !S!=0"
  13.         )
  14. )
  15. set B_ & set S_ & set D_
  16. 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