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

FSM

注意!

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

惊奇发现

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

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

是的,又是伟大的 栈溢!

一次有趣的比赛:

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

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

巡阅

• 150113 Zoom.Quiet checked