layout: post author: zoomq title: D码点评:6 最短的 FSM 实现 description: ~ 麻辣评点,善意满盈 categories: gDgcoDe tags: gdg D码点评 dd wechat coding

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

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

FSM

注意!

不是: 飞天面条神教(Flying Spaghetti Monsterism)
不是: 自由软件运动(Free software movement)
而是: 有限状态自动机(Finite State Machine)
- 参考: 有限状态机 - 维基百科,自由的百科全书

惊奇发现

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

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

是的,又是伟大的栈溢!

一次有趣的比赛:

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

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

操作字母表仅为 {0,1}.
状态仅为 S1 S2.
变迁规仅为 (S1, 0) -> S2, (S1, 1) -> S1, (S2, 0) -> S1 以及 (S2, 1) -> S2.
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个字符

{% highlight python %} 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] {% endhighlight %}

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

注册 G+
关注 GDG Zhuhai
成为 GDG Zhuha开发者

通过珠海GDG 可以:

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

PS:

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

PPS:

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

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

有好物的,及时向大妈们吼: [email protected]

微信栏目

当前应该是:

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

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

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

订阅方法

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

GDG珠海社区资源:

邮件列表: [email protected] (可发空邮件到 [email protected] 即完成订阅)
微博: @GDG珠海
微信: GDG珠海
G+ 主页: GDG ZhuHai
G+ 社群: ZhuHai GDG

Author:

/mail / gittip / github

FSM