代码高尔夫：有限状态机！

发布于 2024-10-11 15:40:26 字数 6001 浏览 5 评论 0原文

有限状态机

确定性有限状态机是一种简单的计算模型，在计算机科学基础课程中广泛用作自动机理论的介绍。它是一个简单的模型，相当于正则表达式，它确定某个输入字符串是接受还是拒绝。抛开一些形式，有限状态机的运行由以下部分组成：

字母表，一组字符。
状态，通常显示为圆圈。其中一个状态必须是开始状态。有些状态可能接受，通常显示为双圆圈。
转换通常被可视化为状态之间的有向拱门，是与字母相关的状态之间的有向链接。
输入字符串，字母字符列表。

机器上的运行从启动状态开始。读取输入字符串的每个字母；如果当前状态和与该字母对应的另一个状态之间存在转换，则当前状态更改为新状态。读完最后一个字母后，如果当前状态为接受状态，则接受输入字符串。如果最后一个状态不是接受状态，或者字母在运行期间没有对应的状态，则输入字符串将被拒绝。

注意：这个简短的解释远不是 FSM 的完整、正式的定义；维基百科的优秀文章对该主题进行了精彩的介绍。

示例

例如，以下机器判断从左到右读取的二进制数是否有偶数个 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 的运行，写为 <信> ->，后跟最终状态。示例输入的输出为：

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 行（显示第一个state) 可能会被省略，并且以下输出也是可以接受的：

ACCEPT

For 101:

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

For '10X':

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

奖品

最短的解决方案将获得 250 代表奖金。

参考实现

参考 Python 实现可在此处获取。请注意，对于空字符串输入，输出要求已放宽。

附录

输出格式

根据流行的需求，对于空输入字符串，以下输出也是可以接受的：

ACCEPT

或

REJECT

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

状态名称

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

输入格式

与大多数代码高尔夫一样，您可以假设您的输入是正确的。

答案摘要：

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

sed 137 解决方案是最短的，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 解决方案。

原文

Finite state machine

A deterministic finite state machine is a simple computation model, widely used as an introduction to automata theory in basic CS courses. It is a simple model, equivalent to regular expression, which determines of a certain input string is Accepted or Rejected. Leaving some formalities aside, A run of a finite state machine is composed of:

alphabet, a set of characters.
states, usually visualized as circles. One of the states must be the start state. Some of the states might be accepting, usually visualized as double circles.
transitions, usually visualized as directed arches between states, are directed links between states associated with an alphabet letter.
input string, a list of alphabet characters.

A run on the machine begins at the starting state. Each letter of the input string is read; If there is a transition between the current state and another state which corresponds to the letter, the current state is changed to the new state. After the last letter was read, if the current state is an accepting state, the input string is accepted. If the last state was not an accepting state, or a letter had no corresponding arch from a state during the run, the input string is rejected.

Note: This short descruption is far from being a full, formal definition of a FSM; Wikipedia's fine article is a great introduction to the subject.

Example

For example, the following machine tells if a binary number, read from left to right, has an even number of 0s:

The alphabet is the set {0,1}.
The states are S1 and S2.
The transitions are (S1, 0) -> S2, (S1, 1) -> S1, (S2, 0) -> S1 and (S2, 1) -> S2.
The input string is any binary number, including an empty string.

The rules:

Implement a FSM in a language of your choice.

Input

The FSM should accept the following input:

<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.

For example, the aforementioned machine with 1001010 as an input string, would be written as:

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

Output

The FSM's run, written as <State> <letter> -> <state>, followed by the final state. The output for the example input would be:

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

For the empty input '':

S1
ACCEPT

Note: Following your comments, the S1 line (showing the first state) might be omitted, and the following output is also acceptable:

ACCEPT

For 101:

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

For '10X':

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

Prize

A 250 rep bounty will be given to the shortest solution.

Reference implementation

A reference Python implementation is available here. Note that output requirements have been relaxed for empty-string input.

Addendum

Output format

Following popular demand, the following output is also acceptable for empty input string:

ACCEPT

REJECT

Without the first state written in the previous line.

State names

Valid state names are an English letter followed by any number of letters, _ and digits, much like variable names, e.g. State1, state0, STATE_0.

Input format

Like most code golfs, you can assume your input is correct.

Summary of answers:

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

The sed 137 solution is the shortest, ruby 145 is #2. Currently, I can't get the sed solution to work:

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

both gave me:

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

so unless It there are clarifications the bounty goes to the ruby solution.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

箜明 2024-10-18 15:40:26

Python 2.7+，201 192 187 181 179 175 171 个字符

PS。问题得到缓解后（不需要在空输入上输出状态行），这里是明显更短的新代码。如果您使用的是 <2.7 版本，则没有字典理解，因此应使用 {c+o:s for o,c,s in i[1:-1]}< /code> 尝试 dict((c+o,s)for o,c,s in i[1:-1]) 以获得 +5 的价格。

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]

及其测试输出：

# for empty input
ACCEPT

# for input '1001010'
S1 1  ->  S1
S1 0  ->  s2
s2 0  ->  S1
S1 1  ->  S1
S1 0  ->  s2
s2 1  ->  s2
s2 0  ->  S1
ACCEPT

# for input '101'
S1 1  ->  S1
S1 0  ->  s2
s2 1  ->  s2
REJECT

