D码点评:6 最短的 FSM 实现

据说在每一个电台里,都有一个扫地的老太太. 很偶然地,当她经过一个主持人的身边,看了一眼音频,会低声提醒对方说:小心,电频太低无法通过验证.

144986.gif(GIF 图像,471x428 像素)

FSM

注意!

惊奇发现

在给珠海GDG 的公众号写自动应答机时,发现的:

python - Code Golf: Finite-state machine! - Stack Overflow

是的,又是伟大的 栈溢!

一次有趣的比赛:

看谁用最短的代码实现以下 FSM:

fDBWN.png(PNG 图像,220x132 像素)

  1. 操作字母表仅为 {0,1}.
  2. 状态仅为 S1 S2.
  3. 变迁规仅为 (S1, 0) -> S2, (S1, 1) -> S1, (S2, 0) -> S1 以及 (S2, 1) -> S2.
  4. The input string is any binary number, including an empty string.

约定

  • 输入是 1001010 样儿的数串
  • 输出形如:

    S1 1 -> S1 S1 0 -> s2 s2 0 -> S1 S1 1 -> S1 S1 0 -> s2 s2 1 -> s2 s2 0 -> S1 ACCEPT

  • 如果遇到违反状态变迁的,如: 10X

    S1 1 -> S1 S1 0 -> s2 s2 X REJECT

结果

最终在被管理员关闭回答前,收集到的代码情况:

  • Cobol - 4078 characters
  • Python - 171 characters, 568 characters, 203 characters, 218 characters, 269 characters
  • sed - 137 characters
  • ruby - 145 characters, 183 characters
  • Haskell - 192 characters, 189 characters
  • LISP - 725 characters
  • Perl - 184 characters
  • Bash - 184 characters
  • Rexx - 205 characters
  • Lua - 356 characters
  • F# - 420 characters
  • C# - 356 characters
  • Mixal - 898 characters

是的,明显的 sed 赢了! 但是真实的感觉?!

sed 137个字符

$!{H;D}
/:/!{G;s/(\S*)..(\S*)/\2 \1:/}
s/(.* .)(.*\n\1 (\S*))/\1 -> \3\n\3 \2/
/-/{P;D}
/^[A-Z].* :/cACCEPT
s/( .).*/\1/
/:/!P
cREJECT

Python 171个字符

import sys
i=map(str.split,sys.stdin)
s=i[0][0]
for c in''.join(i[-1]):
    if s:o=s;s={c+o:s for o,c,s in i[1:-1]}.get(c+s,());print o,c,'->',s
print'ARCECJEEPCTT'[s>'Z'::2]

Haskell 192个字符

s%(c:d,t)=s++' ':c:maybe('\n':x)(\[u]->" -> "++u++'\n':u%(d,t))(lookup[s,[c]]t)
s%_|s<"["="ACCEPT\n"|1<3=x
x="REJECT\n"
p(i:j)=(words i!!0)%(last j,map(splitAt 2.words)j)
main=interact$p.lines

是也乎

好的,结论很明显了:

  • 给人看的,一般都不简洁
  • 给机械用的,一般可以很精简
  • 作到平衡的, 只有 Python
  • Ruby? 世界上有这门语言嘛?

[11.17] PyCon2013CHina 珠海场

  • Python 年度大会
  • Pythonner 大趴
  • Pythonista 相亲集会
  • Pythonic 体验交流

请及时举报你身边的 华蠎行者! 举报热线: zoomquiet+pycon (AT) gmail.com

巡阅


以上...


|_|0|_|
|_|_|0|
|0|0|0|

加入 珠海GDG

  1. 注册 G+
  2. 关注 GDG Zhuhai
  3. 成为 GDG Zhuhai开发者

通过 珠海GDG 可以:

    第一时间获知谷歌最新的技术,
    可以学到如何去谷歌平台上赚钱的思路和方法,
    可以认识很多有可能将来一起走上自己创业道路的人,
    可以学会把你的创新带向国际市场,
    参加那里的活动有经常和国际上的开发者们进行交流的机会...

PS:

若无意外,题图都是从原文提取或是通过 Google 图片搜索出来的, 版权属左, 不负责任 ;-)

PPS:

珠海GDG wechat/Blog 都是欢迎投稿的,只要追认内容吻合以下条件:

0. 有趣 ~ 至少是自个儿有兴趣的领域吧...
1. 有料 ~ 至少有点儿原创的东西吧..
2. 有种 ~ 至少不能是成功学吧!

有好物的,及时向大妈们吼: support@zhgdg.org

微信栏目

当前应该是:

    G术图书 (gb:推荐好书,书无中外)
    D码点评 (dd:麻辣评点,善意满盈)
    G说公论 (gt:时评杂文,新旧不拘)
    珠的自白(dm:大妈自述,每周一篇)
    海选文章(hd:得要相信,大妈法眼)

总之! 珠海的组委大妈们,决定开始坚持发文,方方面面细细同大家分享/交流

总之! 请大家告诉大家, 珠海生活中的技术社区 已经认真回归 微信,都来订阅吧!

订阅方法

  • 搜索微信号 GDG-ZhuHai
  • 或查找公众号: GDG珠海
  • 或扫描: qrcode_for_gh_5e32c47b5b23_258.jpg

GDG珠海 社区资源:

  • 邮件列表: gdg-zhuhai@googlegroups.com (可发空邮件到 gdg-zhuhai+subscribe@googlegroups.com 即完成订阅)
  • 微博: @GDG珠海
  • 微信: GDG珠海
  • G+ 主页: GDG ZhuHai
  • G+ 社群: ZhuHai GDG
2013-10-01  

声明: 本文采用 BY-NC-SA 授权。转载请注明转自: #ZHGDG#

comments powered by Disqus