python - 高尔夫代码: Finite-state machine!

Question

Locked. This question and its answers are locked，因为该问题是题外话，但具有历史意义。它目前不接受新的答案或互动。








有限状态机

确定性有限状态机是一种简单的计算模型，在基础CS类(class)中被广泛用作自动机理论的介绍。它是一个简单的模型，等效于正则表达式，它确定某个输入字符串被接受还是被拒绝。 Leaving some formalities aside，有限状态机的运行由以下组成:

字母，一组字符。

状态，通常可视化为圆圈。状态之一必须是开始状态。有些状态可能会被接受，通常可视化为双圆圈。

过渡通常可视化为状态之间的有向弓，是与字母相关联的状态之间的有向链接。

输入字符串，一个字母字符列表。

在运行状态下，机器开始运行。读取输入字符串的每个字母；如果当前状态和对应于字母的另一个状态之间存在转换，则当前状态将更改为新状态。读取最后一个字母后，如果当前状态为接受状态，则接受输入字符串。如果最后一个状态不是接受状态，或者在运行过程中某个字母没有来自该状态的相应拱形，则拒绝输入字符串。

注意:这种短暂的破坏远不是FSM的完整正式定义； Wikipedia's fine article是对该主题的出色介绍。

例子

例如，下面的机器告诉从左到右读取的二进制数是否具有偶数个 0:

字母是设置的{0,1}。

状态为S1和S2。

转换是(S1, 0) -> S2，(S1, 1) -> S1，(S2, 0) -> S1和(S2, 1) -> S2。

输入字符串是任何二进制数字，包括一个空字符串。

规则:

以您选择的语言实现FSM。

输入

FSM应该接受以下输入:

<States>       List of state, separated by space mark.
               The first state in the list is the start state.
               Accepting states begin with a capital letter.
<transitions>  One or more lines. 
               Each line is a three-tuple:
               origin state, letter, destination state)
<input word>   Zero or more characters, followed by a newline.

例如，上述将 1001010作为输入字符串的机器将写为:

S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
1001010

输出

FSM的运行，写为 <State> <letter> -> <state>，后跟最终状态。示例输入的输出为:

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

对于空的 ''输入:

S1
ACCEPT

注意:在您的注释之后，可以省略 S1行(显示第一个状态)，并且以下输出也是可以接受的:

ACCEPT

对于 101:

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

对于 '10X':

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

奖

最短的解决方案为250 rep赏金。

引用实现

引用Python实现可在 here中获得。请注意，对于空字符串输入，已经放宽了输出要求。

附录

输出格式

根据普遍的需求，对于空的输入字符串，以下输出也是可接受的:

ACCEPT

或者

REJECT

没有在前一行中写入第一个状态。

州名

有效的州名称是英文字母，后跟任意数量的字母， _和数字，非常类似于变量名，例如 State1， state0， STATE_0。

输入格式

像大多数代码高尔夫球一样，您可以假定输入正确。

答案摘要:

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 137 solution是最短的， ruby 145是＃2。目前，我无法使用sed解决方案:

cat test.fsm | sed -r solution.sed
sed -r solution.sed test.fsm

都给了我:

sed: -e expression #1, char 12: unterminated `s' command

因此，除非有明确说明，否则悬赏金将用于 ruby 解决方案。

最佳答案

Ruby 1.9.2-178190182182177153161158154145字符

h={}
o=s=p
$<.map{|l|o,b,c=l.split;h[[o,b]]=c;s||=o}
o.chars{|c|puts s+' '+c+((s=h[[s,c]])?' -> '+s :'')}rescue 0
puts s&&s<'['?:ACCEPT: :REJECT

测试脚本

[
  "S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
1001010",
  "S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
101",
  "S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
",
  "S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
10X"
].each do |b|
  puts "------"
  puts "Input:"
  puts b
  puts
  puts "Output:"
  puts `echo "#{b}" | ruby fsm-golf.rb`
  puts "------"
end

产出

所有输入均以:

S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2

Input: '1001010'
Output:
S1 1 -> S1
S1 0 -> s2
s2 0 -> S1
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
s2 0 -> S1
ACCEPT

Input: '101'
Output:
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
REJECT

Input: 'X10'
Output:
S1 X
REJECT

Input: ''
Output:
ACCEPT

Input: '10X'
Output:
S1 1 -> S1
S1 0 -> s2
s2 X
REJECT

关于python - 高尔夫代码: Finite-state machine!，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4661818/

上一篇：python - 从字节文件中打开 PIL 图像

下一篇：python - 如何限制循环的迭代？

相关文章：

python - 如何处理异常，同时在 python 中附加一个列表，其中包含从存储从 .json 文件读取的数据的字典中读取的数据？

python - 无法将 BoxSizer 放入 wxpython 中的笔记本中

python - torch transform.resize() 与 cv2.resize()

design-patterns - 为这组对象寻找一个好的设计模式

algorithm - 西方最快的布景操作

python - 使用 string.translate() 将不可打印的字符转换为点

python - 在Python中使用 Storm

language-agnostic - 点与线段之间的最短距离

code-golf - Code Golf : the Mandelbrot set

string - Code Golf : "Color highlighting" of repeated text

Answer 1

Ruby 1.9.2-178190182182177153161158154145字符

h={}
o=s=p
$<.map{|l|o,b,c=l.split;h[[o,b]]=c;s||=o}
o.chars{|c|puts s+' '+c+((s=h[[s,c]])?' -> '+s :'')}rescue 0
puts s&&s<'['?:ACCEPT: :REJECT

测试脚本

[
  "S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
1001010",
  "S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
101",
  "S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
",
  "S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
10X"
].each do |b|
  puts "------"
  puts "Input:"
  puts b
  puts
  puts "Output:"
  puts `echo "#{b}" | ruby fsm-golf.rb`
  puts "------"
end

产出

所有输入均以:

S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2

Input: '1001010'
Output:
S1 1 -> S1
S1 0 -> s2
s2 0 -> S1
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
s2 0 -> S1
ACCEPT

Input: '101'
Output:
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
REJECT

Input: 'X10'
Output:
S1 X
REJECT

Input: ''
Output:
ACCEPT

Input: '10X'
Output:
S1 1 -> S1
S1 0 -> s2
s2 X
REJECT