# for input '10X'
S1 1  ->  S1
S1 0  ->  s2
s2 X  ->  ()
REJECT

# for input 'X10'
S1 X  ->  ()
REJECT

上一个条目（len 201）：

import sys
i=list(sys.stdin)
s=i[0].split()[0]
t={}
for r in i[1:-1]:a,b,c=r.split();t[a,b]=c
try:
    for c in i[-1]:print s,c.strip(),;s=t[s,c];print' ->',s
except:print('ACCEPT','REJECT')[s>'Z'or' '<c]

在有人因此打我之前，我想道歉：代码行为与原始规范略有不同 - 每个问题评论讨论。这是我为讨论而做的例证。

附言。虽然我喜欢决议接受/拒绝与最终状态在同一行，但它可以通过添加 让我转移到孤独（例如想象结果将由只关心最后一行被接受或拒绝的愚蠢脚本解析） '\n'+（5 个字符）到最后一个打印，价格为 +5 个字符。

输出示例：

# for empty input
S1  ACCEPT

# for input '1001010'
S1 1  -> S1
S1 0  -> s2
s2 0  -> S1
S1 1  -> S1
S1 0  -> s2
s2 1  -> s2
s2 0  -> S1
S1  ACCEPT

# for input '101'
S1 1  -> S1
S1 0  -> s2
s2 1  -> s2
s2  REJECT

# for input '10X'
S1 1  -> S1
S1 0  -> s2
s2 X REJECT

# for input 'X10'
S1 X REJECT

Python 2.7+, 201 192 187 181 179 175 171 chars

PS. After the problem was relaxed (no need to output state line on empty input), here is new code that's notably shorter. If you are on version <2.7, there is no dict comprehension, so instead of {c+o:s for o,c,s in i[1:-1]} try dict((c+o,s)for o,c,s in i[1:-1]) for the price of +5.

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]

And its test output:

# for empty input
ACCEPT

# for input '1001010'
S1 1  ->  S1
S1 0  ->  s2
s2 0  ->  S1
S1 1  ->  S1
S1 0  ->  s2
s2 1  ->  s2
s2 0  ->  S1
ACCEPT

# for input '101'
S1 1  ->  S1
S1 0  ->  s2
s2 1  ->  s2
REJECT

# for input '10X'
S1 1  ->  S1
S1 0  ->  s2
s2 X  ->  ()
REJECT

# for input 'X10'
S1 X  ->  ()
REJECT

Previous entry (len 201):

import sys
i=list(sys.stdin)
s=i[0].split()[0]
t={}
for r in i[1:-1]:a,b,c=r.split();t[a,b]=c
try:
    for c in i[-1]:print s,c.strip(),;s=t[s,c];print' ->',s
except:print('ACCEPT','REJECT')[s>'Z'or' '<c]

I want to apologize before someone slaps me for it: the code behavior is slightly different from the original spec - per question-comments discussion. This is my illustration for the discussion.

PS. while i like the resolution ACCEPT/REJECT on the same line with the final state, it can me moved to solitude (e.g. imagine results are to be parsed by stupid script that only cares about last line being accept or reject) by adding '\n'+ (5 chars) to the last print for the price of +5 chars.

Example output:

# for empty input
S1  ACCEPT

# for input '1001010'
S1 1  -> S1
S1 0  -> s2
s2 0  -> S1
S1 1  -> S1
S1 0  -> s2
s2 1  -> s2
s2 0  -> S1
S1  ACCEPT

# for input '101'
S1 1  -> S1
S1 0  -> s2
s2 1  -> s2
s2  REJECT

# for input '10X'
S1 1  -> S1
S1 0  -> s2
s2 X REJECT

# for input 'X10'
S1 X REJECT

代码高尔夫：有限状态机！

有限状态机

示例

规则：

输入

输出

奖品

参考实现

附录

输出格式

状态名称

输入格式

答案摘要：

Finite state machine

Example

The rules:

Input

Output

Prize

Reference implementation

Addendum

Output format

State names

Input format

Summary of answers:

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（20）

Python 2.7+，201 192 187 181 179 175 171 个字符

Python 2.7+, 201 192 187 181 179 175 171 chars

sed -- 118 137 个字符

sed -- 118 137 characters

Ruby 1.9.2 - 178 190 182 177 153 161 158 154 145 个字符

测试脚本

输出

Ruby 1.9.2 - 178 190 182 177 153 161 158 154 145 characters

Testing Script

Outputs

Python，218 个字符

Python, 218 characters

Haskell - 252 216 204 197 192 个字符

Haskell - 252 216 204 197 192 characters

Perl — 184 个字符

Perl — 184 characters

Python 3，Chars：203

Python 3, Chars: 203

MIXAL 898 个字符

神化 Knuth！

MIXAL 898 characters

Deify Knuth!

Haskell - 189 个字符

Haskell - 189 characters

Ruby — 183

Ruby — 183

Rexx 205 个字符

Rexx 205 characters

bash - 186 185 184 chars

bash - 186 185 184 chars

Python (2.6) ~ 269 个字符。

Python (2.6) ~ 269 characters.

Lua - 248 227

Lua - 248 227

F# 420

F# 420

关于作者

相关话题

热门标签

推荐作者

1CH1MKgiKxn9p

ゞ记忆︶ㄣ

JackDx

信远

yaoduoduo1995

霞映澄塘

友情链接

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。