Code Golf:有限状态机!
Ada*_*tan 35 python language-agnostic code-golf state-machine
有限状态机
确定性有限状态机是一种简单的计算模型,广泛用作基础CS课程中自动机理论的介绍.它是一个简单的模型,相当于正则表达式,它确定某个输入字符串是Accepted还是Rejected.抛开一些手续,有限状态机的运行包括:
- 字母表,一组字符.
- 状态,通常可视化为圆圈.其中一个州必须是开始状态.一些州可能会接受,通常可视化为双圈.
- 过渡,通常可视化为状态之间的定向拱,是与字母相关联的状态之间的有向链接.
- 输入字符串,字母字符列表.
一个运行在机器上开始处于起步状态.读取输入字符串的每个字母; 如果当前状态与对应于该字母的另一个状态之间存在转换,则当前状态将更改为新状态.在读取最后一个字母后,如果当前状态是接受状态,则接受输入字符串.如果最后一个状态不是接受状态,或者一个字母在运行期间没有来自状态的相应拱门,则拒绝输入字符串.
注意:这种短暂的破坏远不是FSM的完整,正式的定义; 维基百科的精彩文章是对该主题的精彩介绍.
例
例如,以下机器告知从左到右读取的二进制数是否具有偶数个0s:
- 字母表是集合
{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个代表奖金.
参考实施
这里提供了一个参考Python实现.请注意,空字符串输入已放宽输出要求.
附录
输出格式
根据大众需求,以下输出也可用于空输入字符串:
ACCEPT
要么
REJECT
没有在前一行写的第一个状态.
州名
有效状态的名字是英文字母后跟任意数量的字母,_以及数字,很像变量的名称,例如State1,state0,STATE_0.
输入格式
像大多数代码高尔夫球一样,您可以假设您的输入是正确的.
答案摘要:
- Cobol - 4078个字符
- Python - 171个字符,568个字符,203个字符,218个字符,269个字符
- sed - 137个字符
- 红宝石 - 145个字符,183个字符
- Haskell - 192个字符,189个字符
- LISP - 725个字符
- Perl - 184个字符
- Bash - 184个字符
- Rexx - 205个字符
- Lua - 356个字符
- F# - 420个字符
- C# - 356个字符
- Mixal - 898个字符
的sed137溶液是最短的,红宝石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
所以,除非有澄清,否则赏金将归入红宝石解决方案.
Nas*_*nov 23
Python 2.7+, 201 192 187 181 179 175 171个字符
PS.问题放松后(无需在空输入上输出状态行),这里的新代码明显更短.如果你的版本是<2.7,那么就没有dict理解,所以不要{c+o:s for o,c,s in i[1:-1]}试试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]
我想在有人抨击我之前道歉:代码行为与原始规范略有不同 - 每个问题 - 评论讨论.这是我讨论的插图.
PS.虽然我喜欢与最终状态在同一行上的ACCEPT/REJECT分辨率,但我可以通过添加'\n'+(5个字符)来移动到孤独(例如想象结果将由愚蠢的脚本解析,只关心最后一行是接受还是拒绝))到最后print的+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
- `print'ARCECJEEPCTT'[s>'Z':: 2]`是一个美丽的东西,值得一个独立的赞成:-) (15认同)
- 真？-1,为什么？!:-( (2认同)
- @paxdiablo:这是一个讽刺,我觉得牺牲可读性是不好的; 但是我能做些什么 - 我很虚弱,我把我的灵魂卖掉了2更少,从'print('ACCEPT','REJECT')[s>'Z'] (2认同)
Joe*_*ger 21
我今天感觉很复古,我的选择语言是IBM Enterprise Cobol - 字数2462 4078(对不起,从屏幕导向设备粘贴,尾随空间是一个悲剧性的副作用):
Identification Division.
Program-ID. FSM.
Environment Division.
Data Division.
Working-Storage Section.
01 FSM-Storage.
*> The current state
05 Start-State Pic X(2).
05 Next-State Pic X(2).
*> List of valid states
05 FSM-State-Cnt Pic 9.
05 FSM-States Occurs 9
Pic X(2).
*> List of valid transitions
05 FSM-Trans-Cnt Pic 999.
05 FSM-Trans Occurs 999.
10 Trans-Start Pic X(2).
10 Trans-Char Pic X.
10 Trans-End Pic X(2).
*> Input
05 In-Buff Pic X(72).
*> Some work fields
05 II Pic s9(8) binary.
05 JJ Pic s9(8) binary.
05 Wk-Start Pic X(2).
05 Wk-Char Pic X.
05 Wk-End Pic X(2).
05 Wk-Cnt Pic 999.
05 Pic X value ' '.
88 Valid-Input value 'V'.
05 Pic X value ' '.
88 Valid-State value 'V'.
05 Pic X value ' '.
88 End-Of-States value 'E'.
05 Pic X value ' '.
88 Trans-Not-Found value ' '.
88 Trans-Found value 'T'.
Linkage Section.
01 The-Char-Area.
05 The-Char Pic X.
88 End-Of-Input value x'13'.
05 The-Next-Char Pic X.
Procedure Division.
Perform Load-States
Perform Load-Transitions
Perform Load-Input
Perform Process-Input
Goback.
*> Run the machine...
Process-Input.
Move FSM-States (1) to Start-State
Set address of The-Char-Area to address of In-Buff
Perform until End-Of-Input
Perform Get-Next-State
Set address of The-Char-Area to address of The-Next-Char
Move Next-State to Start-State
End-Perform
If Start-State (1:1) is Alphabetic-Lower
Display 'REJECT'
Else
Display 'ACCEPT'
End-If
Exit.
*> Look up the first valid transition...
Get-Next-State.
Set Trans-Not-Found to true
Perform varying II from 1 by 1
until (II > FSM-State-Cnt)
or Trans-Found
If Start-State = Trans-Start (II)
and The-Char = Trans-Char (II)
Move Trans-End (II) to Next-State
Set Trans-Found to true
End-If
End-Perform
Display Start-State ' ' The-Char ' -> ' Next-State
Exit.
*> Read the states in...
Load-States.
Move low-values to In-Buff
Accept In-Buff from SYSIN
Move 0 to FSM-State-Cnt
Unstring In-Buff
delimited by ' '
into FSM-States (1) FSM-States (2) FSM-States (3)
FSM-States (4) FSM-States (5) FSM-States (6)
FSM-States (7) FSM-States (8) FSM-States (9)
count in FSM-State-Cnt
End-Unstring
Exit.
*> Read the transitions in...
Load-Transitions.
Move low-values to In-Buff
Accept In-Buff from SYSIN
Perform varying II from 1 by 1
until End-Of-States
Move 0 to Wk-Cnt
Unstring In-Buff
delimited by ' '
into Wk-Start Wk-Char Wk-End
count in Wk-Cnt
End-Unstring
If Wk-Cnt = 3
Add 1 to FSM-Trans-Cnt
Move Wk-Start to Trans-Start (FSM-Trans-Cnt)
Move Wk-Char to Trans-Char (FSM-Trans-Cnt)
Move Wk-End to Trans-End (FSM-Trans-Cnt)
Move low-values to In-Buff
Accept In-Buff from SYSIN
Else
Set End-Of-States to true
End-If
End-Perform
Exit.
*> Fix input so it has newlines...the joys of mainframes
Load-Input.
Perform varying II from length of In-Buff by -1
until Valid-Input
If In-Buff (II:1) = ' ' or In-Buff (II:1) = low-values
Move x'13' to In-Buff (II:1)
Else
Set Valid-Input to true
End-If
End-Perform
Exit.
End Program FSM.
- Cobol的名声不好,因为人们记得打卡和代码表的旧时代.1985年和2002年的标准确实改善了语言. (6认同)
- COBOL!太酷了,有人可以用*那种语言编写有意义的代码. (3认同)
- 虽然我很佩服任何知道COBOL的人(因为我在System z上工作),但我认为Code Golf的想法是获得_shortest_答案.所以我不完全确定为什么这个有这么多的赞成票:-) (3认同)
- 我喜欢这比较短的实现有更多的选票. (2认同)
Nab*_*abb 19
sed - 118 137个字符
这是使用-r标志(+3),总共134 + 3 = 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
这应该处理没有正确转换的输入...希望它现在完全符合规范......
Ruby 1.9.2 - 178 190 182 177 153 161 158 154 145个字符
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
Adam提供了参考实现.在我制作之前我没有看到它,但逻辑是相似的:
编辑:这是Python 2.6代码.我没有尽量减少长度; 我只是试图让它在概念上变得简单.
import sys
a = sys.stdin.read().split('\n')
states = a[0].split()
transitions = a[1:-2]
input = a[-2]
statelist = {}
for state in states:
statelist[state] = {}
for start, char, end in [x.split() for x in transitions]:
statelist[start][char] = end
state = states[0]
for char in input:
if char not in statelist[state]:
print state,char
print "REJECT"
exit()
newstate = statelist[state][char]
print state, char, '->', newstate
state = newstate
if state[0].upper() == state[0]:
print "ACCEPT"
else:
print "REJECT"